Генератор чисел Фибоначчи
Пытаюсь сделать более элегантное решение, но не получается, не хватает опыта. Пробовал сделать следующий генератор:
fib_range = [(fib_range[iteration-2] + fib_range[iteration-1) for iteration in range (2,maximum)] Увы сколько не пробовал его изменять — выдаёт ошибку. Подскажите, пожалуйста, кто уже имеет огромный опыт в Python 3.x, как правильно оформить генератор для этого примера?
Отслеживать
222k 15 15 золотых знаков 120 120 серебряных знаков 234 234 бронзовых знака
задан 15 фев 2019 в 17:29
Sergey Ryabov Sergey Ryabov
73 1 1 серебряный знак 9 9 бронзовых знаков
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
def fib(n): a, b = 0, 1 for __ in range(n): yield a a, b = b, a + b print(list(fib(10)) # Тест [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] Отслеживать
ответ дан 15 фев 2019 в 19:22
17.2k 4 4 золотых знака 21 21 серебряный знак 32 32 бронзовых знака
Спасибо! Действительно элегантно! Использование функции это отличное решение, а можно ли этот алгоритм упаковать в одну строчку, аналогично генератору, который я пытался сделать?
16 фев 2019 в 3:26
@SergeyRyabov, вы не пытались сделать генератор, а рекурсивную функцию. Может быть, что потому вы даже удивленный ответами, которые вы не хотели. То, что вы пытались сделать в одну строчку, называется абстракция списка (list comprehension) — он основан не на функциях, а на итеруемых объектах, как списки, множества, кортежи, итараторы, генераторы, и т. д. — Также, не возможно.
16 фев 2019 в 13:54
Увы сложности перевода, по этому я назвал list comprehension как генератор. Увы он и абстракцией списка тоже никак не называется. Однако в некоторых книгах используется название Генератор Списка, вот его и применил. В любом случае — спасибо!
17 фев 2019 в 13:37
def fib(): a,b = 1,1 while True: yield a a,b = b,a+b import itertools print(list(itertools.islice(fib(), 100))) [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075] Как сделать число фибоначчи в питоне
Как находить числа Фибоначчи в Python: простые способы и оптимизации
09 марта 2023
Оценки статьи
Еще никто не оценил статью
В этой статье мы рассмотрим несколько простых способов нахождения чисел Фибоначчи в Python и оптимизации для более быстрого выполнения кода.
Числа Фибоначчи — это последовательность чисел, начинающаяся с 0 и 1, где каждое последующее число равно сумме двух предыдущих.
Эта последовательность широко используется в математике, физике и информатике, поэтому ее нахождение в Python может быть полезно во многих случаях.
Рекурсивный подход нахождения чисел Фибоначчи
Один из самых простых способов нахождения чисел Фибоначчи — это рекурсивный подход. Мы можем определить функцию, которая будет вызывать саму себя для нахождения двух предыдущих чисел и возвращать их сумму.
Вот как это может выглядеть в Python:
def fibonacci_recursive(n): if n 1: return n else: return fibonacci_recursive(n-1) + fibonacci_recursive(n-2) print(fibonacci_recursive(20)) #6765 Этот код будет работать правильно, но может быть очень медленным при больших значениях n , так как он будет вызывать себя множество раз для каждого числа Фибоначчи. Это связано с тем, что мы вычисляем каждое число Фибоначчи несколько раз.
Итерационный подход нахождения чисел Фибоначчи
Более эффективный подход — это использование итераций для нахождения чисел Фибоначчи. В этом случае мы будем использовать цикл for для последовательного вычисления каждого числа Фибоначчи от 0 до n .
Вот как это может выглядеть в Python:
def fibonacci_iterative(n): if n 1: return n else: fib_prev, fib_current = 0, 1 for i in range(2, n+1): fib_next = fib_prev + fib_current fib_prev, fib_current = fib_current, fib_next return fib_current print(fibonacci_iterative(20)) #6765 Использование формулы Бине для нахождения чисел Фибоначчи
Еще более эффективный способ нахождения чисел Фибоначчи — это использование формулы Бине. Формула Бине позволяет вычислить любое число Фибоначчи за O(1) времени.
Для использования формулы Бине, нам нужно знать золотое сечение и его сопряженное число, которые можно выразить следующим образом:
φ = (1 + sqrt(5)) / 2 ψ = (1 — sqrt(5)) / 2
Затем, мы можем использовать формулу Бине, чтобы вычислить n-ое число Фибоначчи следующим образом:
F_n = (φ^n — ψ^n) / sqrt(5)
Вот как это может выглядеть в Python:
from math import sqrt def fibonacci_binet(n): phi = (1 + sqrt(5)) / 2 psi = (1 - sqrt(5)) / 2 return int((phi**n - psi**n) / sqrt(5)) print(fibonacci_binet(20)) #6765 Обратите внимание, что мы используем функцию sqrt() из модуля math для вычисления квадратного корня.
Оптимизации для итерационного подхода
Хотя итерационный подход более эффективен, мы все еще можем сделать некоторые оптимизации для улучшения его производительности. Вот несколько идей:
Мы можем использовать динамическое программирование для сохранения уже вычисленных значений и избежать повторных вычислений. Для этого мы можем использовать словарь, где ключом будет номер числа Фибоначчи, а значением — его значение.
Мы можем использовать формулу Бине для нахождения только одного числа Фибоначчи, если нам не нужно вычислять последовательность чисел.
Вот как это может выглядеть в Python:
from math import sqrt fib_dict = 0: 0, 1: 1> def fibonacci_dp(n): if n not in fib_dict: fib_dict[n] = fibonacci_dp(n-1) + fibonacci_dp(n-2) return fib_dict[n] def fibonacci_binet_single(n): phi = (1 + sqrt(5)) / 2 psi = (1 - sqrt(5)) / 2 return int((phi**n - psi**n) / sqrt(5)) print(fibonacci_binet_single(20)) #6765 print(fibonacci_dp(20)) #6765 Эти оптимизации помогут ускорить выполнение кода, особенно при больших значениях n .
Заключение по нахождению чисел Фибоначчи в Python
В заключение, нахождение чисел Фибоначчи в Python может быть выполнено разными способами, от рекурсивного подхода до использования формулы Бине.
Выбор подхода зависит от конкретных требований задачи и необходимой производительности. Оптимизации могут помочь ускорить выполнение кода, особенно при больших значениях n.
Меню категорий
-
Загрузка категорий.
Как написать число Фибоначчи в Питоне: простое и эффективное решение с помощью рекурсии и цикла
Первый пример использует рекурсию для вычисления чисел Фибоначчи, а второй пример использует цикл. Оба варианта дадут вам результат: число Фибоначчи для заданного значения n.
Детальный ответ
Как написать число Фибоначчи в Питоне
Числа Фибоначчи представляют последовательность, в которой каждое число является суммой двух предыдущих чисел. Числа Фибоначчи начинаются с 0 и 1. Например, последовательность чисел Фибоначчи выглядит следующим образом: 0, 1, 1, 2, 3, 5, 8, 13, и так далее. Давайте рассмотрим несколько способов написания программы на Питоне для генерации чисел Фибоначчи.
1. Использование цикла for
Один из способов написания программы на Питоне для генерации чисел Фибоначчи — использование цикла for. В этом подходе мы будем итерироваться через заданное количество чисел и генерировать числа Фибоначчи с помощью формулы.
def fibonacci(n): fib_sequence = [0, 1] for i in range(2, n+1): next_num = fib_sequence[i-1] + fib_sequence[i-2] fib_sequence.append(next_num) return fib_sequence
В этом примере мы создаем пустой список `fib_sequence`, в котором мы будем хранить числа Фибоначчи. Затем мы итерируемся от 2 до `n+1` и генерируем следующее число Фибоначчи, добавляя его в список. Вы можете вызвать эту функцию, передав число `n`, чтобы получить последовательность чисел Фибоначчи.
2. Рекурсивный подход
Второй способ — использование рекурсии. В рекурсивном подходе функция вызывает саму себя для генерации чисел Фибоначчи.
def fibonacci(n): if n
Здесь мы проверяем базовый случай, когда `n` меньше или равно 1, и просто возвращаем `n`. В противном случае мы вызываем функцию `fibonacci` с аргументами `n-1` и `n-2`, чтобы сгенерировать следующее число Фибоначчи. Вы можете вызвать функцию `fibonacci` с заданным числом `n` для получения числа Фибоначчи.
3. Использование генератора
Третий способ - использование генератора. Генераторы в Питоне позволяют генерировать значения в ленивом режиме.
def fibonacci(): a, b = 0, 1 while True: yield a a, b = b, a + b
Здесь мы определяем функцию `fibonacci` без аргументов. Внутри функции мы устанавливаем начальные значения `a` и `b` равными 0 и 1 соответственно. Затем мы начинаем бесконечный цикл `while True`, в котором мы генерируем текущее значение `a` и обновляем `a` и `b` для генерации следующего значения. Вы можете использовать этот генератор для получения чисел Фибоначчи в любом месте вашей программы.
Заключение
Теперь у вас есть несколько способов написания программы на Питоне для генерации чисел Фибоначчи. Вы можете выбрать подход, который больше всего соответствует вашим потребностям и предпочтениям. Не забывайте экспериментировать и разрабатывать свои решения, чтобы более глубоко понять, как работают числа Фибоначчи и как их генерировать в Питоне.
Числа Фибоначчи в Python: реализация и примеры
Числа Фибоначчи - это последовательность чисел, в которой каждое число равно сумме двух предыдущих чисел. Наиболее часто используемые начальные числа - это 0 и 1. Таким образом, первые несколько чисел Фибоначчи выглядят так: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и т.д.
Для вычисления чисел Фибоначчи в Python можно использовать различные подходы. Один из таких подходов - это рекурсивная функция. Рекурсивная функция - это функция, которая вызывает сама себя. В следующем примере кода мы определим рекурсивную функцию для вычисления чисел Фибоначчи:
def fibonacci(n): if n
В этом коде мы определяем функцию «fibonacci», которая принимает один аргумент «n». Если аргумент «n» меньше или равен 1, то мы просто возвращаем этот аргумент. В противном случае мы вызываем функцию «fibonacci» с аргументами «n-1» и «n-2» и складываем результаты.
Мы можем вызвать функцию, чтобы вычислить число Фибоначчи для определенного значения «n»:
print(fibonacci(5)) # Output: 5 print(fibonacci(10)) # Output: 55
Рекурсивная функция для вычисления чисел Фибоначчи может быть не очень эффективной, потому что она вызывает сама себя многократно. Мы можем улучшить производительность, используя другой подход - использование цикла. В следующем примере мы определим функцию для вычисления чисел Фибоначчи, используя цикл:
def fibonacci(n): if n
В этом примере кода мы определяем функцию «fibonacci», которая принимает один аргумент «n». Если аргумент «n» меньше или равен 1, то мы просто возвращаем этот аргумент. В противном случае мы используем цикл для вычисления последовательности чисел Фибоначчи.
Мы можем вызвать функцию, чтобы вычислить число Фибоначчи для определенного значения «n»:
print(fibonacci(5)) # Output: 5 print(fibonacci(10)) # Output: 55
В этом примере кода мы использовали присваивание кортежа для обмена значениями «a» и «b» без необходимости вводить дополнительную переменную.
В общем, вычисление чисел Фибоначчи - это классический пример использования рекурсивных функций и циклов в Python. Рекурсивный подход подходит для небольших значений «n», а циклы - для больших значений.