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

Числа Фібоначчі можуть складати основу так званої «фібоначчівської» системи числення, тобто представлення будь-якого числа, а у вигляді деякої послідовності цифр ц1ц2ц3… цn. Ця послідовність може бути отримана наступним (індуктивним) чином.

Віднімемо від заданого числа, а = а0 найбільше з не переважаючих його чисел Фібоначчі u й напишемо цифру ц1 = 1 і різницю а1 = а0 — un будемо вважати це першим кроком нашої побудови.

Припустимо, що k кроків побудови уже зроблені, в результаті чого з`явилася послідовність цифр:

ц 1… цk (5).

що складається з нулів та одиниць, а також деяке число a. Тоді k + 1 крок побудови буде зводитись до наступного: порівняємо число, а с числом Фібоначчі un-k, і якщо виявиться, аk? un-k, то припишемо до послідовності (5) цk+1 = 0 і фіксуємо число аk+1 = аk, а якщо буде аk? un-k, то припишемо до (5) цk+1 = 1 і положимо аk+1 = аk — un-k. Ми виконаємо n — 1 кроків цього процесу, в результаті чого, очевидно, прийдемо до n — 1- членної послідовності (5) і числу аn-1 = 0.

Фактично описаний процес являє собою послідовне виділення з числа, а доданків рівним найбільшим можливим числам Фібоначчі, тобто представлення, а у вигляді суми різних чисел Фібоначчі.

Остаточно відповідна числу, а послідовність (5) буде називатися його фібоначчієвим записом і позначатися через, Ц (а). Складові Ц (а) нулі і одиниці назвемо фібоначчієвими цифрами числа а. Ясно, що якщо Ц (а) = ц1… цn-1, то:

а = un ц1 + un-1 ц2 +… + u2 цn-1 (6).

Пояснимо сказане на прикладі. Нехай, а = 19. Тоді:

un = 13 (n = 7), ц = 1, a1 = 19 — 13 = 6.

u6 = 8 > a1 ц = 0, a2 = a1 = 6.

u5 = 5? a2 ц = 1, a3 = 6 — 5 = 1.

u4 = 3 > a3 ц = 0, a4 = a3 = 1.

u3 = 2 > a4 ц = 0, a5 = a4 = 1.

u2 = 1? a5 ц = 1, a6 = 1 — 1 = 0.

Таким чином, Ц (19) = 101 001, і 19 = u7 + u5 + u2.

Зрозуміло, що кожне число, а має єдиний фібоначчієвий запис Ц (а). Проте не будь-яка послідовність, що починається з одиниці і складається з одиниць і нулів має бути фібоначчієвим записом Ц (а) для деякого числа а. Наприклад в Ц (а) не можуть стояти дві одиниця підряд.

Дійсно, нехай в Ц (а) дві одиниці зустрічаються підряд після деякого нуля: цk = 0, цk+1 = цk+2 = 1. Це значить, що:

ak-1? un-k+1, (7).

ak-1 = ak, ak — un-k = ak+1, ak+1-? un-k-1.

Але отримане складання усіх складових другого рядка дає нам:

ak-1? un-k + un-k-1 = un-k+1.

що суперечить (7).

Отже, будь-яка послідовність із n — 1 нулів і одиниць, що починається з одиниці і не має двох одиниць підряд, є фібоначчієвим запис Ц (а) деякого числа а, для котрого:

un? a? un+1. (8).

Фібоначчієвий запис числа нагадує двійкову систему числення з тією різницею, що нулі і одиниці в двійковій системі відповідають числам, які не можуть бути сумою попередніх. Також спостерігається деяка схожість с з кодом степенів числа два. Ці коди також складаються з одиниць та нулів, проте не мають обмеження на положення одиниць. Проблема шифрування та кодування інформації в часи новітніх технологій особливо гостро стоять перед науковцями, тому вивчення даного представлення числа буде корисним будь-якому комп’ютерному спеціалісту. Вивчення даного питання у школі ненав’язливо розширить представлення дітей про системи числення, даючи зрозуміти, що не тільки десятковою системою багата математика.