Ошибка сегментации (сбрасывается ядро) при выполнении кода для N> = 10 ^ 7 - PullRequest
Новая
       10

Ошибка сегментации (сбрасывается ядро) при выполнении кода для N> = 10 ^ 7

1 голос
/ 17 мая 2019

Я пытаюсь написать код для проблемы Байтландские золотые монеты из codeChef. Код отлично работает для n < 10^7, но дает ошибку сегментации для более высоких значений. Я искал типы данных, которые могли бы содержать большие числа , но это тоже не работало. Я, конечно, думаю, что в моем коде нет проблем, но, возможно, дерево рекурсии становится слишком большим для обработки компилятором. Вот код. 

#include <bits/stdc++.h>

using namespace std;

#define lli long long int

lli divide(lli n, lli dp[])
{
    lli ans = 0;

    if (n == 0)
        return 0;

    if (dp[n] != 0)
        return dp[n];

    lli m1 = floor(divide(n / 2, dp));
    lli m2 = floor(divide(n / 3, dp));
    lli m3 = floor(divide(n / 4, dp));
    lli sum = m1 + m2 + m3;
    ans = max(sum, n);
    dp[n] = ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        lli n;
        cin >> n;
        lli dp[n + 1] = { 0 };
        lli ans = divide(n, dp);
        cout << ans << endl;
    }
}

Ответы [ 2 ]

3 голосов
/ 17 мая 2019

Я думаю, что в этой строке большой массив выделен в стеке: 

lli dp[n + 1] = {0};

Это, вероятно, причина segfault.Вы можете изменить его на std::vector.Например: 

std::vector<lli> dp(n + 1, 0);

В качестве альтернативы вы можете сделать его статическим или выделить его с помощью new[] (возможно, только один раз для всех тестов, чтобы минимизировать накладные расходы, и в этом вы должны помнить, чтобы очистить егоправильно с delete[]).

2 голосов
/ 17 мая 2019

Как упоминалось @sbarzowski, когда вы делаете 

lli dp[n+1] = {0}

, вы запрашиваете выделение памяти в стеке.Выделение памяти в стеке, хотя приводит к более быстрому времени доступа, но приводит к нехватке памяти.Вместо этого используйте выделение памяти в куче.Для этого вы можете использовать оператор new.Для подробного объяснения стека и распределения кучи проверьте: https://www.geeksforgeeks.org/stack-vs-heap-memory-allocation/

Кроме того, рекомендуется использовать std::vector или std::array при работе с большим количеством элементов, которые должны храниться вместе.Список литературы: Вектор против массива для большого количества элементов?

...