Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

Генератор Фибоначчи

Автор:   •  Июль 15, 2021  •  Реферат  •  1,372 Слов (6 Страниц)  •  6 Просмотры

Страница 1 из 6

Өскенбай Саяжан Алмасбайқызы

Генератор Фибоначчи — генератор псевдослучайных чисел, также называемые аддитивными генераторами.

В отличие от генераторов, использующих линейный конгруэнтный алгоритм, фибоначчиевы генераторы можно использовать в статистических алгоритмах, требующих высокого разрешения.

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.

Алгоритм Блюм — Блюма — Шуба  — генератор псевдослучайных чисел, предложенный в 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:

...

Скачать:   txt (6.4 Kb)   pdf (82.1 Kb)   docx (12 Kb)  
Продолжить читать еще 5 страниц(ы) »
Доступно только на Essays.club