Изменения

Фибоначчиева система счисления (править)

Версия от 22:05, 27 января 2010

228 байт добавлено , 15 лет назад

перенос (арифметика) + →‎Обобщение на действительные числа: некоторые ориссные мысли под комментарием

Строка 5: Строка 5:

!Число

!Запись в ФСС

−

![[#~~Использование в~~ теории информации|Код Фибоначчи]]

+

![[#В теории информации|Код Фибоначчи]]

|-

| align=right |0

Строка 63: Строка 63:

=== Обоснование ===

−

В основе лежит ''теорема [[~~Цеккендорф~~, ~~Эдуар~~|~~Цеккендорфа~~]]'' — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.

+

В основе лежит ''теорема [[Цекендорф, Эдуард|Цекендорфа]]''<ref>[http://www.goldenmuseum.com/1601Mathematics_rus.html Эдуард Цекендорф]</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>.

Строка 79: Строка 79:

=== Арифметика ===

−

При сложении чисел в позиционных системах счисления приходится выполнять ''перенос'', то есть устранять последствия ~~[[арифметическое переполнение|~~переполнения]] разряда. Например, в двоичной системе: 01 + 01 = 02 = 10. В фибоначчиевой системе дело обстоит намного сложнее. Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только вправо, но и влево: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0. Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.

+

При сложении чисел в позиционных системах счисления приходится выполнять [[перенос (арифметика)|перенос]], то есть устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10. В фибоначчиевой системе дело обстоит намного сложнее. Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только вправо, но и влево: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0. Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.

Строка 146: Строка 146:

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

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

−

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

+

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

+

Тут надо уточнить, на самом деле связь будет с некоторыми оговорками и с точностью до множителя √5 или что-то такое.

+

Думаю, что должна быть связь с формулой секцией ниже, поскольку то умножение действует по той же логике, что и перемножение чисел в Φ-системе.

+

--Incnis Mrsi -->

Правила сложения аналогичны показанным [[#Арифметика|выше]] с той поправкой, что перенос в сторону младших разрядов распространяется без ограничения. В данной системе счисления можно производить и умножение.

Анонимный участник

w>Incnis Mrsi