Задача
Предположим, нам нужно вычислить n-ое число Фибоначчи, где n - это положительное целое число.
Инициализация: Создадим массив для хранения результатов вычислений (назовем его fib) и установим начальные значения для чисел Фибоначчи: fib[0] = 0 и fib[1] = 1.
fib
fib[0] = 0
fib[1] = 1
Итерация: Начнем цикл с i = 2 и продолжим до i = n. На каждой итерации мы будем вычислять fib[i] на основе fib[i-1] и fib[i-2]:
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-ое число Фибоначчи.
fib[n]
Метод снизу вверх эффективен, так как избегает дублирования вычислений и имеет линейную сложность по времени. Вычисления производятся с самой маленькой подзадачи, решение которой сохраняется в массиве. Для решение более крупных подзадач используются решения более мелких подзадач.
Например, для n = 6, вычисление будет следующим образом:
n = 6
fib[2] = fib[1] + fib[0] = 1 + 0 = 1
fib[3] = fib[2] + fib[1] = 1 + 1 = 2
fib[4] = fib[3] + fib[2] = 2 + 1 = 3
fib[5] = fib[4] + fib[3] = 3 + 2 = 5
fib[6] = fib[5] + fib[4] = 5 + 3 = 8
Таким образом, fib[6] равно 8, что является 6-ым числом Фибоначчи.
fib[6]
# Инициализация базовых случаев 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"
#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; }
Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
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)).
n
return
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач