Embedded Files
???
Що це за формула
???
Задача #3258 Послідовність Фібоначчі
Задача #3258 Послідовність Фібоначчі
Задача #2292 Число Фібоначчі
Задача #2292 Число Фібоначчі
Розглянемо послідовність чисел 1,1,2,3,5,8,13,21,… у якій кожне число є сумою двох попередніх. Це числа Фібоначчі. Формальне їх визначення таке:
F(1)=1, F(2)=1,
F(n)= F(n-2)+ F(n-1), якщо n>2.
Функція F(n) задана рекурсивно, тобто «через себе». База - значення функції на аргументах 1 і 2, а рекурентний крок – формула
F(n)= F(n-2)+ F(n-1).
При обчисленні значення F(6) будуть викликані процедури обчислення F(4) та F(5). У свою чергу, для обчислення останніх буде потрібно обчислення двох пар F(3), F(4) і F(2), F(3). Можна намалювати «дерево рекурсивних викликів».
Можна зауважити, що F(3) обчислюється тричі. Якщо розглянути обчислення F(n) при великих n, то повторних обчислень буде дуже багато. Це і є основний недолік рекурсії — повторні обчислення тих самих значень. Крім того, з рекурсивними функціями пов'язано одну серйозну помилку: дерево рекурсивних викликів може виявитися нескінченним і комп'ютер зависне. Важливо, щоб процес зведення завдання до більш простих колись закінчувався.
Існує спосіб вирішити проблему повторних обчислень. Він очевидний - потрібно запам'ятовувати знайдені значення, щоб не обчислювати їх щоразу заново. Звичайно, для цього доведеться активно використати пам'ять.
Наприклад, рекурсивний алгоритм обчислення чисел Фібоначчі легко доповнити трьома рядками:
створити глобальний масив MEMO, що складається з нулів;
після обчислення числа Фібоначчі F(n) помістити його значення в MEMO[n];
на початку рекурсивної процедури зробити перевірку те що MEMO[n]=0, і якщо MEMO[n]≠0, то повернути MEMO[n] як результат, а інакше приступити до рекурсивного обчислення.
Рекурсію із запам'ятовуванням для обчислення чисел Фібоначчі ми просто привели для демонстрації ідеї. Для чисел Фібоначчі є простий «людський алгоритм», який не використовує рекурсивні виклики та запам'ятовування всіх обчислених значень. Достатньо пам'ятати два останні числа Фібоначчі, щоб обчислити наступне. Потім попереднє можна «забути» та перейти до обчислення наступного:
1. a = b = 1;
2. якщо n > 2 , то зробити n - 2 раз: c = a + b; a = b; b =c;
3. повернути відповідь b;
Олександр Сидоренко. З чого почати програмувати? Полтава 2023
Код: рекурсія
Код: рекурсія
# РЕКУРСІЯ
def fib(n):
if n < 3: # базовий випадок
return 1
else: # Рекурсивний випадок
return fib(n - 1) + fib(n - 2)
n=int(input())
print(fib(n))
Код: рекурсія #2 (Python 10)
Код: рекурсія #2 (Python 10)
# РЕКУРСІЯ 2
def fib(n):
# базовий випадок
if n < 3:
return 1
# хитрість
elif (n == 20) and (f > 0):
return f
else:
# Рекурсивний випадок
return fib(n - 1) + fib(n - 2)
f = 0
n = int(input())
f = fib(20)
print(fib(n))
Код: цикл
Код: цикл
# ЦИКЛ
def fib(k):
a, b, c = 0, 1, 1
for i in range(k - 1):
c = a + b
a, b = b, c
return c
n=int(input())
print(fib(n))
Код: формула
Код: формула
# ФОРМУЛА
import math
n=int(input())
print(int((((1+math.sqrt(5))/2)**n-((1-math.sqrt(5))/2)**n)/math.sqrt(5)))
Мемоїзація
Мемоїзація
Код: рекурсія із запам'ятовуванням
Код: рекурсія із запам'ятовуванням
# РЕКУРСІЯ MEMO
def fib(n):
# базовий випадок
if n < 3:
return 1
# memo випадок
elif memo[n] != 0 :
return memo[n]
else:
# Рекурсивний випадок
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
n=int(input())
memo = [0] * (n+1)
print(fib(n))
Код: рекурсія з мемоїзацією
Код: рекурсія з мемоїзацією
# РЕКУРСІЯ MEMO
def fib(n, memo={}):
# базовий випадок
if n < 3:
return 1
# memo випадок
elif n in memo:
return memo[n]
else:
# Рекурсивний випадок
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
n=int(input())
print(fib(n))
Код: рекурсія з декоратором
Код: рекурсія з декоратором
# РЕКУРСІЯ з ДЕКОРАТОРОМ
from functools import *
@lru_cache(None)
def fib(n):
if n < 3: # базовий випадок
return 1
else: # Рекурсивний випадок
return fib(n - 1) + fib(n - 2)
n=int(input())
print(fib(n))
Код: цикл
Код: цикл
# ЦИКЛ
def fib(n):
a, b, c = 0, 1, 1
for i in range(n - 1):
c = a + b
a, b = b, c
return c
n = int(input())
x = []
for i in range(n):
x.append(int(input()))
for i in range(n):
print(fib(x[i]))
Page updated
Google Sites
Report abuse