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

Материал из ТолВИКИ
Перейти к: навигация, поиск

Автор-составитель : Бетева


Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д. Последовательность Фибоначчи определяется следующим образом:

Ф0.png Ф1.png Фн.png

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

История

Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci) (также известный как Леонардо Пизанский (Leonardo Pisano)). Однако именно благодаря математику 19 века Люка (Lucas) название "числа Фибоначчи" стало общеупотребительным. Впрочем, индийские математики упоминали числа этой последовательности ещё раньше: Гопала (Gopala) до 1135 г., Хемачандра (Hemachandra) — в 1150 г.

Свойства

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

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

   * Соотношение Кассини: 
     Кассини.png
   * Правило "сложения": 
     Сложение.png
   * Из предыдущего равенства при k = n вытекает: 
     Из предыд равенства.png
   * НОД-равенство: 
     Нод равенство.png

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

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

Суммчислфиб.png

где k1 >= k2+2, k2 >= k3+2, ... , kr >= 2 (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

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

Отсюдаслед.png Отсюдаслед2.png Отсюдаслед3.png

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

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

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

В теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системе счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:

   ε2ε3…εn1,

где n — номер самого старшего разряда с единицей.

Арифметика

Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.

В фибоначчиевой системе счисления дело обстоит сложнее:

   * Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что 

F1=1=F2 и F0=0.

   * Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 

0200 = 0100 + 0011 = 0111 = 1001.

Источники: [1] [2]

Личные инструменты
наши друзья
http://аудиохрестоматия.рф/