Изменения

'''[[Фибоначчи]]ева [[система счисления]]''' — способ представления [[целое число|целых чисел]] через [[числа Фибоначчи]] F_k.

'''[[Фибоначчи]]ева система счисления''' — [[позиционная система счисления]] для [[целое число|целых чисел]] на основе [[числа Фибоначчи|чисел Фибоначчи]] F₂=1, F₃=2, F₄=3, F₅=5, F₆=8 и т.д.

== Представление натуральных чисел ==

== Представление натуральных чисел ==

  |<tt>10</tt>……<tt>01</tt>

  |<tt>10</tt>……<tt>01</tt>

  | align=right |<tt>10</tt>……<tt>011</tt>

  | align=right |<tt>10</tt>……<tt>011</tt>

  |}

  |}

Любому неотрицательному целому числу <math>a = 0,\ 1,\ 2,\dots</math> можно единственным образом представить через последовательность [[бит]]ов …σ_k…σ₄σ₃σ₂: <math>a = \sum_k \sigma_k F_k,\ \sigma_k = 0,1</math>, причём последовательность {σ_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\sigma_k=1) \rightarrow (\sigma_{k+1}=0)</math>.

Любому неотрицательному целому числу <math>a = 0,\ 1,\ 2,\dots</math> можно единственным образом представить через последовательность [[бит]]ов …ε_k…ε₄ε₃ε₂: <math>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1</math>, причём последовательность {ε_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>.

За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].

За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].

Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз <tt>1</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>\varphi = (1 + \sqrt{5})/2</math> — [[иррациональное число]].

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

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

где ''N'' таково, что <math>a < \varphi^N</math>.

Разумеется, следует считать что <math>\varepsilon_k = 0</math> для <math>k \ge N</math>.

 

Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент [[кольцо (алгебра)|кольца]] <math>{\mathbb Z}+\varphi{\mathbb Z}</math>) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.<!-- тут хорошо бы найти источник -->

Разумеется, данная операция не является настоящим умножением чисел, однако [[Дональд Кнут]] доказал её [[ассоциативность]].

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

позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.<!-- тут надо уточнить, на самом деле связь будет с некоторыми оговорками и с точностью до множителя √5 или что-то такое  --Incnis Mrsi -->

== Обобщение на действительные числа ==

== Фибоначчиево «произведение» ==

Похожее устройство имеет [[позиционная система счисления]] для [[действительные числа|действительных чисел]], основанием которой служит [[золотое сечение]] <math>\phi = (1 + \sqrt{5})/2</math> — [[иррациональное число]].

Для целых чисел <math>a = \sum_k \varepsilon_k F_k\ </math> и <math>b = \sum_l \zeta_l F_l\ </math> можно определить «произведение»<ref>{{OEIS2C|A101330}}, [[:en:Zeckendorf's theorem]]{{ref-en}}</ref>

формула для которого аналогична формуле умножения двоичных чисел.

 

Разумеется, данная операция не является настоящим умножением чисел, и выражается<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 [\varphi^{-2}(b+1)] -  b [\varphi^{-2}(a+1)]\ ,</math> где […] — [[целая часть]].

 

Эта операция обладает [[ассоциативность]]ю. Можно видеть, что формула «произведения» соответствует настоящему перемножению выражений вида <math>a = \sum_k \varepsilon_k \varphi^k\,,k=2, 3\dots</math>.

 

Впервые на ассоциативность этой операции обратил внимание [[Дональд Кнут]].

{{section-stub}}<!-- надо перевести [[en:Golden_ratio_base]], но я уже ничего не соображаю --Incnis Mrsi -->

{{rq|source}}

* [http://rain.ifmo.ru/cat/view.php/theory/coding/integer-2005#Fcode «Коды Фибоначчи»], факультет информационных технологий и программирования [[ИТМО]]

* [http://www.wikiznanie.ru/ru-wz/index.php/Код_Фибоначчи «Код Фибоначчи»] на Викизнании

{{примечания}}

[[Категория:Системы счисления]]

[[Категория:Системы счисления]]