Перегляд вихідного коду сторінки Система числення Фібоначчі

'''Система числення''' '''[[Фібоначчі]]'''&nbsp;— [[Система числення|змішана система числення]] для [[Цілі числа|цілих чисел]] на основі [[Числа Фібоначчі|чисел Фібоначчі]] <math>F_2=1</math>, <math>F_3=2</math>, <math>F_4=3</math>, <math>F_5=5</math>, <math>F_6=8</math> і&nbsp;т.&nbsp;д.
{| class="standard" style="margin-left: 20px" align="right"
| colspan="3" |[[Файл:Zeckendorf_representations.svg|320x320пкс]]
|-
! Число
! Запис
у {{Comment|СЧФ|Система числення Фібоначчі}}
! код
Фібоначчі
|-
| align="right" | 0
| align="right" | <tt>0</tt>……<tt>0</tt>
| bgcolor="#999999" |
|-
| align="right" | F<sub>2</sub>=1
| align="right" | <tt>1</tt>
| align="left" | <tt>1<span style="color:#B20080;">1</span></tt>
|-
| align="right" | F<sub>3</sub>=2
| align="right" | <tt>10</tt>
| align="left" | <tt>01<span style="color:#B20080;">1</span></tt>
|-
| align="right" | F<sub>4</sub>=3
| align="right" | <tt>100</tt>
| align="left" | <tt>001<span style="color:#B20080;">1</span></tt>
|-
| align="right" | 4
| align="right" | <tt>101</tt>
| align="left" | <tt>101<span style="color:#B20080;">1</span></tt>
|-
| align="right" | F<sub>5</sub>=5
| align="right" | <tt>1000</tt>
| align="left" | <tt>0001<span style="color:#B20080;">1</span></tt>
|-
| align="right" | 6
| align="right" | <tt>1001</tt>
| align="left" | <tt>1001<span style="color:#B20080;">1</span></tt>
|-
| align="right" | 7
| align="right" | <tt>1010</tt>
| align="left" | <tt>0101<span style="color:#B20080;">1</span></tt>
|-
| align="right" | F<sub>6</sub>=8
| align="right" | <tt>10000</tt>
| align="left" | <tt>00001<span style="color:#B20080;">1</span></tt>
|-
| colspan="3" align="center" | …
|-
| F<sub>n</sub> − 1
| <tt>&nbsp; 101010</tt>…
| align="right" | …<tt>010101<span style="color:#B20080;">1</span> &nbsp;</tt>
|-
| F<sub>n</sub>
| <tt>10</tt>……<tt>00</tt>
| align="right" | <tt>00</tt>……<tt>01<span style="color:#B20080;">1</span></tt>
|-
| F<sub>n</sub> + 1
| <tt>10</tt>……<tt>01</tt>
| align="right" | <tt>10</tt>……<tt>01<span style="color:#B20080;">1</span></tt>
|}

== Подання натуральних чисел ==
Будь-яке невід'ємне ціле число <math>a</math> можна єдиним чином подати послідовністю [[біт]]ів <math>\dots\varepsilon_k\dots\varepsilon_4\varepsilon_3\varepsilon_2</math> (<math>\varepsilon_k \in \{ 0,1\}</math>) так що <math>a = \sum_k \varepsilon_k F_k</math>, причому послідовність <math>\{\varepsilon_k\}</math> містить лише скінченне число одиниць, і не має пар сусідніх одиниць: <math>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>. За винятком останньої властивості, дане подання аналогічне [[Двійкова система числення|двійковій системі числення]] .

=== Обґрунтування ===
В основі лежить ''[[теорема Цекендорфа]]''<ref>{{Cite web |url=http://www.goldenmuseum.com/1601Mathematics_rus.html |title=Эдуард Цекендорф |accessdate=2019-12-15 |archive-date=2017-05-06 |archive-url=https://web.archive.org/web/20170506095256/http://www.goldenmuseum.com/1601Mathematics_rus.html }} {{Webarchive|url=https://web.archive.org/web/20170506095256/http://www.goldenmuseum.com/1601Mathematics_rus.html |date=2017-05-06 }}</ref>: будь-яке невід'ємне ціле число можна єдиним чином подати у вигляді суми деякого набору чисел Фібоначчі з індексами більшими від одиниці, який не містить пар сусідніх чисел Фібоначчі.

Доведення існування легко провести [[Математична індукція|за індукцією]]. Будь-яке ціле число <math>a\ge 1</math> потрапить у проміжок між двома сусідніми числами Фібоначчі, тобто для деякого <math>n\ge 2</math> виконується нерівність: <math>F_n \le a < F_{n+1}</math> . Таким чином, <math>a = F_n + a'</math>, де <math>a'=a-F_n\ <\ F_{n-1}</math>, Так що розкладання числа <math>a'</math> вже не буде містити доданка <math>F_{n-1}</math>.

=== Використання ===

==== Юпана ====
[[Файл:Yupana_1.png|міні| [[Юпана]] ]]
Припускають, що деякі різновиди [[Юпана|юпани]] ([[Абак (рахівниця)|абака]] [[Інки|інків]]) використовували систему числення Фібоначчі, щоб мінімізувати необхідне для обчислень число зерен<ref>{{Cite web|last=Antonio Aimi, Nicolino De Pasquale|url=https://web.archive.org/web/*/http://www.quipus.it/english/Andean%20Calculators.pdf|title=Andean Calculators|accessdate=2009-12-12}}</ref>.

==== У теорії інформації ====
На основі системи числення Фібоначчі будується ''код (кодування) Фібоначчі''&nbsp;— {{Нп|універсальний код||ru|Универсальный код}} для натуральних чисел (1, {{nbsp|1}} 2, {{nbsp|1}} 3 …), який використовує послідовності [[біт]]ів. Оскільки комбінація {{nbsp|1}} <tt>11</tt> заборонена в системі числення Фібоначчі, її можна використовувати як маркер кінця запису.

Для складання коду Фібоначчі за записом числа в системі числення Фібоначчі слід переписати цифри у зворотному порядку (так, що старша одиниця виявляється останнім символом) і приписати в кінці ще раз {{nbsp|1}} <tt>1</tt> (див. таблицю). Тобто, кодова послідовність має вигляд:

: ε<sub>2</sub>ε<sub>3</sub>…ε<sub>''n''</sub><span style="color:#B20080;">1,</span>

де ''n''&nbsp;— номер найстаршого розряду з одиницею.

=== Арифметика ===
Додавання чисел у [[Позиційна система числення|позиційних системах числення]] виконується з використанням [[Додавання#Додавання в інших системах числення|переносу]], що дозволяє усувати наслідки переповнення розряду. Наприклад, у двійковій системі: <span style="background-color: rgb(255,255,51)">01</span> + <span style="background-color: rgb(255,255,51)">01</span> = <span style="background-color: rgb(255,255,51)">0<span style="color:red;">2</span></span> = <span style="background-color: rgb(255,255,51)">10.</span>

У системі числення Фібоначчі ситуація складніша:

* По-перше, вага старших розрядів не є кратною вазі розряду, з якого виконується перенесення. При додаванні двох одиниць в одному розряді потрібне перенесення не тільки вліво, але й управо: <span style="background-color: rgb(102,255,51)">0<span style="color:red;">2</span>00</span> = <span style="background-color: rgb(102,255,51)">1001.</span> При перенесенні у відсутні розряди ε<sub>1</sub> і ε<sub>0</sub> слід пам'ятати, що F<sub>1</sub>=1=F<sub>2</sub> і F<sub>0</sub>=0.
* По-друге, потрібно позбавлятися від сусідніх одиниць: <span style="background-color: rgb(102,255,51)">0<span style="color:red;">11</span></span> = <span style="background-color: rgb(102,255,51)">100.</span> Правило для розкриття двійок є наслідком цієї рівності: <span style="background-color: rgb(102,255,51)">0<span style="color:red;">2</span>00</span> = <span style="background-color: rgb(102,255,51)">0100</span> + <span style="background-color: rgb(102,255,51)">00<span style="color:red;">11</span></span> = <span style="background-color: rgb(102,255,51)">0<span style="color:red;">11</span>1</span> = <span style="background-color: rgb(102,255,51)">1001</span>.

== Узагальнення на дійсні числа ==
{| class="standard" style="margin-right: 20px" align="right"
! Число
! Подання <br/> через степінь {{nbsp|1}}<math>\varphi</math>
|-
| 1
| <tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1</tt>
|-
| 2
| <tt>&nbsp;&nbsp;&nbsp;&nbsp; 10,01</tt>
|-
| 3
| <tt>&nbsp;&nbsp;&nbsp; 100,01</tt>
|-
| 4
| <tt>&nbsp;&nbsp;&nbsp; 101,01</tt>
|-
| 5
| <tt>&nbsp;&nbsp; 1000,1001</tt>
|-
| 6
| <tt>&nbsp;&nbsp; 1010,0001</tt>
|-
| 7
| <tt>&nbsp; 10000,0001</tt>
|-
| 8
| <tt>&nbsp; 10001,0001</tt>
|-
| 9
| <tt>&nbsp; 10010,0101</tt>
|-
| 10
| <tt>&nbsp; 10100,0101</tt>
|-
| 11
| <tt>&nbsp; 10101,0101</tt>
|-
| 12
| <tt>100000,101001</tt>
|-
| 13
| <tt>100010,001001</tt>
|-
| 14
| <tt>100100,001001</tt>
|}
Схоже влаштована [[позиційна система числення]] з [[Ірраціональні числа|ірраціональною]] основою, рівною [[Золотий перетин|золотому перетину]] <math>\varphi = (1 + \sqrt{5})/2</math>.

Будь-яке [[дійсне число]] <math>x</math> з відрізка <math>[0,1]</math> допускає розкладання в [[Степеневий ряд|ряд]] через від'ємні степені золотого перетину:

: <math>x = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\qquad \varepsilon_k \in \{0,1\}</math>

де <math>\left\{ \varepsilon_k \right\}</math> має ту ж властивість відсутності сусідніх одиниць. Коефіцієнти знаходяться послідовним порівнянням <math>x</math> з <math>\varphi^{-1}</math>&nbsp;— золотим перетином відрізка <math>[0,1]</math>, відніманням <math>\varphi^{-1}</math> (якщо <math>\varepsilon_k = 1</math>) і множенням на <math>\varphi</math>. З цього неважко бачити, що будь-яке невід'ємне дійсне число допускає розкладання:

: <math>a = \sum_{k=N-1}^{-\infty} \varepsilon_k \varphi^k\,,</math>

де {{Math|<var>N</var>}} таке, що <math>a < \varphi^N</math>. Зрозуміло, слід вважати, що <math>\varepsilon_k = 0</math> для всіх <math>k \geqslant N</math>.

Ці формули повністю аналогічні формулам для звичайних позиційних систем з цілими основами. Виявляється, що будь-яке невід'ємне ціле число (і, більш загально, кожен невід'ємний елемент [[Кільце (алгебра)|кільця]] <math>{\mathbb Z}+\varphi{\mathbb Z}</math>) має подання лише зі скінченною кількістю одиниць, тобто у вигляді скінченної суми неповторюваних степенів золотого перетину.<ref>{{iw|Система числення на основі золотого перетину||en|Golden ratio base}}</ref>

Аналогія між числами Фібоначчі і степенями золотого перетину заснована на однаковій формі тотожностей:

: <math>F_k = F_{k-1} + F_{k-2}</math>
: <math>\varphi^k = \varphi^{k-1} + \varphi^{k-2}</math>

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

Правила додавання аналогічні показаним [[Система числення Фібоначчі#Арифметика|вище]] з тією поправкою, що перенесення в бік молодших розрядів поширюється без обмеження. У даній системі числення можна виконувати й множення.

== Множення Фібоначчі ==
Для цілих чисел <math>a = \sum_k \varepsilon_k F_k\ </math> і <math>b = \sum_l \zeta_l F_l\ </math> можна визначити «множення»<ref>{{OEIS|A101330}}{{ref-en}}, [[Теорема Цекендорфа]]</ref>

: <math>a \circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l},</math>

аналогічне множенню чисел у [[Двійкова система числення|двійковій системі числення]].

Зрозуміло, що дана операція не є справжнім множенням чисел, і виражається формулою:<ref>[http://www.research.att.com/~njas/sequences/a101330.txt Notes on the Fibonacci circle and arroba products]{{ref-en}}</ref>

: <math>a\circ b = 3 a b - a \lfloor(b+1)\varphi^{-2}\rfloor - b \lfloor(a+1)\varphi^{-2}\rfloor,</math>

де <math>\lfloor\cdot\rfloor</math>&nbsp;— [[Ціла частина числа|ціла частина]], <math>\varphi=\frac{1+\sqrt{5}}{2}</math>&nbsp;— [[золотий перетин]] .

Ця операція має [[асоціативність]], що вперше зауважив [[Дональд Кнут]]<ref>{{Стаття|видання=Applied Mathematics Letters|том=1|номер=1|сторінки=57—60|doi=10.1016/0893-9659(88)90176-0|мова=und|автор=D. E. Knuth|рік=1988}}</ref>. Слід зазначити, що інше «множення» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> відрізняється лише зсувом на два розряди, вже не є асоціативним.

== Примітки ==
{{Reflist|2}}

== Література ==
* {{книга
|автор        = Воробьёв&nbsp;Н.&nbsp;Н.
|назва     = Числа Фибоначчи
|серія        = [[Популярные лекции по математике]]
|видавництво = Наука
|том          =  39
|рік          = 1978
|посилання       = http://ilib.mccme.ru/plm/ann/a06.htm
}}{{ref-ru}}

* {{стаття
|назва     = Система счисления Фибоначчи, реализация на C++
|рік     = 2014
|посилання     = http://www.moveinfo.ru/article/stablelink?page=0000041
|видання     = 
|archiveurl     = https://web.archive.org/web/20141016062442/http://www.moveinfo.ru/article/stablelink?page=0000041
|archivedate     = 2014-10-16
}}{{ref-ru}}
[[Категорія:Стиснення даних]]
[[Категорія:Золотий перетин]]
[[Категорія:Системи числення]]