分段错误 C++(数组太大?) [英] Segmentation Fault C++ (array too large?)

问题描述

我正在研究 Project Euler 问题 14，我需要在其中找到最长的 collat​​z 序列低于 1,000,000.我提出了一种适用于较小数字(例如 100)的算法，它将 1 到 100 的每个 collat​​z 数字存储到一个数组中，并使用该数组作为参考来加快计算更大数字的速度.我的代码如下:

I'm working on the Project Euler Problem 14, where I need to find the longest collatz sequence under 1,000,000. I've come up with an algorithm that works for smaller numbers (say, 100) that stores each collatz number from 1 - 100 into an array and uses that array as a reference to speed up the computations for higher numbers. My code is as follows:

#include <iostream>
using namespace std;

long even(long n){ //the even-collatz function
    n=n/2;
    return n;
}

long odd(long n){ //the odd collatz function
    n=3*n+1;
    return n;
}

int main(){
    long  x, c=0, y[1000000]; // x= the number we are finding the collatz number of, c a counter that keeps track of how many steps we've taken in the sequence, y is an array to store the collatz numbers.

    for (x=1; x<1000000; x++){ //iterates from x=1 to 1 million
            long a = x;     //sets a number a equal to the number we are currently trying to find the collatz number of
            long b = a;     
            c=0;                    //intializes counter at 0 
            while (a!=0){           //loops infinitely; the only way to exit is through a break.
                    if (a%2==0){    // detects if the number is even
                            a=even(a);      //applies the even-collatz function if so; sets x=x/2
                            c=c+1;
                            if (y[a]!=0){   // checks if the collatz number of x is already discovered
                                    y[b]=c+y[a]; //adds the current number of steps to the collatz number of x and 
                                    break;  //exits the while loop
                            }

                    }
                    else if (a==1){         //checks if the new x is equal to one and
                            y[b]=c;         //if it is, it writes the current value of c to y[b] and
                            break;          // exits the loop
                    }
                    else if (a%2==1){       //same as the "even" block, except for odd numbers 

                            a=odd(a);
                            c=c+1;
                            if( y[a]!=0){
                                    y[b]=c+y[a];
                                    break;
                            }

                    }
            //this is the end of the while loop; we've applied the collatz function as many times as we've needed to to x, and incremented the counter each time
            }
  }

    long z;
    for (int n=0;n!=100;n++){
            if (y[n+1]>y[n]){
                    z=y[n+1];
            }
    }
    cout << z << "
";


}

我遇到的问题是在 for 循环中 x=1818 之后出现段错误.通过调试，我发现segfault发生的速度取决于数组y的大小，所以我假设数组太大了.根据我对段错误的(基本)理解，我认为我只是在访问不允许"的内存.我有什么办法可以规避这个问题，还是我应该开始努力寻找解决这个问题的另一种方法?我在 Ubuntu studio 上使用 g++ 进行编译.

The issue I'm having is that I get a segfault after x=1818 in the for loop. Through debugging, I've found that how quickly the segfault occurs depends on the size of array y, so I'm assuming that the array is just too big. From my (basic) understanding of segfaults, I think I'm just accessing memory that I'm "not allowed". Is there any way for me to circumvent this, or should I just start working towards another solution to this problem? I'm compiling using g++ on Ubuntu studio.

推荐答案

这个数组可能对于您系统的默认堆栈大小来说太大了；最简单的解决方法是将其定义更改为:

This array is probably too big for your system's default stack size; the simplest fix is to change its definition to:

std::vector<long> y(1000000);

其他一切都可以保持不变.您可以稍后在循环中使用 y.size() 而不是幻数 1000000.

and everything else can stay the same. You could use y.size() instead of the magic number 1000000 later in your loop.

这篇关于分段错误 C++(数组太大?)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！