回分類題庫
d148: The 3n + 1 problem
出處:ACM100

Difficulity : 1
Accepted : 314 Times | Submit :816 Times | Clicks : 4805
Accepted : 229 Users | Submit : 248 Users | Accepted rate : 92%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2010-02-04 00:11

Content :

考慮以下的演算法:

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(包含i,j)之間的數所產生的數列中最大的 cycle length 是多少。

Input :

輸入可能包含了好幾列測試資料,每一列有一對整數資料 i,j 。 0< i,j < 1,000,000

Output :

對每一對輸入 i , j 你應該要輸出 i, j 和介於 i, j 之間的數所產生的數列中最大的 cycle length。

Sample Input :

1 10
100 200
201 210
900 1000

Sample Output :

1 10 20
100 200 125
201 210 89
900 1000 174

Hint :

* 中文翻譯:Lucky 貓 英 中

Author :

ACM100

  Solve it!   Status Forum (2)

C++
C
JAVA
24303. x1213 (6 ms , 742KB)
22531. henryokc (18 ms , 2304KB)
23924. star1327p (22 ms , 2190KB)
50101. abc29298727 (32 ms , 4140KB)
50098. abc29298727 (32 ms , 4282KB)
50080. acc2see (24 ms , 630KB)
46188. acc2see (26 ms , 4122KB)
46190. acc2see (28 ms , 618KB)
30809. ej04xjp6 (36 ms , 4170KB)
20783. nipa (70 ms , 3016KB)
76295. ag100j (222 ms , 18412KB)
76294. ag100j (222 ms , 10696KB)
70832. nwgs524513cja (248 ms , 6008KB)
52899. nwgs524513cja (282 ms , 6064KB)
52502. nwgs524513cja (296 ms , 6570KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡