ACM题目1095: The 3n + 1 problem

题目描述

Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

输入

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

输出

For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.

样例输入

样例输出

1 10 20
100 200 125
201 210 89
900 1000 174
思路：
有了初始数字i和循环次数j
就可以用if判断来得到最后的i值
我自己编写的程序显示答案错误
错误代码：

#include<stdio.h>
int main()
{
int i,j;//i用来保存起始的数字，j用来保存遍历的次数
scanf("%d %d",&i &j);
int m;//m用来保存更新后的i值
while(j--)
{
if(i%2==0)
{
i=i/2;
}
if(i%2!=0)
{
i=i*3+1;
}
}
m=i;
printf("%d %d %d",i j m);
return 0;

}

错误提示：

ACM题目1095: The 3n + 1 problem

错误原因：

当i执行一定次数之后数字变为1程序即终止，但是给了i和j的值不能确定遍历j次后程序是否已经终止

所以要对i和j的值进行大小的判断,忽略判断的话就会导致有一部分特殊情况没有考虑到

正确代码：

#include<stdio.h>

int dfs(int a)
{
   int i=1;
   while(a!=1)
   {
       if(a%2==0)
       {
           i++;
           a/=2;
       }
       else
       {
           i++;
           a=(a*3)+1;
       }
   }
   return i;

}
int  main()
{
    
    int i,j,t;//t作为临时变量用来判断i j大小
    int num;//num用来计算比较的次数
    int k;
    
    while(scanf("%d%d",&i,&j)!=EOF)
    {
        printf("%d %d ",i,j);
        if(i>j)
        {
           
            t=i;
            i=j;
            j=t;
        }
	    int max=0;//循环长度初始化长度
	    for(k=i;k<=j;k++)
	    {
	        num=dfs(k);
	        if(num>max)
	        {
	            max=num;
	        }
	        
	    }
	    printf("%d
",max);
	}
    return 0;
}

反思：

考虑问题要充分一些

另外敲代码的时候要仔细一些把每一个字母都敲正确，防止出现一些因为粗心而出现的不该犯的错误

ACM题目1095: The 3n + 1 problem

相关推荐