C语言程序设计100例之（57）：3n+1问题

本文主要是介绍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 <stdio.h>

#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<end?begin:end;

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;

}

习题57

57-1 角谷步数

问题描述

你听说过角谷猜想吗？

任意的正整数，比如 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个幸运数字。

输入样例

输出样例

（1）编程思路。

同例57一样，定义数组int cache[1000000]={0}，其中cache[i]保存整数i的循环节长度。cache[i]-1的值就是整数i的角谷步数。

要求角谷步数为n的最小的正整数，从1开始搜索，若某个数i的cache[i]==n+1，则i就是所求的最小整数。

（2）源程序。

#include <stdio.h>

#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;

}

57-2 Good Numbers

问题描述

一个数N，如果它每一个位数字之和可以整除10，那么它就是Good Numbers。比如451就是一个Good Numbers，4+5+1=10，求[A,B]之间这样的数的个数。

输入

输入第1行包含一个整数T (T <= 10000) ，表示测试用例的组数；

之后有T行，每行两个整数A和B（0 <= A <= B <= 10¹⁸）。

输出

对于每个测试用例，输出信息为“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 <stdio.h>

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;

}

57-3 Rabbit Number

问题描述

设 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≤10⁹）。

输出格式

输出仅一行一个整数，表示所求 Rabbit N umber 的个数。

输入样例

1 58

输出样例

（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)< <s(x)*s(x)，一定不是Rabbit Number。

既然各位数字不超过3，而区间中数字的位数不超过10位，这样可以枚举每一位上的数字（0~3），对于枚举的每个数，若满足在区间[L,R]中且为Rabbit N umber的要求，则进行计数。

（2）源程序。

#include <stdio.h>

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;

}

这篇关于C语言程序设计100例之（57）：3n+1问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程