dotcpp-1095: 3n+1 problem

大家好，欢迎来到IT知识分享网。

/*
    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 be 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 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 maxium cycle length over all numbers between i and j, including both endpoints.

Input Description:
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.

Output Description:
For each pair of input integers i and j, output i, j in the same order in which 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.

In:
1 10
100 200
201 210
900 1000

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

*/

#include <stdio.h>

int main(){
    int i,j;
    int n; //n: cycle length (cycle times) for each num
    int mcl; // max cycle length
    int oi, oj; //original i,j;

    while(~scanf("%d%d",&i,&j)){
        oi=i, oj=j; //keep the original value.
        if(i>j){
            int t;
            t=i,i=j,j=t; //swap(i,j) otherwise judge answer error!
        }
        mcl=0; //reset for each pair(i,j)
        for(;i<=j;i++){
            n=1; //will be eventually terminated at 1 (times+1)
            //printf("i=%d\n",i);
            for(int k=i;k!=1;){
                if((k&1)==0){
                    //even
                    k/=2;
                }else{
                    //odd
                    k=3*k+1;
                }
                //generated a new num j
                //printf("%d\n",k);
                n++;
            }
            //putchar('\n');
            mcl=n>mcl?n:mcl;
        }
        printf("%d %d %d\n",oi,oj,mcl);
    }
    return 0;
}

问题描述：求[i,j]范围中的数的3n+1最大循环次数

游戏规则：数k为奇数时k=3k+1；为偶数时k=k/2，这样变化最后都会理念上停止于1 (k=1)

想法：枚举i~j的数，对每个数循环直到其变为1，比较每个数的循环次数，得出该范围中的最大循环次数mcl

貌似测试数据有i>j的情况，所以输入之后保存原始i,j值为oi, oj，需要时交换i, j，同时i自增到j