UVA 3n + 1（prob 100）什麼是我的C++程序錯誤

Question

我試着解決3n + 1問題（UVA 100），這裏是我的代碼，但根據UVA在線評判我的程序給出了錯誤的答案，我的代碼通過了我能想到的所有測試案例，但無法檢測到什麼是錯誤的，請幫我找到錯誤。

#include <iostream> 
#include <algorithm> 
#include <vector> 

using namespace std; 

vector<int> Num;// for Memoization till 1000000 

int counter(long int j) { 
    if(j > 1000000) { 
     if(j%2 == 1) return(counter((3*j+1)>>1)+2); 
     else return(counter(j>>1)+1); 
    } 
    else { 
     if(Num[j] != 0) return Num[j]; 
     if(j%2 == 1) Num[j] = counter(3*j+1)+1; 
     else Num[j] = counter(j>>1)+1; 
    } 
} 

int main() { 
    Num.resize(1000001);//auto initilizes the vector with 0 
    Num[1] = 1; // set the counter for n = 1 as 1; 
    int X,Y; 
    while (cin >> X >> Y) { 
     int x = X , y = Y, mxl = 0; 
     if(X > Y) swap(X,Y); 
     for (long int j = Y; j >= X; --j) { 
      if(Num[j] == 0) counter(j); 
      if(mxl < Num[j]) mxl = Num[j]; 
     } 
     cout << x << " " << y << " " << mxl << endl; 
    } 
return 0; 
} 

Answer 1

int counter(long int j) { 
    if(j > 1000000) { 
     if(j%2 == 1) return(counter((3*j+1)>>1)+2); 
     else return(counter(j>>1)+1); 
    } 
    else { 
     if(Num[j] != 0) return Num[j]; 
     if(j%2 == 1) Num[j] = counter(3*j+1)+1; 
     else Num[j] = counter(j>>1)+1; 
    } 
} 

在哪裏的情況下你的回報值，其中Num[j] == 0在這最後的代碼段（外else）？

你設置Num[j]到正確的值，但從來沒有返回它。

我懷疑你是後是一樣的東西（擺脫那些完全沒有必要if..return..else結構，以及）：

int counter(long int j) { 
    if(j > 1000000) { 
     if(j%2 == 1) 
      return(counter((3*j+1)>>1)+2); 
     return(counter(j>>1)+1); 
    } 
    if(Num[j] != 0) 
     return Num[j]; 
    if(j%2 == 1) 
     Num[j] = counter(3*j+1)+1; 
    else 
     Num[j] = counter(j>>1)+1; 

    return Num[j]; // This is important. 
} 

---

我應該提及，但是，遞歸可能不是這裏使用的理想工具。首先，序列可能很長的可能性意味着在獲得解決方案之前，可能會耗盡堆棧空間。

其次，遞歸調用是而不是沒有成本。搜索解決方案時，可能需要花費大量時間設置和拆除堆棧幀。

我傾向於選擇迭代解決方案來避免這些潛在的問題。