ZeroJudge D712: The 3n + 1 problem

考慮以下的演算法：

  1. 輸入 N
  2. 印出 N
  3. 如果 N = 1 結束
  4. 如果 N 是奇數 那麼 N = 3＊N + 1
  5. 否則 N = N / 2
  6. GOTO 2

例如：輸入 22，得到的數列 –> 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

據推測此演算法對任何整數而言會終止 (當列印出 1 的時候)。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的 N ( 0 < N <= 1,000,000 ) 來說，以上的推測已經被驗證是正確的。

給一個輸入 N，透過以上的演算法我們可以得到一個數列 (1 作為結尾）。此數列的長度稱為 N 的 Cycle Length。上面提到的例子：22 的 Cycle Length 為 16.

問題來了：對任 2 個整數 i 和 j 我們想要知道介於 i 和 j (含) 之間的數所產生的數列中最大的 Cycle Length 是多少。

範例測資

範例輸入範例輸出
EOF 輸入，每筆測資有一對整數資料 i 和 j 。 (0 < i, j <= 1,000,000)輸出 i 和 j 還有「從 i 到 j 的 3n+1 Problem 的最長總 Cycle Length」
1 10
100 200
201 210
900 1000		1 10 20
100 200 125
201 210 89
900 1000 174
ZeroJudge D712 範例測資

解題思路

本題可以用建立 1 到 1000000 的表來做，但是要跑 1000000 次的 3N+1 函式還是很耗時，可以發現當 N 可以被 2 整除時，他的 3N+1 函式回傳值就會是 N/2 的回傳值再加 1，利用這點只需要判斷 1 到 1000000 中的「奇數」就好了。

但是這樣子還是不夠快，所以除了將 3N+1 函式的回傳值進行建表，還需要進行 i 到 j 的最大值的線段數建立，最後再建立一個 Query 的函式將 i 到 j 的最大值進行計算，這樣子就不會TLE了。另外，測資中有可能 i 會大於 j，這種情況就需要 Swap(i, j)，但是輸出的時候還是要按照原有的順序進行輸出，這點需注意。

範例程式碼－ZeroJudge D712: The 3n + 1 problem

#include <iostream>
using namespace std;

int MAP[1000005] = {};
int a, b, maxx = -1;
int tree[3000000] = {};

void initial() {
    for(int i = 2; i < 1000001; i++)
    {
        long long int c = i;
        int count = 1;
        if(i % 2 == 0)
        {
            MAP[i] = MAP[i>>1]+1;
            continue;
        }
        while(c >= i)
        {
            if(c % 2)
            {
                c = c*3+1;
                c >>= 1;
                count+=2;
            }
            else
            {
                c = c>>1;
                count++;
            }
        }
        MAP[i] = count + MAP[c]-1;
    }
}

void build(int l, int r, int index)
{
    if (l == r)
    {
        tree[index] = MAP[l];
        return;
    }
    build(l, (l+r)/2, (2*index)+1);
    build(((l+r)/2)+1, r, (2*index)+2);
    tree[index] = max(tree[(index*2)+1], tree[(index*2)+2]);
    return;
}

void query (int l, int r, int index)
{
    if (a <= l && r <= b)
    {
        maxx = max(maxx, tree[index]);
        return;
    }
    if (l == r)
    {
        maxx = max(maxx, tree[index]);
        return;
    }
    int half = (l+r)/2;
    if (a <= half)
    {
        query(l, half, (index*2)+1);
    }
    if (b > half) query (half+1, r, (index*2)+2);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    MAP[1] = 1;
    initial();
    build(1, 1000000, 0);
    while (cin >> a >> b)
    {
        int c = a;
        int d = b;
        if (a > b) swap(a, b);
        maxx = -1;
        query(1, 1000000, 0);
        cout << c << " " << d << " " << maxx << "\n";
    }
}

//ZeroJudge D712
//Dr. SeanXD
標籤

相關文章

發佈留言