11.17 作业 Problem E: The 3n + 1 problem

Description

计算机科学中的问题往往被归纳为某一类问题（如NP问题，无法解决问题，递归等）。在这道问题中你将分析一种算法，它对所有可能的输入结果是未知的。 考虑以下算法：    1. 输入n    2. 输出n    3. 如果n=1然后停止    4. 如果n是奇数： n <-- n*3+1    5. 其他的情况：   n <-- n/2    6. 转向 2 例如：对于输入22，输出将会是22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1。据推测，该算法对于任何整数将终止于1。尽管算法很简单，目前还不清楚这一猜想是否正确。但是对于所有整数n(0<n<1,000,000)，已经过验证（事实上，符合规律的数比这还要多）。 对于给定的n，是有可能计算出该算法共输出了多少个数的，包括结尾的1，这个数叫做n的周期长度。在上面的例子中，22的周期长度是16。对于任何两个数字i和j，求出在i和j之间的数中，周期长度最大的那个数的周期长度。

Input

输入将包括一系列的整数对i和j，每行一对整数。所有整数将少于1000000 且大于0。你应该处理i和j（包括i,j） 之间的所有整数。可以假设，任何操作不会溢出32位整数。

Output

对于每一个对输入整数i和j，输出为i、j和最大周期长度。这三个数用空格分开，三个数在同一行，每两个数之间有一个空格。

Sample Input

1 10 100 200 201 210 900 1000

Sample Output

1 10 20 100 200 125 201 210 89 900 1000 174

HINT

应该把已经计算过的数的周期长度保存下来，超时的原因是已经计算过的周期长度的重复计算，

思路：

先将一个数组全部赋值为-1.如果值为-1就用函数进行运算得到结果后赋值给它。这样下次这个数就不用再进行循环运算了。大大减少了运算时间。

注：如果题目中没有明确指出在运算过程中不会溢出。需要考虑n*3会不会溢出int型的范围。这个时候就要long long int 一个数 代替n进行运算

代码：

#include<stdio.h> #include<string.h> #include<math.h> int bi(int n)//定义函数 { int k = 0; while(n!=1) { if(n%2 == 0) { n = n/2; } else { n = n*3 + 1; } k += 1; } return k+1; } int s[1000100];//开数组 int main() { int i, j, max,t; memset(s, -1, sizeof(s));//全部赋值为-1 while(scanf("%d%d",&i,&j)!=EOF) { printf("%d %d",i,j);//先输出i，j if(i > j)//比较i j大小 { t = i; i = j; j = t; } max = bi(i); for(i=i+1;;i<=j;i++) { if(s[i] == -1)//如果数据还未被记录 进行运算 如果已经被记录在数组内 直接调用 { s[i] = bi(i); } if(s[i] > max)//每次比较大小 { max = s[i]; } } printf(" %d\n",max); } return 0; }