Изменения

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

Версия от 12:01, 8 октября 2014

340 байт добавлено , 10 лет назад

оформление, викификация

Строка 1: Строка 1: −

'''[[Фибоначчи]]ева система счисления''' — [[смешанная система счисления]] для [[целое число|целых чисел]] на основе [[числа Фибоначчи|чисел Фибоначчи]] F2=1, F3=2, F4=3, F5=5, F6=8 ~~и т~~.д.

+

'''[[Фибоначчи]]ева система счисления''' — [[смешанная система счисления]] для [[целое число|целых чисел]] на основе [[числа Фибоначчи|чисел Фибоначчи]] F2=1, F3=2, F4=3, F5=5, F6=8 и т. д.

{| align=right class=standard style="margin-left: 20px"

| colspan=3 |[[Файл:Zeckendorf representations.png|320px]]

|-

!Число

−

!Запись в ФСС

+

!Запись в {{comment|ФСС|Фибоначчиева система счисления}}

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

|-

Строка 45: Строка 45:

| colspan=3 align=center |…

|-

−

|Fn-1

+

|Fn − 1

|<tt> 101010</tt>…

| align=right |…<tt>0101011 </tt>

Строка 53: Строка 53:

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

|-

−

|Fn+1

+

|Fn + 1

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

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

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

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

−

В основе лежит ''теорема [[Цекендорф, Эдуард|Цекендорфа]]''<ref>[http://www.goldenmuseum.com/1601Mathematics_rus.html Эдуард Цекендорф]</ref> — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора чисел Фибоначчи с индексами больше единицы, не содержащего пар соседних чисел Фибоначчи.

+

В основе лежит ''теорема [[Цекендорф, Эдуард|Цекендорфа]]''<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>.

=== Использование ===

+

==== Юпана ====

[[Файл:Yupana 1.GIF|thumb|Юпана]]

Строка 73: Строка 74:

==== В теории информации ====

−

На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код]] для натуральных чисел (1, 2, 3…), использующий последовательности [[бит]]ов. Поскольку комбинация <tt>11</tt> запрещена в ~~Фибоначчиевой~~ системе счисления, её можно использовать как маркер конца записи.

+

На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код]] для натуральных чисел (1,{{nbsp|1}}2,{{nbsp|1}}3…), использующий последовательности [[бит]]ов. Поскольку комбинация{{nbsp|1}}<tt>11</tt> запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.

−

Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз <tt>1</tt> (см. таблицу). То есть, кодовая последовательность имеет вид:

+

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

: ε2ε3…ε''n''1,

−

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

+

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

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

Строка 82: Строка 84:

В фибоначчиевой системе счисления дело обстоит сложнее:

−

* Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0.

+

* Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0.

* Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.

−

Строка 92: Строка 93:

|-

! Число

−

! Представление через~~ ~~степени <math>\varphi</math>

+

! Представление через степени{{nbsp|1}}<math>\varphi</math>

|-

−

|~~ ~~1

+

| 1

−

|<tt>     1,</tt>

+

|<tt>     1</tt>

|-

−

|~~ ~~2

+

| 2

|<tt>    10,01</tt>

|-

−

|~~ ~~3

+

| 3

|<tt>   100,01</tt>

|-

−

|~~ ~~4

+

| 4

|<tt>   101,01</tt>

|-

−

|~~ ~~5

+

| 5

|<tt>  1000,1001</tt>

|-

−

|~~ ~~6

+

| 6

|<tt>  1010,0001</tt>

|-

−

|~~ ~~7

+

| 7

|<tt> 10000,0001</tt>

|-

−

|~~ ~~8

+

| 8

|<tt> 10001,0001</tt>

|-

−

|~~ ~~9

+

| 9

|<tt> 10010,0101</tt>

|-

Строка 139: Строка 140:

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

−

Любое [[вещественное число]] ''x'' из отрезка [0,1] допускает разложение в [[степенной ряд|ряд]] через отрицательные степени золотого сечения:

+

Любое [[вещественное число]] {{math|''x''}} из отрезка [0,1] допускает разложение в [[степенной ряд|ряд]] через отрицательные степени золотого сечения:

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

−

где {ε<~~sub~~>k</~~sub~~>} обладает тем же свойством отсутствия соседних единиц.

+

где <math>\left\{ \varepsilon_k \right\}</math> обладает тем же свойством отсутствия соседних единиц.

−

Коэффициенты находятся последовательным сравнением ''x'' с <math>\varphi^{-1}</math> — золотым сечением отрезка [0,1], вычитанием <math>\varphi^{-1}</math> (если ε<~~sub~~>k</~~sub~~>=1) и умножением на <math>\varphi</math>.

+

Коэффициенты находятся последовательным сравнением {{math|''x''}} с <math>\varphi^{-1}</math> — золотым сечением отрезка [0,1], вычитанием <math>\varphi^{-1}</math> (если <math>\varepsilon_k = 1</math>) и умножением на <math>\varphi</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>\varepsilon_k = 0</math> для всех <math>k \ge N</math>.

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

−

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

+

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

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

−

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

+

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

−

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

+

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

+

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

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

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

Строка 161: Строка 163:

== Фибоначчиево умножение ==

−

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

+

Для целых чисел <math>a = \sum_k \varepsilon_k F_k\ </math> и <math>b = \sum_l \zeta_l F_l\ </math> можно определить «умножение»<ref>{{OEIS|A101330}}{{ref-en}}, {{iw|Теорема Цекендорфа|||Zeckendorf’s theorem}}</ref>

−

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

+

: <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>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> — [[целая часть]], <math>\varphi=\frac{1+\sqrt{5}}{2}</math> — [[золотое сечение]].

+

где <math>\lfloor\cdot\rfloor</math> — [[целая часть]], <math>\varphi=\frac{1+\sqrt{5}}{2}</math> — [[золотое сечение]].

−

Эта операция обладает [[~~Ассоциативность (математика)~~|ассоциативностью]], на что впервые обратил внимание [[Дональд Кнут]].<ref>{{cite journal |author=D. E. Knuth |title=Fibonacci multiplication |journal=Applied Mathematics Letters |volume=1 |issue=1 |year=1988 |pages=57-60 |doi=10.1016/0893-9659(88)90176-0}}</ref>

+

Эта операция обладает [[Ассоциативная операция|ассоциативностью]], на что впервые обратил внимание [[Кнут, Дональд Эрвин|Дональд Кнут]]<ref>{{cite journal |author=D. E. Knuth |title=Fibonacci multiplication |journal=Applied Mathematics Letters |volume=1 |issue=1 |year=1988 |pages=57-60 |doi=10.1016/0893-9659(88)90176-0}}</ref>. Следует отметить, что другое «произведение» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> отличающееся лишь сдвигом на два разряда, уже не является

−

Следует отметить, что другое «произведение» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> отличающееся лишь сдвигом на два разряда, уже не является

Строка 179: Строка 180:

== Литература ==

* {{книга

−

|автор = Н. Н. ~~Воробьёв~~

+

|автор = Воробьёв Н. Н.

−

|заглавие = Числа Фибоначчи

+

|заглавие = Числа Фибоначчи

−

|серия = [[Популярные лекции по математике]]

+

|серия = [[Популярные лекции по математике]]

|издательство = Наука

−

|том = 39

+

|том = 39

−

|год = 1978

+

|год = 1978

−

|ссылка = http://ilib.mccme.ru/plm/ann/a06.htm

+

|ссылка = http://ilib.mccme.ru/plm/ann/a06.htm

}}

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

w>DmitTrix

Изменения

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

Версия от 12:01, 8 октября 2014

Навигация

Поиск