3n+1問題 用c語言實作

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 = 1for every integer n.Still, the conjectureholds for all integers up to at least 1, 000, 000.

For an input n, the cycle-length of n isthe number of numbers generated up to andincluding 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 cyclelength over all numbers between i and j, including both endpoints.

Input

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

Output

For each pair of input integers i and j, output i, j in thesame order in which they appeared in the input and thenthe 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 oneline and with one line of output for each line of input.

Sample Input

1 10
100 200
201 210
900 1000
      

Sample Output

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

// [問題描述]

// 考慮如下的序列生成算法：從整數 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。這個猜想對于至少 1 000 000

// 内的整數都是正确的。

//

// 對于給定的 n，該序列的元素（包括 1）個數被稱為 n 的循環節長度。在上述例子中，22 的循環節長度

// 為 16。輸入兩個數 i 和 j，你的任務是計算 i 到 j（包含 i 和 j）之間的整數中，循環節長度的最大

// 值。

//

// [輸入]

// 輸入每行包含兩個整數 i 和 j。所有整數大于 0，小于 1 000 000。

//

// [輸出]

// 對于每對整數 i 和 j，按原來的順序輸出 i 和 j，然後輸出二者之間的整數中的最大循環節長度。這三

// 個整數應該用單個空格隔開，且在同一行輸出。對于讀入的每一組資料，在輸出中應位于單獨的一行。

//

// [樣例輸入]

// 1 10

// 100 200

// 201 210

// 900 1000

//

// [樣例輸出]

// 1 10 20

// 100 200 125

// 201 210 89

// 900 1000 174

//

我一開始在programming Challenges這個網站上送出總是報錯,我的正确解法如下：

#include <stdio.h>

#define MAX 200000000

int cache[MAX];

int findOneDataLength(long long data) {
    if (data == 1) {
        return 1;
    }
    if (data & 1) {
        data += (data << 1) + 1;
    } else {
        data >>= 1;
    }
    if (data < MAX) {
        if (cache[data]) {
            return cache[data];
        }
        cache[data] = findOneDataLength(data) + 1;
        return cache[data];
    } else {
        return findOneDataLength(data) + 1;
    }

}

int find3nplus1MaxLength(int data1, int data2) {
    int maxLength = -1;
    for (int j = data1; j <= data2; ++j) {
        int data = findOneDataLength(j);
        if (maxLength < data) {
            maxLength = data;
        }
    }
    return maxLength;
}

int main() {
    int data1, data2;
    while (scanf("%d %d", &data1, &data2) != EOF) {
        int temp1 = data1;
        int temp2 = data2;
        if (data1 > data2) {
            data1 = data1 ^ data2;
            data2 = data1 ^ data2;
            data1 = data1 ^ data2;

        }
        int length = find3nplus1MaxLength(data1, data2);
        printf("%d %d %d\n", temp1, temp2, length);
    }
    return 0;


}
      

總結：

  1.在while循環的時候，我一開始的寫法是 while(1)，導緻Time limit exceeded；後來判斷scanf函數的傳回值，就可以了

   2.如果輸入的是（10，1），（20，1），這種第一個輸入的資料比第二個大，也會導緻wrong answer，需要調換兩個資料的位置

  3.如果不使用緩存也會導緻 Time limit exceeded