c039. 00100 - The 3n + 1 problem
Tags :
Accepted rate : 5293人/5726人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-15 02:29

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
1 10
10 1
100 200
201 210
900 1000
Sample Output #1
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
* 中文翻譯:Lucky 貓
Tags:
出處:
UVa100

Status Forum 排行

ID User Problem Subject Hit Post Date
34094 zxc123asd66@ ... (毛喬) c039
2424 2023-02-28 04:38
32918 wmouo (crazypanda) c039
1144 2022-11-17 08:55
32213 xig1517 (超級小蛇) c039
2451 2022-09-21 23:36
31717 a302854888@g ... (小麥) c039
記憶化DP
1369 2022-08-15 23:17
31161 11011102@gm. ... (溫政瑜) c039
想法
1668 2022-07-16 16:29