Фибоначчиева система счисления python

Определение

Последовательность Фибоначчи определяется следующим образом:



Несколько первых её членов:

История

Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci) (также известный как Леонардо Пизанский (Leonardo Pisano)). Однако именно благодаря математику 19 века Люка (Lucas) название "числа Фибоначчи" стало общеупотребительным.

Впрочем, индийские математики упоминали числа этой последовательности ещё раньше: Гопала (Gopala) до 1135 г., Хемачандра (Hemachandra) — в 1150 г.

Числа Фибоначчи в природе

Сам Фибоначчи упоминал эти числа в связи с такой задачей: "Человек посадил пару кроликов в загон, окруженный со всех сторон стеной. Сколько пар кроликов за год может произвести на свет эта пара, если известно, что каждый месяц, начиная со второго, каждая пара кроликов производит на свет одну пару?". Решением этой задачи и будут числа последовательности, называемой теперь в его честь. Впрочем, описанная Фибоначчи ситуация — больше игра разума, чем реальная природа.

Индийские математики Гопала и Хемачандра упоминали числа этой последовательности в связи с количеством ритмических рисунков, образующихся в результате чередования долгих и кратких слогов в стихах или сильных и слабых долей в музыке. Число таких рисунков, имеющих в целом долей, равно .

Числа Фибоначчи появляются и в работе Кеплера 1611 года, который размышлял о числах, встречающихся в природе (работа "О шестиугольных снежинках").

Интересен пример растения — тысячелистника, у которого число стеблей (а значит и цветков) всегда есть число Фибоначчи. Причина этого проста: будучи изначально с единственным стеблем, этот стебель затем делится на два, затем от главного стебля ответвляется ещё один, затем первые два стебля снова разветвляются, затем все стебли, кроме двух последних, разветвляются, и так далее. Таким образом, каждый стебель после своего появления "пропускает" одно разветвление, а затем начинает делиться на каждом уровне разветвлений, что и даёт в результате числа Фибоначчи.

Вообще говоря, у многих цветов (например, лилий) число лепестков является тем или иным числом Фибоначчи.

Также в ботанике известно явление ”филлотаксиса”. В качестве примера можно привести расположение семечек подсолнуха: если посмотреть сверху на их расположение, то можно увидеть одновременно две серии спиралей (как бы наложенных друг на друга): одни закручены по часовой стрелке, другие — против. Оказывается, что число этих спиралей примерно совпадает с двумя последовательными числами Фибоначчи: 34 и 55 или 89 и 144. Аналогичные факты верны и для некоторых других цветов, а также для сосновых шишек, брокколи, ананасов, и т.д.

Для многих растений (по некоторым данным, для 90% из них) верен и такой интересный факт. Рассмотрим какой-нибудь лист, и будем спускаться от него вниз до тех пор, пока не достигнем листа, расположенного на стебле точно так же (т.е. направленного точно в ту же сторону). Попутно будем считать все листья, попадавшиеся нам (т.е. расположенные по высоте между стартовым листом и конечным), но расположенными по-другому. Нумеруя их, мы будем постепенно совершать витки вокруг стебля (поскольку листья расположены на стебле по спирали). В зависимости от того, совершать витки по часовой стрелке или против, будет получаться разное число витков. Но оказывается, что число витков, совершённых нами по часовой стрелке, число витков, совершённых против часовой стрелки, и число встреченных листьев образуют 3 последовательных числа Фибоначчи.

Читайте также:  Ubuntu server системные требования

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

Свойства

Числа Фибоначчи обладают множеством интересных математических свойств.

Вот лишь некоторые из них:

Из предыдущего равенства при вытекает:

Из предыдущего равенста по индукции можно получить, что

всегда кратно .

Верно и обратное к предыдущему утверждение:

если кратно , то кратно .

По отношению к алгоритму Евклида числа Фибоначчи обладают тем замечательным свойством, что они являются наихудшими входными данными для этого алгоритма (см. "Теорема Ламе" в Алгоритме Евклида).

Фибоначчиева система счисления

Теорема Цекендорфа утверждает, что любое натуральное число можно представить единственным образом в виде суммы чисел Фибоначчи:

где , , , (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:



причём ни в каком числе не могут идти две единицы подряд.

Нетрудно получить и правило прибавления единицы к числу в фибоначчиевой системе счисления: если младшая цифра равна 0, то её заменяем на 1, а если равна 1 (т.е. в конце стоит 01), то 01 заменяем на 10. Затем "исправляем" запись, последовательно исправляя везде 011 на 100. В результате за линейное время будет получена запись нового числа.

Перевод числа в фибоначчиеву систему счисления осуществляется простым "жадным" алгоритмом: просто перебираем числа Фибоначчи от больших к меньшим и, если некоторое , то входит в запись числа , и мы отнимаем от и продолжаем поиск.

Формула для n-го числа Фибоначчи

Формула через радикалы

Существует замечательная формула, называемая по имени французского математика Бине (Binet), хотя она была известна до него Муавру (Moivre):

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

Сразу можно заметить, что второе слагаемое всегда по модулю меньше 1, и более того, очень быстро убывает (экспоненциально). Отсюда следует, что значение первого слагаемого даёт "почти" значение . Это можно записать в строгом виде:

где квадратные скобки обозначают округление до ближайшего целого.

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

Матричная формула для чисел Фибоначчи

Нетрудно доказать матричное следующее равенство:

Но тогда, обозначая

Таким образом, для нахождения -го числа Фибоначчи надо возвести матрицу в степень .

Вспоминая, что возведение матрицы в -ую степень можно осуществить за (см. Бинарное возведение в степень), получается, что -ое число Фибоначчи можно легко вычислить за c использованием только целочисленной арифметики.

Периодичность последовательности Фибоначчи по модулю

Рассмотрим последовательность Фибоначчи по некоторому модулю . Докажем, что она является периодичной, и причём период начинается с (т.е. предпериод содержит только ).

Докажем это от противного. Рассмотрим пар чисел Фибоначчи, взятых по модулю :

Читайте также:  Разобрать сабвуфер ps wtp12

Поскольку по модулю может быть только различных пар, то среди этой последовательности найдётся как минимум две одинаковые пары. Это уже означает, что последовательность периодична.

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

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, . . Иногда ряд начинают с нуля: 0, 1, 1, 2, 3, 5, . . В данном случае мы будем придерживаться первого варианта.

Формула:

Пример вычисления:

Вычисление n-го числа ряда Фибоначчи с помощью цикла while

  1. Присвоить переменным fib1 и fib2 значения двух первых элементов ряда, то есть присвоить переменным единицы.
  2. Запросить у пользователя номер элемента, значение которого он хочет получить. Присвоить номер переменной n .
  3. Выполнять следующие действия n – 2 раз, так как первые два элемента уже учтены:
  1. Сложить fib1 и fib2 , присвоив результат переменной для временного хранения данных, например, fib_sum .
  2. Переменной fib1 присвоить значение fib2 .
  3. Переменной fib2 присвоить значение fib_sum .
  • Вывести на экран значение fib2 .
  • Примечание. Если пользователь вводит 1 или 2, тело цикла ни разу не выполняется, на экран выводится исходное значение fib2 .

    Компактный вариант кода:

    Вывод чисел Фибоначчи циклом for

    В данном случае выводится не только значение искомого элемента ряда Фибоначчи, но и все числа до него включительно. Для этого вывод значения fib2 помещен в цикл.

    Рекурсивное вычисление n-го числа ряда Фибоначчи

    1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
    2. Во всех остальных случаях вызвать эту же функцию с аргументами n – 1 и n – 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.

    Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

    В 1202 г. итальянский математик Леонард Пизанский (Leonardo Pisanto, около 1170 – около 1228), известный под именем Фибоначчи (Fibonacci), предложил такую задачу:

    Пара кроликов каждый месяц дает приплод – двух кроликов (самца и самку), от которых через два месяца уже получается новый приплод. Сколько кроликов будет через год, если в начале года мы имели одну пару молодых кроликов?

    Числа, соответствующие количеству кроликов составляют последовательность: 1, 1, 2, 3, 5, 8, 13, 21, 34, …

    Каждый из членов этой последовательности, начиная с третьего, равен сумме двух предыдущих членов. Эта последовательность называется рядом Фибоначчи, а ее члены – числами Фибоначчи. На уроках математики эти числа связаны с так называемым золотым сечениям. На уроках информатики числа Фибоначчи широко используются для объяснения рекурсивной зависимости, где F(n)=F(n-1) + F(n-2), при n³3, F(1)=1 и F(2)=1.

    Читайте также:  Huawei talkband b3 classic

    Таким образом, получаем, что:

    В итоге, получаем числа: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …

    Но мало кто знает, что числа Фибоначчи используются в так называемой Фибоначчиевой системе счисления.

    В старшей школе при изучении темы «Кодирование информации» я предлагаю обучающимся познакомиться с Фибоначчиевой системой счисления в целях расширения представлений о системах счисления и обобщения принципа позиционности.

    Обучающиеся узнают, что принцип разложения любого числа в Фибоначчиевой системе счисления основывается на уже знакомом им переводе десятичного числа в двоичное «Методом подбора степеней числа 2»: исходное десятичное число представляют в виде суммы степеней числа 2, в этой сумме слагаемые выстраивают от большего к меньшему. Затем те степени двойки, которые имеются, заменяются 1, а те, которых нет заменяются на 0.

    Например, число 37 будет представлено в двоичной системе счисления, как 100101 согласно разложению:

    исходное десятичное число степени числа «два»
    32 16 8 4 2 1
    37 1 1 1

    Т.е. в разложении десятичного числа используются двоичные цифры (алфавит) – только 0 и 1. Следовательно, если запись числа в фибоначчиевой системе имеет вид f(n), f(n–1), …, f(2), f(1), то этому числу соответствует десятичное значение, равное , где F(k) – числа Фибоначчи, f(k) Î <0, 1>, причем в записи числа две единицы не должны стоять рядом, что очень важно: при несоблюдении этого условия запись числа будет неоднозначной.

    Например, число 5 в десятичной системе счисления может быть записано как 110Fib (5 = 1 · 3 + 1 · 2 + 0 · 1).

    Разложение (вариант 1)

    исходное десятичное число Базисные числа фибоначчиевой системы счисления
    3 2 1
    5 1 1

    и 1000Fib (5 = 1 · 5 + 0 · 3 + 0 · 2 + 0 · 1), разложение (вариант 2)

    исходное десятичное число Базисные числа фибоначчиевой системы счисления
    5 3 2 1
    5 1

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

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

    Задание 1. Найдите все способы перевода следующих чисел из десятичной системы счисления в фибоначчиеву, например, чисел 37 и 25.

    Вариант решения обучающегося: Перевод числа из десятичной системы счисления в фибоначчиевую:

    исходное десятичное число Базисные числа фибоначчиевой системы счисления
    34 21 13 8 5 3 2 1
    37 1 1

    3710 = 34 + 3 = 1*34+0*21+0*13+0*8+0*5+1*3+0*2+0*1= 10000100Fib

    исходное десятичное число Базисные числа фибоначчиевой системы счисления
    21 13 8 5 3 2 1
    25 1 1 1

    2510 = 21 + 3 + 1 = 1*21+0*13+0*8+0*5+1*3+0*2+1*1=100101Fib

    Задание 2. Переведите в десятичную систему числа, записанные в фибоначчиевой системе, например числа: 10010101 и 101010101.

    Вариант решения обучающегося: Перевод числа из фибоначчиевой системы счисления в десятичную:

    неизвестное десятичное число Базисные числа фибоначчиевой системы счисления
    34 21 13 8 5 3 2 1
    ? 1 1 1 1
    неизвестное десятичное число Базисные числа фибоначчиевой системы счисления
    55 34 21 13 8 5 3 2 1
    ? 1 1 1 1 1

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

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *