Фибоначчиева система

Связанные понятия

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

Кру́глыми чи́слами относительно некоторой позиционной системы счисления называют степени её основания. В этой системе счисления такие числа записываются как единица с последующими нулями. Количество нулей справа от единицы равно показателю степени основания.

В математическом анализе и информатике кривая Мортона, Z-последовательность,Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры.

Номиналы промышленно выпускаемых электронных компонентов (сопротивление резисторов, ёмкость конденсаторов, индуктивность небольших катушек индуктивности) не являются произвольными. Существуют установленные стандартом специальные ряды номиналов, представляющие собой множества значений от 1 до 10. Номинал детали определённого ряда является некоторым значением из соответствующего ряда, умноженным на произвольный десятичный множитель (10 в целой степени).

Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 80-х годах XX столетия группа ученых под руководством профессора Алексея Петровича Стахова из Таганрогского радиотехнического института создала опытный экземпляр помехоустойчивого процессора [3]. Этот процессор мог сам контролировать возникающие в его работе сбои. Для кодирования информации была выбрана фибоначчиева система счисления. Ее использование позволило построить удивительный процессор, на званный “Фибоначчи-процессор”, или “Ф-процессор”. И хотя успешная попытка построения помехоустойчивого процессора на основе фибоначчиевой системы счисления носила скорее теоретический, чем практический интерес, изучение этой замечательной системы счисления заслуживает внимания.

Для указания, что число записано в ФСС, будем использовать в нижнем индексе сокращение fib. Например, 10000101fib = 3810.

Читайте также:  Терминатор игрушка 2

Числа Фибоначчи — элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10 946, …, в которой каждое последующее число, начиная с третьего, равно сумме двух предыдущих чисел.

Для формального определения чисел Фибоначчи используют следующее рекуррентное соотношение:

Последовательность, известная у нас как числа Фибоначчи, использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи (1170-1250).

Леонардо Пизанский Фибоначчи. Благодаря книге Фибоначчи “Liber Abaci” Европа узнала индоарабскую систему чисел, которая позднее вытеснила традиционные для того времени римские числа.

ФСС относится к позиционным системам. Алфавитом ФСС являются цифры 0 и 1, а ее базисом — последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 … . Обратите внимание, что F0 = 1 в базис не включается.

В табл. перечислены некоторые числа в двоичной и фибоначчиевой системах счисления.

Десятичное двоичное ФСС
100 или 11
1000 или 110
10010 или 1110
10100100 или 10011100 или 10100011 или 10011011

Фибоначчиева система является разновидностью двоичной системы — ее алфавит составляют цифры 0 и 1. Следовательно, эту неклассическую двоичную систему счисления, вообще говоря, можно использовать для кодирования информации в компьютере, так как элементная база современной компьютерной техники ориентирована на обработку двоичных последовательностей.

Избыточность ФСС проявляется в различных кодовых представлениях одного и того же числа.

4.1. Алгоритмы перевода целых чисел из ФСС в десятичную систему и обратно

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

В P-ичных системах счисления базис является геометрической прогрессией. Вклад в значение числа цифры a, стоящей на k-м месте слева, равен a-P k , где P — основание системы счисления. Часто говорят, что “вес” k-го разряда равен P k .

В ФСС “вес” каждого разряда числа также определяется базисом этой системы. Для удобства дальнейшей работы выпишем “веса” первых 10 разрядов ФСС (нумерацию разрядов ведем справа налево, начиная с первого). Такая нумерация разрядов удобна, поскольку в качестве веса k-го разряда используется k-е число Фибоначчи.

Читайте также:  Новичкам везет
10-й разряд 9-й разряд 8-й разряд 7-й разряд 6-й разряд 5-й разряд 4-й разряд 3-й разряд 2-й разряд 1-й разряд

Пример 1.Пусть нам дано число Afib = 10101010 записанное в фсс. Чему равно это число в десятичной системе счисления?

Чтобы ответить на этот вопрос, запишем цифры числа в разрядную сетку, затем умножим каждую цифру на вес разряда и сложим полученные числа. Так как цифрами фибоначчиевой системы счисления являются 0 и 1, то нам достаточно сложить веса тех разрядов, где стоят единицы.

8-й разряд 7-й разряд 6-й разряд 5-й разряд 4-й разряд 3-й разряд 2-й разряд 1-й разряд

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент – человек, постоянно откладывающий неизбежность. 10238 – | 7240 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системе счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:

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

Арифметика

Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 0 2 = 10 .

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

  • Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0 2 00 = 1001 . При переносе в отсутствующие разряды ε1 и ε следует помнить, что F1=1=F2 и F=0.
  • Во-вторых, требуется избавляться от соседних единиц: 0 11 = 100 . Правило для раскрытия двоек является следствием этого равенства: 0 2 00 = 0100 + 00 11 = 0 11 1 = 1001 .
Читайте также:  Промокод для франк казино

Этот раздел не завершён.

Обобщение на вещественные числа

Число Представление
через
степени
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

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

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

где <εk> обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с — золотым сечением отрезка [0,1], вычитанием (если εk=1) и умножением на . Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:

где N таково, что . Разумеется, следует считать что для всех .

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца ) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения. [3]

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

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

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

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

Для целых чисел и можно определить «умножение» [4]

которое аналогично умножению чисел в двоичной системе счисления.

Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой: [5]

где — целая часть, — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут. [6] Следует отметить, что другое «произведение» отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *