The 3n + 1 problem(題目鏈接)
思路
-
思路比較簡單，遞歸加存儲
- 網(wǎng)上有人說孩哑，不用存儲也能過（沒有試）
- 但是需要注意n的范圍栓霜，否則數(shù)組會越界
- 因為3*n+1的結果可能比3000000還要大（最開始一直沒有想通）
- 所以超出1000000的數(shù)，就不存儲
輸入的i j不一定是從小到大
代碼
#include <iostream>
using namespace std;
//存儲n對應的循環(huán)長度
int tab[1000000+10];
//返回n對應的循環(huán)長度
int f(int n){
if(n == 1) //當n為 1横蜒，遞歸出口
return 1; //循環(huán)長度為 1
int tmp; //計算出的臨時變量
if(n > 1000000 || tab[n] == 0){ //超出表的范圍或還沒有計算
if(n % 2 == 1){ //奇數(shù)
tmp = f(3*n + 1) + 1; //循環(huán)長度加 1
}else{ //偶數(shù)
tmp = f(n / 2) + 1; //循環(huán)長度也加 1
}
if(n <= 1000000){ //在表的范圍內(nèi)
tab[n] = tmp; //記錄在表中
}
return tmp; //返回循環(huán)長度
}
return tab[n]; //已經(jīng)在表中時胳蛮，直接返回
}
int main(){
int i, j, t1, t2; //
while(cin >> t1 >> t2){ //t1 t2保存輸入順序
if(t1 > t2){ //交換t1 t2的位置
i = t2; //讓 i 小于 j
j = t1;
}else{
i = t1;
j = t2;
}
int max = f(j); //max先賦值為其中的一個值
for(int k = i; k < j; k++){ //循環(huán)整個范圍（j已經(jīng)賦值給max）
if(f(k) > max){
max = f(k); //記錄最大值
}
}
cout << t1 << " " << t2 << " " << max << endl;
}
return 0;
}
總結
- 讀題目不太認真，沒有看到輸出的順序跟輸入要一致
- 默認i j從小到大
- 使用數(shù)組時丛晌，沒有考慮到訪問越界的情況
