作者：尜艾 | 来源：互联网 | 2023-07-15 19:30
程序如下：
while(n > 1)
n = (n & 1 ? 3*n + 1: n / 2);
想了好久，只想到了一点：就是一个数如果经过p次变为2的q次方的形式，那么算法复杂度就是p+q，但是p，q还是不知道怎么确定。
11 个解决方案
应该不是的，我试过的数字都可以化为2的p次方这个形式的，一个数总可以化为另外一个数，所以所有的数之间都是有关联的
哦，我打漏了一点，是n&1 == 1？3*n+1：n/2；这样好点
你还是这样写吧，更好看一点。
while(n > 1)
n = (n % 2 ? 3*n + 1: n / 2);
因为 n & 1 判断的就是最低位是否为1， 若为真仅当 n = 2^k1 + 2^k2 + ... + 2^0 = 偶数 + 1 ,
所以 n & 1 就是判断奇偶性，奇数为真，偶数为假。
下面的，嗯，先顶帖！
n没有初始值的，就是用n作为规模来衡量的，O（logn），O（n）之类的
今天才查到，原来这个就是著名的3x+1问题，到现在为止都是没有解得。本来这个是老师布置的作业。。。。。。真是无语。不过昨天受MIT那个算法视频的启发，觉得应该有一个近似的上限可以大概确定这个函数的界限。大概就是奇数的话：t(n)=t((3*n+1)/2);偶数的话是t(n)=t(n/2);那干脆我们就用t(n)=t((3*n+1)/2);这个是式子来作为计算算法复杂度的递归式，虽然放大了些，但是可以大概的确定了一个上界。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 