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

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

Представление чисел через числа Фибоначчи без соседних слагаемых

2 мин чтенияСложность: Обновлено 29 сентября 2026

Фибоначчиева система счисления — способ записывать натуральные числа как сумму различных чисел Фибоначчи, причём соседние числа Фибоначчи одновременно не используются. Такая запись использует только цифры 0 и 1.

Фибоначчиева система счисленияНазвание связано с числами Фибоначчи, хотя для удобства записи последовательность начинают с $F_2=1$, $F_3=2$.

Система представления натуральных чисел в виде суммы чисел последовательности $1, 2, 3, 5, 8, 13, \ldots$, где каждое слагаемое используется не более одного раза, а два соседних числа последовательности не могут входить в сумму одновременно. В записи это означает, что среди цифр 0 и 1 нет двух единиц, стоящих рядом.

В отличие от обычной позиционной системы, значение цифры здесь определяется не степенью одного основания, а соответствующим числом Фибоначчиевой последовательности. Разряды слева направо соответствуют весам $\ldots, 13, 8, 5, 3, 2, 1$. Обычно используют только каноническую запись: одну из единиц, соответствующих двум одинаковым значениям $1$, не выделяют отдельно.

\[N = a_kF_k + a_{k-1}F_{k-1} + \cdots + a_2F_2, \qquad a_i\in\{0,1\},\quad a_i a_{i+1}=0\]

Условие $a_i a_{i+1}=0$ означает, что соседние цифры не могут быть одновременно равны 1. Например, запись $10101$ читается по весам $8,5,3,2,1$ как $1\cdot8+0\cdot5+1\cdot3+0\cdot2+1\cdot1=12$.

№

Пример записи

Число $10$ представляется так: $10=8+2$. Поэтому его фибоначчиева запись по весам $8,5,3,2,1$ равна $10010$. Единицы не соседствуют, значит, запись допустима.

Не путайте с кодом Фибоначчи

Фибоначчиева система счисления описывает математическое представление числа. Код Фибоначчи — это способ закодировать такую запись, обычно добавляя завершающую единицу для обнаружения конца кода. Эти понятия связаны, но не совпадают.

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

Какая запись допустима в фибоначчиевой системе?

Существование и единственность такой записи для каждого натурального числа обосновывает теорема Цекендорфа. Подробные правила построения рассматриваются в статье о канонической фибоначчиевой записи.

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

Главное

Весами разрядов служат числа $1,2,3,5,8,\ldots$.
В записи используются только 0 и 1, причём соседние единицы запрещены.
Фибоначчиева система и код Фибоначчи — связанные, но разные понятия.