C/C++ 100 万数组中的 Stackoverflow 错误

Question

我正在使用 VC++ 2010。我编写了一个简短的程序来获取长整型数组中 100 万个数字的 Collat​​z 猜想链，并获取系列中的最高数字。当我尝试运行代码时，出现堆栈溢出异常。

我该如何度过这个难关？

//Might have took un-needed headers
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
using namespace std;


//traverse the array for max term 
long int max_array(long int a[], long int num_elements)
{
    long int i, max=-32000;
    for (i=0; i<num_elements; i++)
    {
        if (a[i]>max)
        {
            max=a[i];
        }
    }
    return(max);
}

//recursive function to calculate and count based on Collatz_conjecture
long int Collatz( long int c1, long int currentcounter)
{
    if ( c1 == 1) return currentcounter;
    if ( c1 % 2 ==0)
    {
        currentcounter++;
        Collatz (c1/2, currentcounter);
    }
    else
    {
        currentcounter++;
        Collatz((3*c1)+1, currentcounter);
    }
}

void main()
{   
    long int  totalcounter[1000000]={0},t1,max;

    for (long  int i=1;i<1000001;i++)
    {
        totalcounter[i]++;
        totalcounter[i]=Collatz(i,totalcounter[i]); 
        printf("Collatz count of no: %li is %li \n",i,totalcounter[i]);
    }
    max = max_array(totalcounter, 1000000);
    printf("The max is %d\n", max);
}

Answer 1

自动变量和递归函数调用都会消耗堆栈内存。您两者都大量使用。

您可以用迭代替换递归（从递归到迭代的方法 ）并且您可以将自动变量（巨型数组）替换为堆分配的变量（使用 new）。

做这两件事应该会对你有所帮助。只要确保当您对 Collat​​z 函数采用迭代方法时，您使用的是堆分配的堆栈，这样您就不会再次遇到相同的问题！

Answer 2

堆栈通常具有固定的、相当小的大小——也许是几兆字节。您正在做的两件事很容易导致过多的堆栈使用：

• 创建一个几兆字节的自动数组
• 调用一个没有递归深度限制的递归函数；除非编译器能够将函数优化为循环，否则每次递归调用都会创建一个新的堆栈帧，因此如果 Collat​​z 路径太长，您将耗尽堆栈。

第一个可以通过使用计数器的动态数组来修复：

std::vector<long int> totalcounter;

或者不存储所有结果，只存储每次迭代后找到的最大结果。

第二个问题可以通过检查编译器是否优化了递归或迭代实现来解决；像这样的东西（未经测试）：（

long int Collatz(long int c1)
{
    long int counter = 0;
    while (c1 != 1) {
        ++counter;
        c1 = (c1 % 2 == 0) ? c1/2 : 3*c1+1;
    }
    return counter;
}

如果您确实决定保留递归实现，那么您需要通过引用传递currentcounter，或者使用每个递归调用的返回值更新它并记住此外，main() 中的数组索引应从 0 到 N-1，而不是从 <代码>1到N。main() 必须返回 int，尽管您可以根据需要省略 return 语句） 。

Answer 3

在计算如此大的数字的 Collat​​z 链时，long int 会溢出。我认为这就是你的递归函数出错的原因。尝试将 c1 参数更改为 64 位类型，例如 long long。

我刚刚对此进行了测试，当您达到值 704511 时，链范围高达 56991483520。顺便说一句，这是 Project Euler 问题 14。

编辑：

将数组 totalcounter[] 的声明移到main() 函数使其成为全局的。对于堆栈上的自动存储而言，它太大了（~4MB）。其他替代方案是动态分配数组或使用 std::vector 。

此处的代码示例。