C语言程序设计100例之（57）：3n+1问题
例57 3n+1问题
问题描述
考虑如下的序列生成算法：从整数 n 开始，如果 n 是偶数，把它除以 2；如果 n 是奇数，把它乘 3 加1。用新得到的值重复上述步骤，直到 n = 1 时停止。例如，n = 22 时该算法生成的序列是：22，11，34，17，52，26，13，40，20，10，5，16，8，4，2，1。
人们猜想（没有得到证明）对于任意整数 n，该算法总能终止于 n = 1。这个猜想对于至少 1000 000内的整数都是正确的。
对于给定的 n，该序列的元素（包括 1）个数被称为 n 的循环节长度。在上述例子中，22 的循环节长度为 16。
输入两个数 i 和 j，你的任务是计算 i 到 j（包含 i 和 j）之间的整数中，循环节长度的最大值。
输入格式
输入每行包含两个整数 i 和 j。所有整数大于 0，小于 1 000000。
输出格式
对于每对整数 i 和 j，按原来的顺序输出 i 和 j，然后输出二者之间的整数中的最大循环节长度。这三个整数应该用单个空格隔开，且在同一行输出。对于读入的每一组数据，在输出中应位于单独的一行。
样例输入
1 10
100 200
201 210
900 1000
样例输出
1 10 20
100 200 125
201 210 89
900 1000 174
（1）编程思路。
计算给定区间中每个数的循环节长度，用max保存这些数的循环节长度的最大值。
定义数组int cache[1000000]={0}，其中cache[i]保存整数i的循环节长度，在计算过程中采用填表的方法保存已有计算结果，可以显著减少计算时间。例如，若已计算出5的循环节长度为6（cache[5]=6），则10的循环节长度为cache[10]=cache[5]+1。
另外，在中间计算过程可能会超过 int（4字节存储空间） 型数据所能表示数的范围，故采用long long （8 字节存储空间）型整数来运算。
（2）源程序。
#include
#define MAXSIZE 1000000
int cache[MAXSIZE]={0};
int counter(long long number)
{
if (number == 1)
return 1;
if (number%2==1)
number=3*number+1;
else
number/=2;
if (number < MAXSIZE )
{
if (!cache[number])
cache[number] = counter(number);
return 1 + cache[number];
}
return 1 + counter(number);
}
int main()
{
int begin,end;
while (scanf("%d%d",&begin,&end)!=EOF)
{
int max=0,t;
int left=begin int right=begin>end?begin:end; for (int k = left; k <= right; k++) { t=counter(k); if (t>max) max=t; } printf("%d %d %d\n",begin,end,max); } return 0; } 问题描述 你听说过角谷猜想吗？ 任意的正整数，比如 5， 我们从它开始，如下规则计算： 如果是偶数，则除以2，如果是奇数，则乘以3再加1。 如此循环，最终必会得到“1” ! 比如 5 的处理过程是：5 ---> 16 ---> 8 ---> 4 ---> 2 ---> 1。 一个正整数经过多少步才能变成1， 称为角谷步数。 对于5而言，步数也是5；对于1，步数为0。 编写程序，对于输入的整数n，求角谷步数为n的最小的正整数。 输入 输入包括多行，每行包含一个整数N（1<=N<=300）。 输出 对于输入的每个整数N，输出一行，包含一个整数，表示第N个幸运数字。 输入样例 输出样例 16 （1）编程思路。 同例57一样，定义数组int cache[1000000]={0}，其中cache[i]保存整数i的循环节长度。cache[i]-1的值就是整数i的角谷步数。 要求角谷步数为n的最小的正整数，从1开始搜索，若某个数i的cache[i]==n+1，则i就是所求的最小整数。 （2）源程序。 #include #define MAXSIZE 1000000 int cache[MAXSIZE]={0}; int counter(long long number) { if (number == 1) return 1; if (number%2==1) number=3*number+1; else number/=2; if (number < MAXSIZE ) { if (!cache[number]) cache[number] = counter(number); return 1 + cache[number]; } return 1 + counter(number); } int main() { int n; while (scanf("%d",&n)!=EOF) { int i,t; for (i=1; ; i++) { t=counter(i); if (t==n+1) break; } printf("%d\n",i); } return 0; } 问题描述 一个数N，如果它每一个位数字之和可以整除10，那么它就是Good Numbers。比如451就是一个Good Numbers，4+5+1=10，求[A,B]之间这样的数的个数。 输入 输入第1行包含一个整数T (T <= 10000) ，表示测试用例的组数； 之后有T行，每行两个整数A和B（0 <= A <= B <= 1018）。 输出 对于每个测试用例，输出信息为“Case #X:P”，其中X表示第X组测试用例（X从1开始）,P表示[A,B]之间Good Numbers的个数。 输入样例 1 10 1 20 输出样例 Case #1: 0 Case #2: 1 （1）编程思路。 先列出前20个Good Numbers为：0，19，28，37，46，55，64，73，82，91，109，118，127，136，145，154，163，172，181，190……。由此可以发现： [0,10]之间Good Numbers的个数为1 [0,100]之间Good Numbers的个数为10 [0,1000]之间Good Numbers的个数为100 [0,990]之间Good Numbers的个数为99 [0,992]之间Good Numbers的个数为100 …… [0,n]之间Good Numbers的个数为n/10 + (1或0)，其中加1的情况为：n/10*10 到n有1个Good Numbers。例如：n=997，则Good Numbers的个数99 +1，因为990到997之间的992就是一个Good Numbers。 （2）源程序。 #include int isOne(long long n) // 例如：997计算990-997之间有没有符合条件的数 { int s=0; for(long long i=n/10*10;i<=n;i++) { long long t=i; s=0; while (t) { s+=t%10; t/=10; } if (s%10==0) return 1; } return 0; } long long getNum(long long n) { if (n<0) return 0; if (n<=10) return 1; return n/10+isOne(n); } int main() { int t,cas=1; scanf("%d",&t); while(t--) { long long a,b; scanf("%lld%lld",&a,&b); printf("Case #%d: %lld\n",cas++,getNum(b)-getNum(a-1)); } return 0; } 问题描述 设 S(N ) 表示 N 的各位数字之和，如 S(484) = 4+8+4 = 16， S(22) = 2+2 = 4。如果一个正整数满足 S(x*x) = S(x) *S(x)，我们称之为 Rabbit N umber。比方说，22 就是一个 Rabbit Number，因为 S(484) = S(22) *S(22)。 现在，给出一个区间 [L, R]，求在该区间内的 Rabbit N umber 的个数。 输入格式 输入仅一行，为空格隔开的两个数 L 和 R（1≤L≤R≤109）。 输出格式 输出仅一行一个整数，表示所求 Rabbit N umber 的个数。 输入样例 1 58 输出样例 12 （1）编程思路。 首先，一个Rabbit Number的各位数字一定不超过3。 这个结论可简单推出。设某数字x为1位，x>=4，因为x*x有进位，所以s(x*x)= x*x/10+x*x%10；而s(x)*s(x)=x*x，这样，s(x*x)< 既然各位数字不超过3，而区间中数字的位数不超过10位，这样可以枚举每一位上的数字（0~3），对于枚举的每个数，若满足在区间[L,R]中且为Rabbit N umber的要求，则进行计数。 （2）源程序。 #include int digitSum(long long x) { long long a=x; int sum=0; while (a) { sum+=a%10; a/=10; } return sum; } int main() { long long l,r; int ans=0; int a[11],i; scanf("%lld%lld",&l,&r); int f=1; for (a[1]=0;a[1]<=1 && f;a[1]++) for (a[2]=0;a[2]<=3 && f;a[2]++) for (a[3]=0;a[3]<=3 && f;a[3]++) for (a[4]=0;a[4]<=3 && f;a[4]++) for (a[5]=0;a[5]<=3 && f;a[5]++) for (a[6]=0;a[6]<=3 && f;a[6]++) for (a[7]=0;a[7]<=3 && f;a[7]++) for (a[8]=0;a[8]<=3 && f;a[8]++) for (a[9]=0;a[9]<=3 && f;a[9]++) for (a[10]=0;a[10]<=3 && f;a[10]++) { long long num=0; for (i=1;i<=10;i++) { num=num*10+a[i]; } if (num>r) { f=0; break; } if(num>=l&&num<=r) { if(digitSum(num)*digitSum(num)==digitSum(num*num)) ans++; } } printf("%d\n",ans); return 0; }习题57
57-1 角谷步数
57-2 Good Numbers
57-3 Rabbit Number