Задача

1/11

Числа Фибоначчи: Мемоизация рекурсии (C++)

Теория Нажмите, чтобы прочитать/скрыть

Динамическое программирование

Рассмотрим рекурсивное решение задачи про последовательность чисел Фибоначчи.
 
C++
int fibonacci(int n) 
{
    if (n <= 0) 
    {
        return 0;
    } 
    else if (n == 1) 
    {
        return 1;
    } 
    else 
    {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
 
Python
def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


Данная реализация функции fibonacci  работает, но имеет недостатки, связанные с экспоненциальной сложностью и дублированием вычислений.

Для более эффективного решения задачи о числах Фибоначчи, лучше использовать мемоизацию или динамическое программирование, чтобы избежать повторных вычислений и снизить сложность алгоритма до линейной (O(n)).

 
Динамическое программирование (DP) - это метод решения сложных задач, который состоит в разбиении задачи на более мелкие подзадачи и решении их, а затем комбинировании результатов для получения решения исходной задачи. DP широко применяется в информатике, математике, экономике и других областях для оптимизации и поиска оптимальных решений.


В динамическом программировании (DP) существует два основных метода решения задач: сверху вниз (Top-Down) и снизу вверх (Bottom-Up).  Каждый из них имеет свои преимущества и подходит для разных типов задач. Эти два метода можно использовать для решения широкого спектра задач, включая вычисление оптимальных путей, нахождение максимальных или минимальных значений, управление ресурсами и др. Выбор метода зависит от конкретной задачи, структуры данных и потребностей в оптимизации производительности.
 

Метод сверху-вниз

Метод сверху вниз (Top-Down) в динамическом программировании (ДП) - это подход, который начинает решать задачу с самых больших, общих исходных данных и разбивает ее на более мелкие подзадачи. Затем он решает каждую подзадачу рекурсивно, используя мемоизацию (запоминание результатов решения подзадач) для избегания повторных вычислений. Этот метод также называется "методом с кэшированием" или "методом с сохранением результатов".

Основные шаги метода сверху вниз в ДП:

  1. Определение базовых случаев: Определите базовые случаи, которые можно легко решить без дополнительных вычислений. Эти случаи будут останавливать рекурсивные вызовы.

  2. Рекурсивное разбиение задачи: Разбейте основную задачу на более мелкие подзадачи, которые можно решить рекурсивно. Обычно это делается путем выделения параметра, который будет уменьшаться с каждым рекурсивным вызовом.

  3. Использование мемоизации: Для каждой подзадачи сохраняйте результат ее решения в памяти (например, в массиве или словаре), чтобы избежать повторных вычислений при повторных вызовах.

  4. Сбор результатов: Верните результат решения основной задачи, используя результаты решенных подзадач.

Метод сверху вниз позволяет эффективно решать задачи, которые имеют перекрывающиеся подзадачи, и снижать сложность алгоритма до более оптимальной, чем при обычной рекурсии.


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

Использование данного метода для решения задачи про числа Фибоначчи расcмотрено в практическом примере. 

Задача

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).
 

Примеры
Входные данные Выходные данные
1 2 1
2 3 2
3 4 3