执行力

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的元素;还有当内层循环出现在区间内已标记为删除状态的元素中时,这时内层循环可终止.