爲什麼我不能在C++中使用這段代碼？

Question

#include <iostream> 
#include <time.h> 

using namespace std; 

int main() 
{ 
    const int number = 1000000; 

    //Chain Vars------------------- 
    int chainLength = 0; 
    int startingNumber = 0; 
    int chain = 0; 
    int n = 0; 
    //---------------------------- 


    // start Time----------------- 
    clock_t startTime = clock(); 
    double duration; 
    //--------------------------- 


    //Cache----------------------------- 
    int* cache = new int[number+1]; 

    for (int i = 0; i < number+1; i++) 
    { 
     cache[i] = -1; 
    } 
    cache[1] = 1; 
    //--------------------------------- 


    for (int i = 2; i <= 1000000; i++) 
    { 
     n = i; 
     chain = 0; 

     while (n != 1 && n >= i) 
     { 
      chain++; 
      if ((n % 2) == 0) 
      { 
       n = n/2; 
      } 
      else 
      { 
       n = n * 3 + 1; 
      } 
     } 

     //Store the chain length in cache 
     cache[i] = chain + cache[n]; 
     //------------------------------- 

     if (cache[i] > chainLength) 
     { 
      chainLength = cache[i]; 
      startingNumber = i; 
     } 
    } 


    //----------------------------------------------------------------------------------------------- 
    duration = ((clock() - startTime)/(double)CLOCKS_PER_SEC); 
    cout << "Starting Number is: " << startingNumber << " with a length of: " << chainLength << endl; 
    cout << "Duration = " << duration << endl; 
    //----------------------------------------------------------------------------------------------- 

    getchar(); 

    return 0; 
} 

所以我的錯誤發生在第54行，並說我沒有權限訪問這個內存。在C＃中相同的代碼工作得很好。

Answer 1

在你for循環，你這樣做：

for (int i = 2; i <= 1000000; i++) 
{ 
    n = i; 
    chain = 0; 

    while (n != 1 && n >= i) 
    { 
     chain++; 
     if ((n % 2) == 0) 
     { 
      n = n/2; 
     } 
     else 
     { 
      n = n * 3 + 1; 
     } 
    } 

    //Store the chain length in cache 
    cache[i] = chain + cache[n]; 
    //------------------------------- 

    if (cache[i] > chainLength) 
    { 
     chainLength = cache[i]; 
     startingNumber = i; 
    } 
} 

在某些時候while (n != 1 && n >= i)最有可能與n大於1000000結束。然後你會訪問cache（當你做cache[n]）出界（它是[0:1000000]）。

在while循環之前加std::cout << "i is " << i << std::endl;。之後添加 std::cout << "n is " << n << std::endl;。運行程序，你會得到（幾秒鐘後）：

... 
i is 113381 
n is 85036 
i is 113382 
n is 56691 
i is 113383 
n is -1812855948 
Erreur de segmentation (core dumped) 

你在這裏。現在，您可以使用調試器，識別錯誤，修復錯誤（最有可能重做您的循環），並使其工作！ ;-)

提示：由於n變爲負值，可能達到了int的最大值...然後只需使用類型（如long long int或uint64_t）。然後，你很可能不會有任何溢出（除非你讓number穢物）。

C＃不會像C++那樣管理內存。如果在這裏訪問數組超出範圍（或者，如上所述，您剛剛獲得幸運），則可能不會出現錯誤。我不熟悉C＃。訪問數組必須總是被避免，它可能有不確定的行爲（可能導致或不能導致崩潰）。

Answer 2

運行和調試程序後：

//Store the chain length in cache 
    cache[i] = chain + cache[n]; 

n似乎是0x93f20374（在i是113383），這是負-1812855948，或將利好2482111348 - 但溢出成爲-1812855948。

while (n != 1 && n >= i) 

環路負n結束，導致cache[n]崩潰。

Answer 3

像jpo38說：

提示：當n爲負，也許它達到INT的最大值...使用調試器來驗證，只需做，while循環之前：

這是我的問題，然後我將「int n」改爲「long long n」，因爲「long n」仍然很小，現在它給了我正確的答案。謝謝大家:)這麼簡單，但有時它是你看不到的小事。