ЕГЭОГЭЕНТ
РУҚА
Тапсырма № 1 · ЕГЭ

Каноническая фибоначчиева жазба

Уникальная жазба числа суммой чисел Фибоначчи без соседних единиц
2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

Каноническая фибоначчиева жазба — это представление положительного целого числа в фибоначчиевой системе счисления, в котором нет двух единиц подряд. Для каждого положительного числа такая жазба единственна.

Каноническая фибоначчиева жазбаНазвание связано с канонической, то есть стандартной и однозначной формой жазбалар.
Запись числа в виде суммы различных чисел Фибоначчи, при которой никакие два использованных соседних веса не идут подряд. В позиционной форме это последовательность цифр 0 и 1 без соседних единиц. Обычно используются веса \(F_2=1\), \(F_3=2\), \(F_4=3\), \(F_5=5\), \(F_6=8\) и далее.

Как устроена жазба

Разряды нумеруют начиная с веса \(F_2=1\). Цифра 1 означает, что соответствующее число Фибоначчи входит в сумму, а цифра 0 — что не входит. Условие каноничности: для любых соседних разрядов \(a_i\) и \(a_{i+1}\) выполняется \(a_i a_{i+1}=0\).

\[N=\sum_{i=2}^{k} a_iF_i,\qquad a_i\in\{0,1\},\qquad a_i a_{i+1}=0\]

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

№
Пример

Число \(10=8+2=F_6+F_3\). Если записывать разряды в порядке весов \(8,5,3,2,1\), получаем \(10010\): единицы стоят у весов 8 и 2, а соседних единиц нет. Поэтому \(10010\) — каноническая фибоначчиева жазба числа 10.

!
Не путайте

Каноническая жазба — не любая последовательность нулей и единиц в фибоначчиевой системе. Например, \(11000\) нарушает условие: две единицы соседствуют. Такую запись нужно преобразовать в каноническую форму; подробности ограничений рассматриваются на странице ограничения фибоначчиевой жазбалар.

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

Какая жазба является канонической?

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

Главное

  • Каноническая фибоначчиева жазба использует цифры 0 и 1 и не содержит соседних единиц.
  • Разряды соответствуют числам Фибоначчи \(1,2,3,5,8,\ldots\).
  • По теореме Цекендорфа каждое положительное число имеет единственную такую жазба.