为什么我不能在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”仍然很小，现在它给了我正确的答案。谢谢大家:)这么简单，但有时它是你看不到的小事。