- Код Фибоначчи
-
Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д.
Число Запись
в ФССКод
Фибоначчи0 0……0 F2=1 1 11 F3=2 10 011 F4=3 100 0011 4 101 1011 F5=5 1000 00011 6 1001 10011 7 1010 01011 F6=8 10000 000011 … Fn-1 101010… …0101011 Fn 10……00 00……011 Fn+1 10……01 10……011 Содержание
Представление натуральных чисел
Любому неотрицательному целому числу можно единственным образом представить через последовательность битов …εk…ε4ε3ε2: , причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: . За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Обоснование
В основе лежит теорема Цеккендорфа — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
Доказательство существования легко провести по индукции. Любое целое число попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого верно неравенство: . Таким образом, a = Fn + a', где , так что разложение числа a' уже не будет содержать слагаемого Fn − 1.
Использование в теории информации
На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (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.
Обобщение на действительные числа
Похожее устройство имеет позиционная система счисления для действительных чисел, основанием которой служит золотое сечение — иррациональное число. Оказывается, что любое действительное число x из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:
где {εk} обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с — золотым сечением отрезка [0,1], вычитанием (если εk=1) и умножением на . Из этого нетрудно видеть, что любое неотрицательное действительное число допускает разложение:
где N таково, что . Разумеется, следует считать что для всех .
Число Представление
через
степени1 1, 2 10,01 3 100,01 4 101,01 5 1000,1001 6 1010,0001 7 10000,0001 8 10001,0001 9 10010,0101 10 10100,0101 11 10101,0101 12 100000,101001 13 100010,001001 14 100100,001001 Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца ) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[1]
Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.
Правила сложения аналогичны показанным выше с той поправкой, что перенос в сторону младших разрядов распространяется без ограничения. В данной системе счисления можно производить и умножение.
Фибоначчиево «произведение»
Для целых чисел и можно определить «произведение»[2]
- ,
формула для которого аналогична формуле умножения двоичных чисел.
Разумеется, данная операция не является настоящим умножением чисел, и выражается[3] формулой:
- где […] — целая часть.
Эта операция обладает ассоциативностью. Впервые на ассоциативность этой операции обратил внимание Дональд Кнут[4]. Следует отметить, что другое «произведение» отличающееся лишь сдвигом на два разряда, уже не будет ассоциативно.
Источники
- Н. Н. Воробьёв Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
- «Коды Фибоначчи», факультет информационных технологий и программирования ИТМО
- «Код Фибоначчи» на Викизнании
Wikimedia Foundation. 2010.