为什么会出现分段错误 [英] Why it is giving a segmentation fault

问题描述

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

#include <iostream>

int collatz_calculator(int n, int count)
{
    if(n==1)
    {
        count++;
        return count;
    }
    if(n%2==0)
    {
        count++;
        collatz_calculator(n/2, count);
    }

    else{
        count++;
        collatz_calculator(3*n+1, count);
    }

}

int largest_col_seq()
{
    int count=0;
    int max=0;

    int i=999999;
    int largest=0;
    for(i; i>10; i--)
    {
        int num=collatz_calculator(i, count);
        if(num>max)
        {
            max=num;
            largest=i;
        }
    }
    return largest;

}

int main()
{
    std::cout<<largest_col_seq()<<std::endl;
}

我的尝试：



我试过调试，我没有太多的调试经验你能建议如何知道这里有什么问题的方法

What I have tried:

I have tried with debugging, I have not much experience in debugging can you suggest any method of how to know what is the problem here

推荐答案

几乎可以肯定，你正在吹嘘堆栈顶部。

每次用C ++调用函数时，它会占用堆栈上的一些空间 - 当函数返回时会恢复 - 返回地址和参数，以及一些局部变量的更多信息。在64位系统上，使用的最小堆栈空间为8个字节（指向返回位置的指针为64位），但每次调用 collat​​z_calculator <时，还要添加两个整数，另外8个字节。 / code>。



因为你是递归地调用它，这可能就是发生了什么。



您可以从默认的1Mb增加堆栈：



Almost certainly, you are blowing out the top of the stack.
Every time you call a function in C++ it takes an amount of space on the stack - which is recovered when the function returns - for the return address and the parameters, and more for some local variables. On a 64 bit system, the minimum stack space used is 8 bytes (64 bits for a pointer to the return location), but you also add two integers, for another 8 bytes, each time you call collatz_calculator.

Since you are calling it recursively, that's probably what is happening.

You can increase the stack from the default 1Mb:

PROJECT ... Properties ... Configuration Properties ... Linker ... System ... Stack Reserve Size=number of bytes required

但我可能会看一个非递归的解决方案。

but I'd probably look at a non-recursive solution.

有了支持它的编译器，你可以尝试尾递归。

With compilers supporting it, you may try tail recursion.

#include <iostream>

int collatz_calculator(long long n, int count)
{
    if ( n == 1 )
    {
      return ( count + 1 );
    }

    n = ( n % 2) ? 3 * n +1 : n / 2;

    return  collatz_calculator (n, count + 1 );
}

std::pair<int, int> largest_col_seq(int upper_limit)
{
    int max = 0;
    int max_index = 0;
    for(long long i = upper_limit; i>10; i--)
    {
        int num = collatz_calculator(i, 0);
        if(num>max)
        {
            max = num;
            max_index = i;
        }
    }
    return std::make_pair(max_index, max);
}

int main()
{
    auto max_pair = largest_col_seq(999999);
    std::cout << "maximum sequence length at index = " << max_pair.first << ", length = " << max_pair.second << std::endl;
}

使用 g ++ 编译并在第2级进行优化（ -O2 ）输出

compiled with g++ and optimization at level 2 (-O2) outputs

maximum sequence length at index = 837799, length = 525

<我的Linux机器上有
。

on my Linux box.

这篇关于为什么会出现分段错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！