Динамическое программирование. Метод "снизу-вверх"
Метод "снизу вверх" (Bottom-Up) в динамическом программировании - это стратегия решения задач, которая начинается с решения наименьших подзадач и постепенно комбинирует их результаты для решения более крупной задачи. Этот метод избегает рекурсии и обычно использует циклы для эффективной обработки задачи.
Задача
Предположим, нам нужно вычислить n-ое число Фибоначчи, где n - это положительное целое число.
-
Инициализация: Создадим массив для хранения результатов вычислений (назовем его fib) и установим начальные значения для чисел Фибоначчи: fib[0] = 0 и fib[1] = 1.
-
Итерация: Начнем цикл с i = 2 и продолжим до i = n. На каждой итерации мы будем вычислять fib[i] на основе fib[i-1] и fib[i-2]:
for i from 2 to n: fib[i] = fib[i-1] + fib[i-2]
-
Результат: По завершении цикла fib[n] будет содержать n-ое число Фибоначчи.
Метод снизу вверх эффективен, так как избегает дублирования вычислений и имеет линейную сложность по времени. Вычисления производятся с самой маленькой подзадачи, решение которой сохраняется в массиве. Для решение более крупных подзадач используются решения более мелких подзадач.
Например, для n = 6, вычисление будет следующим образом:
fib[2] = fib[1] + fib[0] = 1 + 0 = 1fib[3] = fib[2] + fib[1] = 1 + 1 = 2fib[4] = fib[3] + fib[2] = 2 + 1 = 3fib[5] = fib[4] + fib[3] = 3 + 2 = 5fib[6] = fib[5] + fib[4] = 5 + 3 = 8
Таким образом, fib[6] равно 8, что является 6-ым числом Фибоначчи.
| Python |
# Инициализация базовых случаев
fib = [0, 1] # Первые два числа Фибоначчи
n = 10 # Найти 10-е число Фибоначчи
# Вычисление остальных чисел Фибоначчи "снизу вверх"
for i in range(2, n + 1):
next_fib = fib[i - 1] + fib[i - 2]
fib.append(next_fib)
# Результат
print(f"Fib({n}) = {fib[n]}") # Выводит "Fib(10) = 55"
|
| C++ |
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> fib(2); // Инициализация базовых случаев
fib[0] = 0;
fib[1] = 1;
int n = 10; // Найти 10-е число Фибоначчи
// Вычисление остальных чисел Фибоначчи "снизу вверх"
for (int i = 2; i <= n; i++) {
int next_fib = fib[i - 1] + fib[i - 2];
fib.push_back(next_fib);
}
// Вывод результата
cout << "Fib(" << n << ") = " << fib[n] << endl;
// результат "Fib(10) = 55"
return 0;
}
|