ACM #100 最佳化

[khoguan (Khoguan Phuann)]

睡了一覺，吃了午飯，又有一些想法，回來還是忍不住給它
踹一踹，共寫了十種以上的版本，終於在速度上獲得顯著的
提昇。時間 0:00.049 剛好第 100 名 XD

以下用了兩種最佳化辦法，一是直接剔除前半段
if (start < end/2) start = end/2; 從一半的地方開始算，
前半部的 cycle length 「應該」都不可能大於後面的。這個
得有數學證明，我的「猜想」還好通過了它的測試。

再來就是查表法，已經算出cycle length的數，就以該數為
索引，其cycle length 為值放到陣列中。在每次迴圈中，
都檢查產生的新數是否在陣列中已放進 cycle length 值，
有的話，便直接加上該值，跳出迴圈。這個陣列表會越來越
完整，後續的數列就會越算越快。不過，動態陣列設得蠻大的，
執行時期會佔用不少記憶體。

// 3n + 1 problem. Time: 0:00.051
#include <iostream>
const int max = 3*1024*1024;
int* vi = new int[max];
int main()
{
    int m, n, max_cyc = 1;
    while (std::cin >> m >> n) {
        int end, start;
        if (m <= n) { end = n; start = m; }
        else {  end = m; start = n; }
        if (start < (end >> 1)) start = (end >> 1);
        for (int k = start; k <= end; ++k) {
            int res = vi[k], tmp = k;
            if (res == 0) {
                ++res;
                while (tmp != 1) {
                    if (tmp % 2) tmp = 3 * tmp + 1;
                    else       tmp >>= 1;
                    if (tmp < max && vi[tmp]) {
                        res += vi[tmp];
                        break;
                    }
                    ++res;
                }
                vi[k] = res;
            }
            if (max_cyc < res) max_cyc = res;
        }
        std::cout << m << ' ' << n << ' ' << max_cyc << '\n';
        max_cyc = 1;
    }
    delete [] vi;
    return 0;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.208.167
※ 編輯: khoguan         來自: 220.130.208.167      (05/29 16:51)
※ 編輯: khoguan         來自: 220.130.208.167      (05/29 20:25)
推 jiahwai:請問要怎看單題排名阿@@?
推 khoguan:從網頁submit程式後就有連結可點