3n+1數鏈問題
Time Limit: 1000ms Memory limit: 65536K 有疑問？點這裡^_^
題目描述
在計算機科學上，有很多類似的問題是無法解決的，我們稱之為不可解決問題。然而，在很多情況下我們並不知道哪一類問題可以解決，哪一類問題不可解決。現在我們就有這樣一個問題，問題如下：
（1）輸入一個正整數n；
（2）把n顯示出來；
（3）如果n=1則結束；
（4）如果n是奇數則n變為3*n+1，否則變為n/2；
（5）轉入第（2）步。
例如對於輸入的正整數22，應該有如下數列被顯示出來：
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
我們推測：對於任意一個正整數，經過以上算法最終會推到1。盡管這個算法很簡單，但我們仍然無法確定我們的推斷是否正確。不過好在我們有計算機，我們驗證了對於小於1000000的正整數都滿足以上推斷。
對於給定的正整數n，我們把顯示出來的數的個數定義為n的鏈長，例如22的鏈長為16。
你的任務是編寫一個程序，對於任意一對正整數i和j，給出i與j之間的最大鏈長，當然這個最長鏈長是由i與j之間的其中一個正整數產生的。我們這裡的i和j即包括i也包括j。
輸入
輸入兩個正整數i、j，i和j之間以一個空格隔開。0 < i <= j < 10000。
輸出
輸出數據只有一行，即為i與j之間的最長鏈長。
示例輸入
1 10
示例輸出
20
#include
int getLinkLen(int n)
{
if (n == 1) return 1;
return n&1 ? getLinkLen(n*3+1)+1 : getLinkLen(n/2)+1;
}
int main()
{
int x, y, i, t, max = 0;
scanf("%d %d", &x, &y);
for (i=x; i<=y; i++){
t = getLinkLen(i);
if (t > max) max = t;
}
printf("%d\n", max);
return 0;
}
