Числа Фибоначчи — это последовательность чисел, в которой каждое последующее число является суммой двух предыдущих. Последовательность обычно начинается с 0 и 1.
F0=0 F1=1 Fn=Fn−1+Fn−2 для n>1
Таким образом, последовательность выглядит так: 0,1,1,2,3,5,8,13,21,34,…
В Python есть несколько способов сгенерировать числа Фибоначчи.
1. Итеративный подход (с использованием цикла For или While)
Это самый эффективный способ для генерации чисел Фибоначчи, особенно для больших n, поскольку он избегает рекурсивных вызовов и связанных с ними накладных расходов.
Вариант 1: Генерация до определенного числа Фибоначчи (n-й член)
Python
Def fibonacci_iterative_n(n):
if n < 0:
return "Число должно быть неотрицательным."
elif n == 0:
return 0
elif n == 1:
return 1
else:
a, b = 0, 1
for _ in range(2, n + 1): # Начинаем с 2, т. к. 0-й и 1-й уже известны
a, b = b, a + b
return b
Print("Итеративный метод (по номеру члена):")
Print(f"fibonacci_iterative_n(0): {fibonacci_iterative_n(0)}") # 0
Print(f"fibonacci_iterative_n(1): {fibonacci_iterative_n(1)}") # 1
Print(f"fibonacci_iterative_n(2): {fibonacci_iterative_n(2)}") # 1
Print(f"fibonacci_iterative_n(3): {fibonacci_iterative_n(3)}") # 2
Print(f"fibonacci_iterative_n(10): {fibonacci_iterative_n(10)}") # 55
Print(f"fibonacci_iterative_n(20): {fibonacci_iterative_n(20)}") # 6765
Вариант 2: Генерация последовательности до определенного предела
Python
Def fibonacci_sequence_limit(limit):
sequence = []
a, b = 0, 1
while a <= limit:
sequence. append(a)
a, b = b, a + b
return sequence
Print("\nИтеративный метод (последовательность до предела):")
Print(f"fibonacci_sequence_limit(10): {fibonacci_sequence_limit(10)}") # [0, 1, 1, 2, 3, 5, 8]
Print(f"fibonacci_sequence_limit(50): {fibonacci_sequence_limit(50)}") # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
2. Рекурсивный подход
Рекурсивное определение чисел Фибоначчи очень элегантно, но Неэффективно для больших n из-за многократных повторных вычислений одних и тех же значений.
Python
Def fibonacci_recursive(n):
if n < 0:
return "Число должно быть неотрицательным."
elif n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_recursive(n — 1) + fibonacci_recursive(n — 2)
Print("\nРекурсивный метод:")
Print(f"fibonacci_recursive(0): {fibonacci_recursive(0)}") # 0
Print(f"fibonacci_recursive(1): {fibonacci_recursive(1)}") # 1
Print(f"fibonacci_recursive(2): {fibonacci_recursive(2)}") # 1
Print(f"fibonacci_recursive(10): {fibonacci_recursive(10)}") # 55
# print(f"fibonacci_recursive(35): {fibonacci_recursive(35)}") # Это займет много времени!
Проблема Рекурсивного Подхода: Для fibonacci_recursive(5) будут вызваны fibonacci_recursive(4) и fibonacci_recursive(3). А fibonacci_recursive(4) в свою очередь вызовет fibonacci_recursive(3) и fibonacci_recursive(2), что приводит к повторным вычислениям. Это приводит к экспоненциальной сложности O(2n).
3. Рекурсивный подход с мемоизацией (или динамическое программирование)
Чтобы решить проблему неэффективности рекурсивного подхода, мы можем использовать Мемоизацию (кэширование результатов). Это значительно улучшает производительность, сводя сложность к O(n).
Python
# Используем словарь для хранения уже вычисленных значений
Memo = {}
Def fibonacci_memoized(n):
if n < 0:
return "Число должно быть неотрицательным."
if n in memo:
return memo[n]
if n == 0:
return 0
if n == 1:
return 1
else:
result = fibonacci_memoized(n — 1) + fibonacci_memoized(n — 2)
memo[n] = result # Сохраняем результат перед возвратом
return result
Print("\nРекурсивный метод с мемоизацией:")
Print(f"fibonacci_memoized(0): {fibonacci_memoized(0)}") # 0
Print(f"fibonacci_memoized(1): {fibonacci_memoized(1)}") # 1
Print(f"fibonacci_memoized(10): {fibonacci_memoized(10)}") # 55
Print(f"fibonacci_memoized(100): {fibonacci_memoized(100)}") # Большое число, вычисляется быстро
Для Python 3.2+: Есть удобный декоратор functools. lru_cache для автоматической мемоизации.
Python
From functools import lru_cache
@lru_cache(maxsize=None) # maxsize=None означает неограниченный кэш
Def fibonacci_lru_cache(n):
if n < 0:
return "Число должно быть неотрицательным."
elif n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_lru_cache(n — 1) + fibonacci_lru_cache(n — 2)
Print("\nРекурсивный метод с @lru_cache:")
Print(f"fibonacci_lru_cache(0): {fibonacci_lru_cache(0)}") # 0
Print(f"fibonacci_lru_cache(1): {fibonacci_lru_cache(1)}") # 1
Print(f"fibonacci_lru_cache(10): {fibonacci_lru_cache(10)}") # 55
Print(f"fibonacci_lru_cache(100): {fibonacci_lru_cache(100)}") # Вычисляется очень быстро
4. Генератор (для последовательности)
Генератор позволяет генерировать числа Фибоначчи по запросу, не создавая весь список в памяти, что очень эффективно для очень длинных последовательностей.
Python
Def fibonacci_generator(n_terms):
a, b = 0, 1
count = 0
while count < n_terms:
yield a # ‘yield’ делает функцию генератором
a, b = b, a + b
count += 1
Print("\nГенератор Фибоначчи:")
# Генерируем первые 10 чисел
For num in fibonacci_generator(10):
print(num, end=" ") # Вывод: 0 1 1 2 3 5 8 13 21 34
Print()
# Можно также получить список из генератора
List_fib = list(fibonacci_generator(7))
Print(f"Список из генератора: {list_fib}") # [0, 1, 1, 2, 3, 5, 8]
Какой метод выбрать?
- Для получения n-го числа Фибоначчи: Итеративный подход (Fibonacci_iterative_n) — самый эффективный и рекомендуемый. Для получения последовательности Фибоначчи (если нужна полная последовательность):
- Если производительность очень критична для огромных последовательностей, используйте Генератор (Fibonacci_generator). Если список не очень большой и удобство важнее минимального выигрыша в памяти, можно использовать итеративный подход с накоплением в список.
Для изучения рекурсии или как демонстрация мемоизации: Рекурсивный подход с мемоизацией (fibonacci_memoized или @lru_cache). Никогда не используйте чистую рекурсию (Fibonacci_recursive) для больших n в реальном коде.
