ЕГЭОГЭ
Задание № 1 · ЕГЭ

Код Фибоначчи

Двоичный код на основе разложения по числам Фибоначчи
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Код Фибоначчи
Для натурального числа сначала находят его разложение в сумму различных чисел Фибоначчи \(F_2=1\), \(F_3=2\), \(F_4=3\), \(F_5=5\) и так далее, причём соседние числа Фибоначчи не используются одновременно. Затем записывают двоичные коэффициенты при этих числах от большего веса к меньшему и дописывают справа единицу. Поэтому корректное кодовое слово заканчивается на \(11\). Код Фибоначчи является способом записи чисел внутри Фибоначчиевой системы счисления.

Как строится код

Для числа \(N\) выбирают наибольшее число Фибоначчи, не превосходящее \(N\), и последовательно вычитают подходящие веса. На соответствующих местах ставят \(1\), на остальных — \(0\). Благодаря правилу выбора единицы не оказываются рядом. После этого к полученной записи добавляют ещё одну единицу справа.

\[N=\sum_{i=2}^{k} b_iF_i,\qquad b_i\in\{0,1\},\qquad b_ib_{i+1}=0;\qquad \operatorname{code}(N)=b_kb_{k-1}\ldots b_2 1\]
№
Пример: код числа 10

Используем веса \(8,5,3,2,1\). Число \(10=8+2\), поэтому коэффициенты слева направо равны \(10010\). Дописываем завершающую единицу: 100101. В основной части нет соседних единиц, а последние две единицы образуют специальное окончание.

!
Не путайте с обычной двоичной записью

Код Фибоначчи не является переводом числа в систему с основанием \(2\). Например, обычная двоичная запись числа \(10\) — \(1010\), а его код Фибоначчи — \(100101\). Кроме того, завершающая единица относится к формату кода, а не к разложению числа.

Проверьте себя

Какой код Фибоначчи соответствует числу \(4\), если веса начинаются с \(1,2,3,5\)?

Главное за минуту

Главное

  • Число представляют суммой непоследовательных чисел Фибоначчи.
  • Коэффициенты записывают нулями и единицами; в основной части соседние единицы запрещены.
  • В конце кода всегда добавляют единицу, поэтому кодовое слово завершается на \(11\).