Фибоначчиева система счисления
Фибоначчиева система счисления — позиционная система счисления для целых чисел на основе чисел Фибоначчи 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} содержит лишь конечное число единиц, и не имеет пар соседних единиц: . За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Обоснование
В основе лежит теорема Цеккендорфа — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
Доказательство существования легко провести по индукции. Любое целое число попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого верно неравенство: . Таким образом, , где , так что разложение числа уже не будет содержать слагаемого .
Использование в теории информации
На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу).
Обобщение на действительные числа
Похожее устройство имеет позиционная система счисления для действительных чисел, основанием которой служит золотое сечение — иррациональное число. Оказывается, что любое действительное число a из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения: где {εk} обладает тем же свойством отсутствия соседних единиц. Из этого нетрудно видеть, что любое неотрицательное действительное число допускает разложение: где N таково, что . Разумеется, следует считать что для .
Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца ) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.
Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств: позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется. Шаблон:Section-stub
Фибоначчиево «произведение»
Для целых чисел и можно определить «произведение»[1] формула для которого аналогична формуле умножения двоичных чисел.
Разумеется, данная операция не является настоящим умножением чисел, и выражается[2] формулой: где […] — целая часть.
Эта операция обладает ассоциативностью. Можно видеть, что формула «произведения» соответствует настоящему перемножению выражений вида .
Впервые на ассоциативность этой операции обратил внимание Дональд Кнут. Следует отметить, что другое «произведение» отличающееся лишь сдвигом на два разряда, уже не будет ассоциативно, поскольку… Шаблон:Section-stub
Источники
- «Коды Фибоначчи», факультет информационных технологий и программирования ИТМО
- «Код Фибоначчи» на Викизнании
en:Fibonacci coding eo:Vikipedio:Projekto matematiko/Fibonacci-a kodigo fr:Codage de Fibonacci