Генератор Фибоначчи
Автор: uskenbay02 • Июль 15, 2021 • Реферат • 1,372 Слов (6 Страниц) • 288 Просмотры
Өскенбай Саяжан Алмасбайқызы
Генератор Фибоначчи — генератор псевдослучайных чисел, также называемые аддитивными генераторами.
В отличие от генераторов, использующих линейный конгруэнтный алгоритм, фибоначчиевы генераторы можно использовать в статистических алгоритмах, требующих высокого разрешения.
В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.
Алгоритм Блюм — Блюма — Шуба — генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом.
Генератор Фибоначчи
from functools import lru_cache
class FibGenerator:
"""
Генератор, вычисляющий числа Фибоначчи.
"""
def __init__(self):
self.a, self.b = 0, 1
def __iter__(self):
return self
def __next__(self):
self.a, self.b = self.b, self.a + self.b
return self.a
def find_with_recursion(n: int) -> int:
"""
Вычисление числа Фибоначчи через рекурсию.
"""
if n in [1, 2]:
return 1
return find_with_recursion(n - 1) + find_with_recursion(n - 2)
find_with_cache = lru_cache(maxsize=None)(find_with_recursion)
find_with_cache.__doc__ = 'Поиск числа Фибоначчи по рекурсивному алгоритму с ' \
'использованием кеша.'
def find_with_list(n: int) -> int:
"""
Вычисление числа Фибоначчи с использованием списка.
"""
lst = [0, 1]
if n == 1:
return lst[n]
for i in range(2, n + 1):
lst.append(lst[i-1] + lst[i-2])
return lst[n]
def find_with_two_variables(n: int) -> int:
"""
Вычисление числа Фибоначчи с использованием двух переменных.
"""
a, b = 0, 1
if n == 1:
return b
for _ in range(2, n + 1):
a, b = b, a + b
return b
def find_last_digit(n: int) -> int:
"""
Дано число 1≤n≤107, необходимо найти последнюю цифру n-го числа Фибоначчи.
"""
a, b = 0, 1
if n == 1:
return b
for _ in range(2, n + 1):
a, b = b, (a + b) % 10
return b
def find_pezano_period_list(m):
"""
Возвращает список остатков от деления последовательности Фибоначи на m
"""
a, b, pezano_lst = 0, 1, [0, 1]
if m == 1:
return [0]
# Максимально период равен 6 * m для всех положительных целых m
for _ in range(6 * m):
a, b = b, (a + b) % m
pezano_lst.append(b)
# Проверяем не начался ли новый период. Период всегда начинается с 0 и 1
if pezano_lst[-2] == 0 and pezano_lst[-1] == 1:
...