2008-03-07 21:39:09小潘

[C++] Q100

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


Input

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

0< i,j < 1,000,000

Output

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

Sample Input Sample Output

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

BY:http://luckycat.kshs.kh.edu.tw/homework/q100.htm

----------------------------------------------------------

#include
using namespace std;

int main()
{
int n1,n2,r,i,s,a=0,b=0;
while(cin >>n1>>n2)
{
a=0;
b=0;
cout < cout < if(n1>n2)
{r =n1;
n1=n2;
n2=r ;}
for(s=n1;s<=n2;s=s+1)
{for(i=s;i>1;)
{if(i%2==1)
i=3*i+1;
else
i=i/2;
a=a+1; }
if (a>b)
b=a;
a=0;
}
b=b+1;
cout < }
system ("pause");
return 0;
}

解釋日後再打





YK 2008-03-08 23:12:53

不過這樣弄報台倒是有創意
又能造福人群..
哈希望你趕快打到我們教的那邊

肥魚 2008-03-07 23:43:48

你太扯了= =

版主回應
怎樣 有意見嗎 ㄏㄏ 2008-03-08 13:14:29