Ошибка сегментации при попытке Project Euler # 14 - PullRequest
Новая
       16

Ошибка сегментации при попытке Project Euler # 14

2 голосов
/ 11 февраля 2020

Это проблема: https://projecteuler.net/problem=14

Пожалуйста, не дайте мне решение. Просто скажи мне, где я иду не так. Это мой код: 

#include <stdio.h>

int Collatz_Count(int n);

int cache [10000000] = {0};
int main(void)
{
    int n, answer, count = 0;

    for (n = 1; n < 1000000; ++n)
    {
        if (Collatz_Count(n) > count)
        {
            count = Collatz_Count(n);
            answer = n;
        }
    }

    printf("The number is %d and the count is %d\n", answer, count);

    return 0;
}

int Collatz_Count(int n)
{
    if (n == 1)
    {
        return 0;
    }

    if (n < 1000000)
    {
        if (cache[n] != 0)
        {
            return cache[n];
        }
        else
        {
            if ((n % 2) == 0)
            {
                cache[n] = (1 + Collatz_Count(n / 2));
            }
            else
            {
                cache[n] = (1 + Collatz_Count(3 * n + 1));
            }

            return cache[n];
        }
    }
    else
    {
        if ((n % 2) == 0)
        {
            return (1 + Collatz_Count(n / 2));
        }
        else
        {
            return (1 + Collatz_Count(3 * n + 1));
        }
    }

}

Я получаю «Ошибка сегментации (сбрасывается ядро)» при выполнении программы. Я только что изучил запоминание и хотел применить его.

Я попытался установить 'n <100000', и он работал правильно, но не тогда, когда 'n <1000000'. </p>

Мне очень жаль за отсутствие комментариев.

1 Ответ

2 голосов
/ 11 февраля 2020

Я запустил программу, используя GDB. Проблема заключается в том, что аргумент Collatz_Count в конечном итоге превышает допустимый диапазон целых чисел, что является неопределенным поведением.

Многие компиляторы переходят на отрицательные числа, когда происходит такое переполнение, и затем пытаются получить доступ к cache с отрицательным индексом дает ошибку сегментации.

Замена int на long long должна исправить проблему.

...