Как можно развернуть данную рекурсию?

107

20 августа 2019, 06:40

Задача в том, чтобы быстро находить n-тый член последовательности Голомба.

Но вариант находить последовательность полностью с помощью ДП и брать dp[n] не подходит, так как затратит больше положенных 255 Мб, т. к. n <= 2e9.

А рекурсивное решение неподходит, т. к. рекурсия выходит слишком глубокой. Возможное решение проблемы - разворот рекурсии.

Как это можно реализовать?

P.s.: Так же на нахождение элемента последовательности даётся порядка одной секунды на не самом сильном железе.

findGolomb(int n) {
    if(n == 1) return 1;
    return 1 + findGolomb(n -
               findGolomb(findGolomb(n - 1)));
}

Answer 1

Получилось!

2е9-ый элемент на моей машине находится за 0.024 сек.

#include <cstdlib>
#include <iostream>
#include <vector>
struct Elem
{
    int index = 3;
    int value = 2;
};
int FindGolombImpl(Elem *data, int size, int n)
{
    if (n <= 1)
        return 1;
    if (size <= 0)
    {
        std::cout << "Not enough storage!\n";
        std::exit(1);
    }
    while (data->index < n)
    {
        data->value++;
        data->index += FindGolombImpl(data+1, size-1, data->value);
    }
    return data->value;
}
int FindGolomb(int n)
{
    // Минимальное значение, которого хватает для вычисления 2e9-ого члена, подобрано методом тыка.
    constexpr int storage_size = 8; 
    Elem storage[storage_size];
    return FindGolombImpl(storage, storage_size, n);
}
int main()
{
    std::cout << FindGolomb(2000000000) << '\n';
}