Изменения
← Новая страница: «'''Фибоначчиева система счисления''' — способ представления [[целое число|цел...»
'''[[Фибоначчи]]ева [[система счисления]]''' — способ представления [[целое число|целых чисел]] через [[числа Фибоначчи]] F<sub>k</sub>.
== Представление натуральных чисел ==
{| align=right class=standard cellpadding=6 style="margin-left: 20px"
!Число
!Запись<br>в ФСС
![[#Использование в теории информации|Код<br>Фибоначчи]]
|-
| 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>11</tt>
|-
| align=right |F<sub>3</sub>=2
| align=right |<tt>10</tt>
| align=left |<tt>011</tt>
|-
| align=right |F<sub>4</sub>=3
| align=right |<tt>100</tt>
| align=left |<tt>0011</tt>
|-
| align=right |4
| align=right |<tt>101</tt>
| align=left |<tt>1011</tt>
|-
| align=right |F<sub>5</sub>=5
| align=right |<tt>1000</tt>
| align=left |<tt>00011</tt>
|-
| align=right |6
| align=right |<tt>1001</tt>
| align=left |<tt>10011</tt>
|-
| align=right |7
| align=right |<tt>1010</tt>
| align=left |<tt>01011</tt>
|-
| align=right |F<sub>6</sub>=8
| align=right |<tt>10000</tt>
| align=left |<tt>000011</tt>
|-
| colspan=3 align=center |…
|-
|F<sub>n</sub>-1
|<tt> 101010</tt>…
| align=right |…<tt>0101011 </tt>
|-
|F<sub>n</sub>
|<tt>10</tt>……<tt>00</tt>
| align=right |<tt>00</tt>……<tt>011</tt>
|-
|F<sub>n</sub>+1
|<tt>10</tt>……<tt>01</tt>
| align=right |<tt>10</tt>……<tt>011</tt>
|}
Любому неотрицательному целому числу <math>a = 0,\ 1,\ 2,\dots</math> можно единственным образом представить через последовательность [[бит]]ов …σ<sub>k</sub>…σ<sub>4</sub>σ<sub>3</sub>σ<sub>2</sub>: <math>a = \sum_k \sigma_k F_k,\ \sigma_k = 0,1</math>, причём последовательность {σ<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\sigma_k=1) \rightarrow (\sigma_{k+1}=0)</math>.
За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].
=== Обоснование ===
В основе лежит ''теорема [[Цеккендорф, Эдуар<!-- это не опечатка, имя французское! --Incnis Mrsi -->|Цеккендорфа]]'' — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <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>.
=== Использование в теории информации ===
На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код (сжатие данных)|универсальный код]] для натуральных чисел (1, 2, 3…), использующий последовательности [[бит]]ов. Поскольку комбинация <tt>11</tt> запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи.
Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз <tt>1</tt> (см. таблицу).
=== Фибоначчиево «произведение» ===
Для <math>a = \sum_k \sigma_k F_k</math> и <math>b = \sum_l \tau_l F_l</math> можно определить «произведение» <math>a\circ b = \sum_{k,l} \sigma_k \tau_l F_{k+l}</math>, формула для которого аналогична формуле умножения двоичных чисел.
Разумеется, данная операция не является настоящим умножением чисел, однако [[Дональд Кнут]] доказал её [[ассоциативность]].
== Обобщение на действительные числа ==
Похожее устройство имеет [[позиционная система счисления]] для [[действительные числа|действительных чисел]], основанием которой служит [[золотое сечение]] <math>\phi = (1 + \sqrt{5})/2</math> — [[иррациональное число]].
{{section-stub}}<!-- надо перевести [[en:Golden_ratio_base]], но я уже ничего не соображаю --Incnis Mrsi -->
[[Категория:Системы счисления]]
[[Категория:Золотое сечение]]
[[en:Fibonacci coding]]
[[eo:Vikipedio:Projekto matematiko/Fibonacci-a kodigo]]
[[fr:Codage de Fibonacci]]
== Представление натуральных чисел ==
{| align=right class=standard cellpadding=6 style="margin-left: 20px"
!Число
!Запись<br>в ФСС
![[#Использование в теории информации|Код<br>Фибоначчи]]
|-
| 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>11</tt>
|-
| align=right |F<sub>3</sub>=2
| align=right |<tt>10</tt>
| align=left |<tt>011</tt>
|-
| align=right |F<sub>4</sub>=3
| align=right |<tt>100</tt>
| align=left |<tt>0011</tt>
|-
| align=right |4
| align=right |<tt>101</tt>
| align=left |<tt>1011</tt>
|-
| align=right |F<sub>5</sub>=5
| align=right |<tt>1000</tt>
| align=left |<tt>00011</tt>
|-
| align=right |6
| align=right |<tt>1001</tt>
| align=left |<tt>10011</tt>
|-
| align=right |7
| align=right |<tt>1010</tt>
| align=left |<tt>01011</tt>
|-
| align=right |F<sub>6</sub>=8
| align=right |<tt>10000</tt>
| align=left |<tt>000011</tt>
|-
| colspan=3 align=center |…
|-
|F<sub>n</sub>-1
|<tt> 101010</tt>…
| align=right |…<tt>0101011 </tt>
|-
|F<sub>n</sub>
|<tt>10</tt>……<tt>00</tt>
| align=right |<tt>00</tt>……<tt>011</tt>
|-
|F<sub>n</sub>+1
|<tt>10</tt>……<tt>01</tt>
| align=right |<tt>10</tt>……<tt>011</tt>
|}
Любому неотрицательному целому числу <math>a = 0,\ 1,\ 2,\dots</math> можно единственным образом представить через последовательность [[бит]]ов …σ<sub>k</sub>…σ<sub>4</sub>σ<sub>3</sub>σ<sub>2</sub>: <math>a = \sum_k \sigma_k F_k,\ \sigma_k = 0,1</math>, причём последовательность {σ<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\sigma_k=1) \rightarrow (\sigma_{k+1}=0)</math>.
За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].
=== Обоснование ===
В основе лежит ''теорема [[Цеккендорф, Эдуар<!-- это не опечатка, имя французское! --Incnis Mrsi -->|Цеккендорфа]]'' — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <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>.
=== Использование в теории информации ===
На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код (сжатие данных)|универсальный код]] для натуральных чисел (1, 2, 3…), использующий последовательности [[бит]]ов. Поскольку комбинация <tt>11</tt> запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи.
Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз <tt>1</tt> (см. таблицу).
=== Фибоначчиево «произведение» ===
Для <math>a = \sum_k \sigma_k F_k</math> и <math>b = \sum_l \tau_l F_l</math> можно определить «произведение» <math>a\circ b = \sum_{k,l} \sigma_k \tau_l F_{k+l}</math>, формула для которого аналогична формуле умножения двоичных чисел.
Разумеется, данная операция не является настоящим умножением чисел, однако [[Дональд Кнут]] доказал её [[ассоциативность]].
== Обобщение на действительные числа ==
Похожее устройство имеет [[позиционная система счисления]] для [[действительные числа|действительных чисел]], основанием которой служит [[золотое сечение]] <math>\phi = (1 + \sqrt{5})/2</math> — [[иррациональное число]].
{{section-stub}}<!-- надо перевести [[en:Golden_ratio_base]], но я уже ничего не соображаю --Incnis Mrsi -->
[[Категория:Системы счисления]]
[[Категория:Золотое сечение]]
[[en:Fibonacci coding]]
[[eo:Vikipedio:Projekto matematiko/Fibonacci-a kodigo]]
[[fr:Codage de Fibonacci]]