高中生程式解題系統:c039: 00100 - The 3n + 1 problem

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=c039

程式碼是用迴圈一直更新 num 的數值,直到 num == 1為止。
但可用動態規劃加速。

while(num != 1)
{
    num = (num % 2 == 0 ? num / 2: (num*3) + 1);
    cycleLength++;
}

程式碼:
#include <iostream>

using namespace std;

int get_cycle_length(int num);

int main(void)
{
    int i, j, k, start, end;
    int maximum = 1;
    int cycleLength;

    while( cin >> i >> j )
    {
        maximum = 1;
        start = i;
        end = j;
        if( i > j )  // ensure "start" is less than "end"
        {
            start = j;
            end = i;
        }

        for(k = start; k <= end; k++)
        {
            cycleLength = get_cycle_length(k);
            if(maximum < cycleLength)
                maximum = cycleLength;
        }

        cout << i << " " << j << " " << maximum << endl;
    }

    return 0;
}

int get_cycle_length(int num)
{
    int cycleLength = 1;
    while(num != 1)
    {
        num = (num % 2 == 0 ? num / 2: (num*3) + 1);
        cycleLength++;
    }

    return cycleLength;
}

沒有留言: