UVa 3n+1 问题

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.       具体实现

Cpp代码

1. #include "iostream"  
2. using namespace std;  
3.   
4. int getCandidate(int B[], int base, int n)  
5. {  
6.     int i;  
7.     for (i = n-1; i>=0; i--)  
8.     {  
9.         if (((base+i) % 2)&&(B[i]==0))  
10.             return i;  
11.     }  
12.     for (i = n-1; i>=0; i--)  
13.     {  
14.         if (!B[i])  
15.             return i;  
16.     }  
17.     return -1;  
18. }  
19. int nadd2(int left, int right)  
20. {  
21.     int Blength = right - left + 1;  
22.     int length = Blength;  
23.     int *B = new int[length];  
24.     for (int i=0; i<length; i++)  
25.         B[i] = 0;  
26.     int mcl = 0;  
27.     while (length > 0)  
28.     {  
29.         int ccl = 1;  
30.         int pos = getCandidate(B, left, Blength);  
31.         if (pos==-1)  
32.             break;  
33.         B[pos] = 1;  
34.         length--;  
35.         int A = pos+left;  
36.         while (A!=1)  
37.         {  
38.             ccl ++;  
39.             A = (A%2)?(3*A+1):(A/2);  
40.             int Apos;  
41.             if ((A-left>Blength)||(B[A-left])||(A<left))  
42.                 Apos = -1;  
43.             else  
44.                 Apos = A-left;  
45.                   
46.             //B[Apos] = 1;  
47.             if (Apos!=-1)  
48.             {  
49.                 B[Apos] = 1;  
50.                 length --;  
51.             }  
52.         }  
53.         mcl = (mcl<ccl)?ccl:mcl;  
54.     }  
55.     delete[] B;  
56.     return mcl;  
57. }  
58. int main()  
59. {  
60.     int left, right;  
61.     while(cin>>left>>right)  
62.         cout<<left<<" "<<right<<" "<<nadd2(left,right)<<endl;  
63.     return 0;  
64. }  

#include "iostream" using namespace std;  int getCandidate(int B[], int base, int n) {  int i;  for (i = n-1; i>=0; i--)  {   if (((base+i) % 2)&&(B[i]==0))    return i;  }  for (i = n-1; i>=0; i--)  {   if (!B[i])    return i;  }  return -1; } int nadd2(int left, int right) {  int Blength = right - left + 1;  int length = Blength;  int *B = new int[length];  for (int i=0; i<length; i++)   B[i] = 0;  int mcl = 0;  while (length > 0)  {   int ccl = 1;   int pos = getCandidate(B, left, Blength);   if (pos==-1)    break;   B[pos] = 1;   length--;   int A = pos+left;   while (A!=1)   {    ccl ++;    A = (A%2)?(3*A+1):(A/2);    int Apos;    if ((A-left>Blength)||(B[A-left])||(A<left))     Apos = -1;    else     Apos = A-left;         //B[Apos] = 1;    if (Apos!=-1)    {     B[Apos] = 1;     length --;    }   }   mcl = (mcl<ccl)?ccl:mcl;  }  delete[] B;  return mcl; } int main() {  int left, right;  while(cin>>left>>right)   cout<<left<<" "<<right<<" "<<nadd2(left,right)<<endl;  return 0; } 

 

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