考慮以下的演算法:
- 輸入 N
- 印出 N
- 如果 N = 1 結束
- 如果 N 是奇數 那麼 N = 3*N + 1
- 否則 N = N / 2
- 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 |
解題思路
本題可以用建立 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