C/C++教程

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个幸运数字。

输入样例

3

4

7

输出样例

8

16

3

         (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 <= 1018)。

输出

对于每个测试用例,输出信息为“Case #X:P”,其中X表示第X组测试用例(X从1开始),P表示[A,B]之间Good Numbers的个数。

输入样例

2

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≤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)< <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问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!