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

Введение и мотивация

Фибоначчиева система счисления — необычная позиционная система, в которой «разряды» связаны с числами Фибоначчи, а не с степенями некоторого фиксированного основания. Такая система интересна как с теоретической точки зрения (связь с уникальной разложимостью чисел), так и с практической — для задач кодирования и некоторых областей информатики.

Основой системы служит последовательность Фибоначчи, определяемая рекуррентным соотношением и начальными условиями, которые мы будем принимать в специальной форме для удобства записи. Формула для этой последовательности записывается как $F_n = F_{n-1} + F_{n-2},\quad F_1 = 1,\; F_2 = 2$.

Система счисления - способ представления целых чисел при помощи фиксированного набора символов (цифр) и правила их взвешивания по позициям; в фибоначчиевой системе веса позиций задаются числами Фибоначчи.

Последовательность Фибоначчи для системы счисления

В контексте фибоначчиевой системы удобно использовать вариант последовательности, начинающийся с двух первых значений, принятых как единица и две единицы в сумме, то есть первые два члена берутся так, чтобы любая запись была однозначной. Именно эту последовательность мы использовали в $F_n = F_{n-1} + F_{n-2},\quad F_1 = 1,\; F_2 = 2$.

Для наглядности часто приводят начальные члены последовательности, перечислив несколько первых значений, чтобы увидеть, какие веса позиций будут в системе. Список таких начальных членов можно записать так: $F_1=1,\;F_2=2,\;F_3=3,\;F_4=5,\;F_5=8,\;F_6=13,\;F_7=21,\;F_8=34,\;F_9=55,\;F_{10}=89,\;F_{11}=144$.

Числа Фибоначчи (в варианте для записи) - последовательность положительных целых чисел, задаваемая рекуррентным соотношением и выбранными начальными условиями; в фибоначчиевой системе счисления эти числа используются как веса для позиций.

Определение фибоначчиевой записи и теорема Цекендорфа

Фибоначчиева запись числа — это разложение положительного целого числа в сумму различных чисел из выбранной последовательности Фибоначчи с коэффициентами 0 или 1. Формально такое разложение можно записать как $N=\displaystyle\sum_{k=1}^m a_k F_k,\quad a_k\in\{0,1\}$.

Главное условие, которое обеспечивает однозначность разложения в этой системе — запрет на использование двух соседних чисел Фибоначчи одновременно. Это условие формализуется как $a_k\,a_{k+1}=0\quad\text{для всех }k$ и означает, что в векторе коэффициентов никогда не встречаются две единицы подряд.

Теорема Цекендорфа - утверждение о том, что любое положительное целое число представимо единственным образом как сумма неповторяющихся чисел Фибоначчи без соседних членов; эта теорема лежит в основе фибоначчиевой системы счисления.

Алгоритм записи числа (жадный алгоритм)

Практический алгоритм получения фибоначчиевой записи числа прост: последовательно вычитают наибольшие возможные числа Фибоначчи. Первый шаг — выбрать наибольший член последовательности, не превосходящий данное число. Этот выбор формально описывается неравенством $F_k\le N< F_{k+1}$.

После выбора такого члена алгоритм заменяет исходное число на разность с выбранным членом и повторяет процедуру для остатка. Операция вычитания на очередном шаге выглядит как $N:=N-F_k$, и процесс завершается, когда остаток становится равным нулю.

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

Примеры и пошаговый разбор

После того как найдено разложение в виде суммы, удобно представить его в виде двоичного вектора коэффициентов по убыванию индексов Фибоначчи — такая строка называют фибоначчиевой записью. Для примера со ста это даёт запись $100=(1000010100)_F$.

Если развернуть эту запись в сумму по индексам и по определению последовательности Фибоначчи, то проверка сходится: $(1000010100)_F=1\cdot F_{10}+0\cdot F_9+0\cdot F_8+0\cdot F_7+0\cdot F_6+1\cdot F_5+0\cdot F_4+1\cdot F_3+0\cdot F_2+0\cdot F_1=89+8+3$ — то есть сумма весов действительно даёт исходное число.

Арифметика в фибоначчиевой системе

Арифметические операции в фибоначчиевой системе удобнее всего выполнять через перевод в привычную десятичную систему, выполнение операции и обратный перевод записи в фибоначчиев вид с применением жадного алгоритма. Сам факт суммирования записей можно обозначить простой формулой суммы двух чисел и получения результата: $N_{\text{sum}}=N_1+N_2$.

При попытке выполнять сложение «на местах» возникают промежуточные состояния с подряд идущими единицами. Для их устранения используют правила перерасчёта, эквивалентные свойствам последовательности Фибоначчи: блоки единиц приводятся к корректной форме, заменяясь более старшими разрядами, пока не будут соблюдены условия теоремы Цекендорфа.

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

Свойства, оценка длины записи и приложения

Длина фибоначчиевой записи, то есть количество используемых разрядов m, связана с порядком величины представляемого числа. Приближённо это соотношение можно выражать через логарифм по основанию золотого сечения, и оценка выглядит так: $m\approx\log_{\varphi}N,\quad \varphi=\dfrac{1+\sqrt{5}}{2}$.

Благодаря уникальности представления и свойствам плотности чисел Фибоначчи, такие системы используются в некоторых схемах кодирования без префиксных кодов, а также в задачах комбинаторики, где запрещены соседние единицы. Ещё одна область применения — изучение автоматов и слов над алфавитом $N=\displaystyle\sum_{k=1}^m a_k F_k,\quad a_k\in\{0,1\}$ с ограничением $a_k\,a_{k+1}=0\quad\text{для всех }k$, что даёт интересные комбинаторные последовательности.

Задачи для практики

Для отработки навыков предложите ученикам: найти фибоначчиевы записи для набора небольших чисел, проверить корректность записи для произвольной строки нулей и единиц, и реализовать на бумаге жадный алгоритм для заданного числа. В абстрактном виде сами задачи формулируются через представления вида $N=\displaystyle\sum_{k=1}^m a_k F_k,\quad a_k\in\{0,1\}$ и условие $a_k\,a_{k+1}=0\quad\text{для всех }k$.

Дополнительный наводящий вопрос: как быстро определить старший значимый разряд для большого числа? Ответ связывается с оценкой длины представления и выражением через золотое сечение, см. $m\approx\log_{\varphi}N,\quad \varphi=\dfrac{1+\sqrt{5}}{2}$.