Интернет магазин китайских планшетных компьютеров



Компьютеры - Фибоначчиева система счисления

22 января 2011
http://www.sevastopol.dwg-rf.ru/ заработок на распечатке чертежей.

Оглавление:
1. Фибоначчиева система счисления
2. Обобщение на вещественные числа
3. Фибоначчиево умножение



Цена и стоимость слуховых аппаратов www.melfon.ru.

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

Zeckendorf representations.png
Число Запись
в ФСС
Код
Фибоначчи
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

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

Любое неотрицательное целое число a = 0,\ 1,\ 2,\dots можно единственным образом представить через последовательность битов …εk…ε4ε3ε2: a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1, причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: \forall k\ge 2: \Rightarrow. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

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

Доказательство существования легко провести по индукции. Любое целое число a\ge 1 попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n\ge 2 верно неравенство: F_n \le a <  F_{n+1}. Таким образом, a = Fn + a', где a'=a-F_n\ <\ F_{n-1}, так что разложение числа a' уже не будет содержать слагаемого Fn − 1.

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

Юпана

Юпана

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

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

На основе фибоначчиевой системы счисления строится код Фибоначчи — универсальный код для натуральных чисел, использующий последовательности битов. Поскольку комбинация 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.


Просмотров: 3812


<<< Упаковка исполняемых файлов
Альтернативные потоки данных >>>