执行力
关于更新的说明
topman 发表于 2008-11-09 18:11:56
UVa 3n+1 problem
topman 发表于 2008-11-09 17:58:36
UVa 3n+1问题
1. 问题描述
编号:100.
简单描述:就是对一个整数(大于等于1),不断按照这样的规律进行运算,即如果当前数是偶数,则下一个数为当前数除以2,如果当前数为奇数,则下一个数为当前数乘3加1,整个过程直到计算到1为止.那么形成的数列的长度称为cycle-length.
问题的输入是:给定一个区间[a,b]
问题的输出为:输出给定区间(含端点)所以数的cycle-length的最大的cycle-length.
详细描述可参见这里.
2. 问题分析
2.1 直观分析
最直观的方法当然是采用蛮力法(即brute-force),将给定区间的每个数求出其cycle-length,然后在所以的cycle-length中找出最大的即可.
2.2 优化
优化是建立在分析的基础之上.
我们先对一个简单例子进行实验.
例如给定区间为B[1,10],即1,2,3,4,5,6,7,8,9,10
通过简单分析我们可以知道,通常较大的数具有较大的cycle-length,所以我们可以首先取A=9(为什么不取10,是因为9在一次处理后可变为28,大于10)按照给定的规律来进行如下:
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
可以看出,上面红色标记的部分,处于给定的区间内,而且它们的cycle-length显然是小于当前的数9的cycle-length,所以这些数可以从给定的区间内剔除掉,记住当前的cycle-length,于是
经过一次的操作后,给定的区间变为3,6
继续按照这个方法进行,直至这个区间为空,停止,其中最大的cycle-length即为所求.
2.3 得出算法
算法的描述同2.2处优化部分的分析,具体的算法描述可见3.
3. 算法描述
算法伪代码(类C)描述如下:
function getMCL
B[left, right]; //为给定的区间
mcl = 0; //mcl指max-cycle-length
while !B.empty()
{
A = getCandidate(B);//这个函数是用来找出B区间内当前最适合处理的元素,
//一般是最大的奇数,即预计可能具有较大cycle-length的元素
ccl = 1; //ccl是指current-cycle-length
while (A!=1)
{
ccl++;
A = (A%2)?(3*A+1):(A/2);
if find(B,A) //这个函数是用来判断B区间内是否存在中间结果A
pop(B,A); // 有则剔除
}
mcl = (mcl<ccl)?ccl:mcl;
}
return mcl;
4. 具体实现
5. 复杂性分析
主要的耗时部分是二层循环部分,而外层循环的次数主要取决于内层循环在区间内的命中率.没有进行过统计学的分析,但只要candidate选取合适,每次内层循环会有大于50%的命中率.
假设区间内数A的内层循环次数(即由A按照规则变为1的cycle-length)为X,平均命中率为p,那么时间复杂度为:
T(n) = X*T(n*(1-p)) //其中X为平均的cycle-length
6. 备注
在实现过程中,最初使用的是C++中的vector,但运行时的实际耗时比使用数组的蛮力法还要长,经过分析,这是因为编译器在维护vector这个数据结构时所耗时长是比较大的,特别是当使用vector的earse方法来删除某个特定元素时.所以最后还是使用最基本的数组来实现,用标记来指示删除状态.
所以在实际的算法实现中,数据结构的选取也是非常重要的,所谓的程序=算法+数据结构是也.
可以改进的地方包括有:getCandidate函数的算法,即如何预估一个具有较长cycle-length的元素;还有当内层循环出现在区间内已标记为删除状态的元素中时,这时内层循环可终止.