Фибоначчиева система счисления
Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т. д.
| ||
| Число | Запись в ФСС |
Код Фибоначчи |
|---|---|---|
| 0 | 0……0 | |
| F2=1 | 1 | 11 |
| F3=2 | 10 | 011 |
| F4=3 | 100 | 0011 |
| 4 | 101 | 1011 |
| F5=5 | 1000 | 00011 |
| 6 | 1001 | 10011 |
| 7 | 1010 | 01011 |
| F6=8 | 10000 | 000011 |
| … | ||
| Fn − 1 | 101010… | …0101011 |
| Fn | 10……00 | 00……011 |
| Fn + 1 | 10……01 | 10……011 |
Содержание
Представление натуральных чисел
Любое неотрицательное целое число <math>a</math> можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 (<math>\varepsilon_k \in \{ 0,1\}</math>) так, что <math>a = \sum_k \varepsilon_k F_k</math>, причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Обоснование
В основе лежит теорема Цекендорфа[1] — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора чисел Фибоначчи с индексами больше единицы, не содержащего пар соседних чисел Фибоначчи.
Доказательство существования легко провести по индукции. Любое целое число <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>.
Использование
Юпана
Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен[2].
В теории информации
На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.
Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:
- ε2ε3…εn1,
где n — номер самого старшего разряда с единицей.
Арифметика
Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.
В фибоначчиевой системе счисления дело обстоит сложнее:
- Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0.
- Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.
 |
Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.
|
Обобщение на вещественные числа
| Число | Представление через степени <math>\varphi</math> |
|---|---|
| 1 | 1 |
| 2 | 10,01 |
| 3 | 100,01 |
| 4 | 101,01 |
| 5 | 1000,1001 |
| 6 | 1010,0001 |
| 7 | 10000,0001 |
| 8 | 10001,0001 |
| 9 | 10010,0101 |
| 10 | 10100,0101 |
| 11 | 10101,0101 |
| 12 | 100000,101001 |
| 13 | 100010,001001 |
| 14 | 100100,001001 |
Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению <math>\varphi = (1 + \sqrt{5})/2</math>.
Любое вещественное число x из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:
- <math>x = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\qquad \varepsilon_k \in \{0,1\}</math>
где <math>\left\{ \varepsilon_k \right\}</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 \geqslant N</math>.
Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца <math>{\mathbb Z}+\varphi{\mathbb Z}</math>) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[3]
Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
- <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> можно определить «умножение»[4]
- <math>a \circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l},</math>
которое аналогично умножению чисел в двоичной системе счисления.
Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой:[5]
- <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> — золотое сечение.
Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут[6]. Следует отметить, что другое «произведение» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.
|
Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.
|
Напишите отзыв о статье "Фибоначчиева система счисления"
Примечания
- ↑ [www.goldenmuseum.com/1601Mathematics_rus.html Эдуард Цекендорф]
- ↑ Antonio Aimi, Nicolino De Pasquale. [web.archive.org/web/*/www.quipus.it/english/Andean%20Calculators.pdf Andean Calculators]. Проверено 12 декабря 2009.
- ↑ Система счисления на основе золотого сечения[en]
- ↑ последовательность A101330 в OEIS (англ.), Теорема Цекендорфа
- ↑ [www.research.att.com/~njas/sequences/a101330.txt Notes on the Fibonacci circle and arroba products] (англ.)
- ↑ D. E. Knuth (1988). «Fibonacci multiplication». Applied Mathematics Letters 1 (1): 57-60. DOI:10.1016/0893-9659(88)90176-0.
Литература
- Воробьёв Н. Н. [ilib.mccme.ru/plm/ann/a06.htm Числа Фибоначчи]. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
- [www.moveinfo.ru/article/stablelink?page=0000041 Система счисления Фибоначчи, реализация на C++]. — 2014.
Отрывок, характеризующий Фибоначчиева система счисления
Но в то же мгновение, как он умер, князь Андрей вспомнил, что он спит, и в то же мгновение, как он умер, он, сделав над собою усилие, проснулся.«Да, это была смерть. Я умер – я проснулся. Да, смерть – пробуждение!» – вдруг просветлело в его душе, и завеса, скрывавшая до сих пор неведомое, была приподнята перед его душевным взором. Он почувствовал как бы освобождение прежде связанной в нем силы и ту странную легкость, которая с тех пор не оставляла его.
Когда он, очнувшись в холодном поту, зашевелился на диване, Наташа подошла к нему и спросила, что с ним. Он не ответил ей и, не понимая ее, посмотрел на нее странным взглядом.
Это то было то, что случилось с ним за два дня до приезда княжны Марьи. С этого же дня, как говорил доктор, изнурительная лихорадка приняла дурной характер, но Наташа не интересовалась тем, что говорил доктор: она видела эти страшные, более для нее несомненные, нравственные признаки.
С этого дня началось для князя Андрея вместе с пробуждением от сна – пробуждение от жизни. И относительно продолжительности жизни оно не казалось ему более медленно, чем пробуждение от сна относительно продолжительности сновидения.
Ничего не было страшного и резкого в этом, относительно медленном, пробуждении.
Последние дни и часы его прошли обыкновенно и просто. И княжна Марья и Наташа, не отходившие от него, чувствовали это. Они не плакали, не содрогались и последнее время, сами чувствуя это, ходили уже не за ним (его уже не было, он ушел от них), а за самым близким воспоминанием о нем – за его телом. Чувства обеих были так сильны, что на них не действовала внешняя, страшная сторона смерти, и они не находили нужным растравлять свое горе. Они не плакали ни при нем, ни без него, но и никогда не говорили про него между собой. Они чувствовали, что не могли выразить словами того, что они понимали.
Они обе видели, как он глубже и глубже, медленно и спокойно, опускался от них куда то туда, и обе знали, что это так должно быть и что это хорошо.
Его исповедовали, причастили; все приходили к нему прощаться. Когда ему привели сына, он приложил к нему свои губы и отвернулся, не потому, чтобы ему было тяжело или жалко (княжна Марья и Наташа понимали это), но только потому, что он полагал, что это все, что от него требовали; но когда ему сказали, чтобы он благословил его, он исполнил требуемое и оглянулся, как будто спрашивая, не нужно ли еще что нибудь сделать.
Когда происходили последние содрогания тела, оставляемого духом, княжна Марья и Наташа были тут.
– Кончилось?! – сказала княжна Марья, после того как тело его уже несколько минут неподвижно, холодея, лежало перед ними. Наташа подошла, взглянула в мертвые глаза и поспешила закрыть их. Она закрыла их и не поцеловала их, а приложилась к тому, что было ближайшим воспоминанием о нем.
«Куда он ушел? Где он теперь?..»
Когда одетое, обмытое тело лежало в гробу на столе, все подходили к нему прощаться, и все плакали.
Николушка плакал от страдальческого недоумения, разрывавшего его сердце. Графиня и Соня плакали от жалости к Наташе и о том, что его нет больше. Старый граф плакал о том, что скоро, он чувствовал, и ему предстояло сделать тот же страшный шаг.
Наташа и княжна Марья плакали тоже теперь, но они плакали не от своего личного горя; они плакали от благоговейного умиления, охватившего их души перед сознанием простого и торжественного таинства смерти, совершившегося перед ними.
Для человеческого ума недоступна совокупность причин явлений. Но потребность отыскивать причины вложена в душу человека. И человеческий ум, не вникнувши в бесчисленность и сложность условий явлений, из которых каждое отдельно может представляться причиною, хватается за первое, самое понятное сближение и говорит: вот причина. В исторических событиях (где предметом наблюдения суть действия людей) самым первобытным сближением представляется воля богов, потом воля тех людей, которые стоят на самом видном историческом месте, – исторических героев. Но стоит только вникнуть в сущность каждого исторического события, то есть в деятельность всей массы людей, участвовавших в событии, чтобы убедиться, что воля исторического героя не только не руководит действиями масс, но сама постоянно руководима. Казалось бы, все равно понимать значение исторического события так или иначе. Но между человеком, который говорит, что народы Запада пошли на Восток, потому что Наполеон захотел этого, и человеком, который говорит, что это совершилось, потому что должно было совершиться, существует то же различие, которое существовало между людьми, утверждавшими, что земля стоит твердо и планеты движутся вокруг нее, и теми, которые говорили, что они не знают, на чем держится земля, но знают, что есть законы, управляющие движением и ее, и других планет. Причин исторического события – нет и не может быть, кроме единственной причины всех причин. Но есть законы, управляющие событиями, отчасти неизвестные, отчасти нащупываемые нами. Открытие этих законов возможно только тогда, когда мы вполне отрешимся от отыскиванья причин в воле одного человека, точно так же, как открытие законов движения планет стало возможно только тогда, когда люди отрешились от представления утвержденности земли.
После Бородинского сражения, занятия неприятелем Москвы и сожжения ее, важнейшим эпизодом войны 1812 года историки признают движение русской армии с Рязанской на Калужскую дорогу и к Тарутинскому лагерю – так называемый фланговый марш за Красной Пахрой. Историки приписывают славу этого гениального подвига различным лицам и спорят о том, кому, собственно, она принадлежит. Даже иностранные, даже французские историки признают гениальность русских полководцев, говоря об этом фланговом марше. Но почему военные писатели, а за ними и все, полагают, что этот фланговый марш есть весьма глубокомысленное изобретение какого нибудь одного лица, спасшее Россию и погубившее Наполеона, – весьма трудно понять. Во первых, трудно понять, в чем состоит глубокомыслие и гениальность этого движения; ибо для того, чтобы догадаться, что самое лучшее положение армии (когда ее не атакуют) находиться там, где больше продовольствия, – не нужно большого умственного напряжения. И каждый, даже глупый тринадцатилетний мальчик, без труда мог догадаться, что в 1812 году самое выгодное положение армии, после отступления от Москвы, было на Калужской дороге. Итак, нельзя понять, во первых, какими умозаключениями доходят историки до того, чтобы видеть что то глубокомысленное в этом маневре. Во вторых, еще труднее понять, в чем именно историки видят спасительность этого маневра для русских и пагубность его для французов; ибо фланговый марш этот, при других, предшествующих, сопутствовавших и последовавших обстоятельствах, мог быть пагубным для русского и спасительным для французского войска. Если с того времени, как совершилось это движение, положение русского войска стало улучшаться, то из этого никак не следует, чтобы это движение было тому причиною.
Этот фланговый марш не только не мог бы принести какие нибудь выгоды, но мог бы погубить русскую армию, ежели бы при том не было совпадения других условий. Что бы было, если бы не сгорела Москва? Если бы Мюрат не потерял из виду русских? Если бы Наполеон не находился в бездействии? Если бы под Красной Пахрой русская армия, по совету Бенигсена и Барклая, дала бы сражение? Что бы было, если бы французы атаковали русских, когда они шли за Пахрой? Что бы было, если бы впоследствии Наполеон, подойдя к Тарутину, атаковал бы русских хотя бы с одной десятой долей той энергии, с которой он атаковал в Смоленске? Что бы было, если бы французы пошли на Петербург?.. При всех этих предположениях спасительность флангового марша могла перейти в пагубность.
В третьих, и самое непонятное, состоит в том, что люди, изучающие историю, умышленно не хотят видеть того, что фланговый марш нельзя приписывать никакому одному человеку, что никто никогда его не предвидел, что маневр этот, точно так же как и отступление в Филях, в настоящем никогда никому не представлялся в его цельности, а шаг за шагом, событие за событием, мгновение за мгновением вытекал из бесчисленного количества самых разнообразных условий, и только тогда представился во всей своей цельности, когда он совершился и стал прошедшим.
