Member 13277493 Ответов: 2

Почему это дает ошибку сегментации

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;
}


Что я уже пробовал:

Я пробовал с отладкой, у меня не так много опыта в отладке, можете ли вы предложить какой-либо метод, как узнать, в чем здесь проблема

2 Ответов

Рейтинг:
8

CPallini

С помощью компиляторов, поддерживающих его, вы можете попробовать хвостовая рекурсия.

#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) выводящий
maximum sequence length at index = 837799, length = 525

на моем Linux-боксе.

Рейтинг:
20

OriginalGriff

Почти наверняка, вы выдуваете верхнюю часть стека.
Каждый раз, когда вы вызываете функцию в C++, она занимает некоторое пространство в стеке - которое восстанавливается при возврате функции - для адреса возврата и параметров, а также для некоторых локальных переменных. В 64-разрядной системе минимальное используемое пространство стека составляет 8 байт (64 бита для указателя на возвращаемое местоположение), но вы также добавляете два целых числа, еще 8 байт, каждый раз, когда вызываете collatz_calculator.

Поскольку вы называете это рекурсивно, это, вероятно, и происходит.

Вы можете увеличить стек с 1 МБ по умолчанию: 

PROJECT ... Properties ... Configuration Properties ... Linker ... System ... Stack Reserve Size=number of bytes required
но я бы, наверное, посмотрел на нерекурсивное решение.