Факториальная и фибоначчиева система счисления

Факториальная и фибоначчиева система счисления

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

Числа Фибоначчи – элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 …, в которой каждое последующее число равно сумме двух предыдущих чисел (F=F1=1, Fk=Fk-1+ Fk-2 (k³2)). Данная последовательность названа по имени средневекового математика Леонардо Пизанского (Фибоначчи).

K
Fk
K
Fk

Число 137=1×89+0×55+1×34+0×21 +1×13 +0×8+0×5 +0×3+0×2+1×1 запишется в виде 1010100001fib. Отметим, что в фибоначчиевой записи не встречается две единицы подряд.

Любопытства ради, заметьте, что

Число 0,6180… называют золотым сечением и используют в численном анализе, в строительстве сооружений, при поиске гармонии в природе и обществе. Еще строители Парфенона усматривали золотую пропорцию катетов 0,6180 : 0,3820 в приятнейшем для глаза треугольнике.

КОНТРОЛЬНЫЕ ВОПРОСЫ

Ознакомьтесь с принципами работы непозиционных и смешанных систем счисления и ответьте на приведенные ниже вопросы.

1. Дайте определения непозиционных и смешанных систем счисления.

2. Назовите и охарактеризуйте свойства непозиционных и смешанных систем счисления.

3. Назовите известные вам непозиционные системы счисления.

4. Назовите известные вам смешанные системы счисления.

5. Объясните причину неполной непозиционности римской системы счисления.

6. Охарактеризуйте различие между цифрой и числом.

7. Ознакомившись с позиционными системами счисления, охарактеризуйте систему счисления майя.

8. Сравните между собой факториальную и фибоначчиеву системы счисления.

9. Чему равно отношение 15-го и 16-го чисел Фибоначчи и насколько оно далеко от золотого сечения?

10. Находится ли представительство партий в Государственно думе в отношении золотого сечения?

11. Чему равна обратная величина золотого сечения? Не наводит ли эта величина на размышления, которые позволили бы найти золотое сечение с большим числом знаков?

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

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

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

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

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

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

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

Читайте также:  Отключите опции кэширования и затенения памяти bios

Леонардо Пизанский Фибоначчи. Благодаря книге Фибоначчи “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-й разряд

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

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 9270 — | 7454 — или читать все.

Читателям газеты-вкладки “В мир информатики” конечно же известно, что существуют два вида систем счисления: позиционные и непозиционные. А знаете ли вы, что позиционные системы, в свою очередь, можно разделить на традиционные и нетрадиционные?

Напомним основные положения. В позиционной системе счисления количественный эквивалент цифры зависит от ее положения в записи числа. Для таких систем мы фиксируем некоторое основание — целое положительное число
р 2 и рассматриваем так называемый базис. Чтобы понять последнее понятие, давайте вспомним, что в привычной нам десятичной системе значение числа образуется следующим образом: значения его цифр умножаются на “веса” соответствующих разрядов и все полученные значения складываются. Например:

Читайте также:  Как убрать рекламу вулкан на андроиде

2348310 = 2 · 10 4 + 3 · 10 3 + 4 · 10 2 + 8 · 10 1 + 3 · 10 0 .

Аналогично и для чисел, записанных в других системах счисления:

10001102 = 1 · 2 6 + 0 · 2 5 + 0 · 2 4 + 0 · 2 3 + 1 · 2 2 + 1 · 2 1 + 0 · 2 0 ;

7А0С16 = 7 · 16 3 + 10 · 16 2 + 0 · 16 1 + 12 · 16 0 .

Последовательность чисел, каждое из которых задает “вес” соответствующих разрядов, и называют базисом системы счисления. Из приведенных примеров видно, что базисы десятичной, двоичной, шестнадцатеричной систем счисления образуют геометрическую прогрессию со знаменателем р, равным 10, 2 и 16 соответственно.

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

Если какое-то из перечисленных условий не соблюдается, то речь идет о нетрадиционной системе счисления. В статьях [2–3] рассказывалось, например, о троичной уравновешенной системе счисления с цифрами –1, 0 и 1 (присутствует отрицательное число). А можно ли в качестве базиса выбрать не геометрическую прогрессию, а некоторую последовательность натуральных чисел? Оказывается, да. Такая система, например, применялась для календаря и астрономических наблюдений индейцами племени майя. Они использовали 20-ричную систему счисления за некоторым исключением: р = 1, р1 = 20, р2 = 18, р3 = 20, р4 = 20 и т.д. Это было сделано для облегчения расчетов календарного цикла. Например, число 100 в этой системе, равное 1 · 18 · 20 + 0 · 20 + 0 · 1 = 360, есть примерно число дней в нашем, “солнечном”, году. У индейцев 20 дней-кинов образовывали месяц (виналь, или уинал), 18 месяцев-уиналов образовывали год (тун) и так далее:

Виналь = 20 кин = 20 дней.

Тун = 18 виналь = 360 дней = около 1 года.

Катун = 20 тун = 7200 дней = около 20 лет.

Бактун = 20 катун = 144 000 дней = около 400 лет.

Пиктун = 20 бактун = 2 880 000 дней = около 8000 лет.

Калабтун = 20 пиктун = 57 600 000 дней = около 160 000 лет.

Кинчильтун = 20 калабтун = 1?152?000?000 дней =
= около 3 200 000 лет.

Алавтун = 20 кинчильтун = 23 040 000 000 дней =
= около 64 000 000 лет.

Также в качестве примера можно рассмотреть представление времени в виде количества суток, часов, минут и секунд. При этом величина “d дней h часов m минут s секунд” соответствует значению d · 24 · 60 · 60 + + h · 60 · 60 +
+ m · 60 + s секунд.

Рассмотрим еще две нетрадиционные системы счисления.

Первая называется факториальной. В этой системе счисления базис образует последовательность факториалов натуральных чисел: 1! = 1, 2! = 2,
3! = 6, … . Другой ее особенностью является то, что количество цифр, используемых в том или ином разряде (так называемая размерность алфавита), неодинаково — оно увеличивается с ростом номера разряда. В первом разряде могут быть только цифры 0 и 1, во втором — 0, 1 и 2, в k-м — 0, 1, 2, …, k и так далее. Следовательно, если запись числа в факториальной системе имеет вид dn dn–1…d2d1, то этому числу соответствует десятичное значение, равное

= d1 · 1! + d2 · 2! + d3 · 3! + … + dn · n!,

— где dk — цифра числа (0 dk k). Десятичному же числу 2008 соответствует 2 · 720 + 4 · 120 + 3 · 24 + 2 · 6 + 2 · 2 + 0 · 1 = 2 · 6! + 4 · 5! + 3 · 4! + 2 · 3! +
+ 2 · 2! + 0 · 1! = 243220f (буква f в виде индекса говорит о записи числа в факториальной системе).

Фибоначчиева система счисления известна еще более узкому кругу специалистов. Из названия нетрудно догадаться, что она основывается на числах Фибоначчи. В этой системе счисления вес k-го разряда равен k-му числу Фибоначчи: 1, 2, 3, 5, 8, 13, 21, 34, 55, … (каждый член, начиная с третьего, равен сумме двух предыдущих). Используемые цифры (алфавит) — только 0 и 1. Следовательно, если запись числа в фибоначчиевой системе имеет вид fn fn–1…f2f1, то этому числу соответствует десятичное значение, равное , где Fk — числа

Читайте также:  Проверить откуда письмо по штрих коду

Фибоначчи, fk <0, 1>, причем в записи числа две единицы не должны стоять рядом 1 . Последнее замечание крайне важно: при несоблюдении этого условия запись числа будет неоднозначной. Например, число 510 может быть записано как 110Fib (5 = 1 · 3 + 1 · 2 + 0 · 1) и 1000Fib (5 = 1 · 5 + 0 · 3 + 0 · 2 + 0 · 1), но правильным считается второе число, где в записи нет двух подряд идущих единиц. В этом случае каждое натуральное число в фибоначчиевой системе счисления записывается единственным образом. Например, 200810 = 1597 + 377 + 34 = F16 + F13 + F8 = 1001000010000000Fib.

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

Задания для самостоятельной работы 2

1. Какие из чисел записаны не по правилам факториальной системы счисления: 42220, 44000, 86633300, 8663320?

2. Определите десятичный эквивалент чисел, записанных

а) в факториальной системе: 502101, 4422310;

б) в фибоначчиевой системе: 10010101, 101010101.

3. Запишите десятичные числа 34502 и 45087012 в факториальной системе счисления.

4. Перечислите первые 14 натуральных чисел в фибоначчиевой системе счисления. Проанализируйте полученные числа и сформулируйте правила перечисления натуральных чисел (правила получения очередного числа) в этой системе.

5. Запишите десятичные числа 30, 125 и 1949 в фибоначчиевой системе счисления.

6. Объясните, какое отношение имеют необычные счеты, показанные на рисунке, к данной статье? Какое десятичное число отложено на правых счетах?

7. На известном вам языке программирования напишите программы перевода десятичного натурального числа N (N 2 31 – 1) в факториальную и фибоначчиеву системы счисления и обратно.

В заключение ответим на вопрос, который скорее всего возник у читателей: а зачем нужны такие системы счисления? Факториальная система счисления используется, например, специалистами в теории чисел для нумерации перестановок. Системы, аналогичные фибоначчиевой, применяются при кодировании информации. В свое время была даже сделана попытка создания компьютера, основанного на фибоначчиевой системе счисления [1]. Это теоретически и практически интересные системы записи чисел. Изучение особенностей таких систем продолжается и в настоящее время, и у наших читателей есть возможность заняться серьезным исследованием данного вопроса.

1. Андреева Е.В., Босова Л.Л., Фалина И.Н. Математические основы информатики. Элективный курс: Учебное пособие. М.: БИНОМ. Лаборатория знаний, 2005.

2. О троичной системе счисления. / Информатика, № 4/2006.

3. Гашков С.Б. Системы счисления и их применения. / Информатика, № 4/2006.

4. Кузьмищев В.А. Тайна жрецов майя. М.: Молодая гвардия, 1975.

5. Касаткин В.Н. Новое о системах счисления. Киев: Выща школа, 1982.

1 Имеется также вариант фибоначчиевой системы счисления, в которой в записи чисел не допускаются два рядом стоящих нуля. — Прим. ред.

2 Ответы и/или программы (можно не все) присылайте в редакцию. Фамилии всех приславших будут опубликованы, а лучшие ответы мы поощрим. — Ред.

Ссылка на основную публикацию
Усики для автомобильной антенны
Убираясь в бардачке я наткнулся на ремкомплект антенных усиков — лежит наверно уже полгода, всё наклеить не могу, то забываю,...
Телефонный шлюз что это
VoIP-шлюз — это межсетевой шлюз, предназначенный для перевода трафика между сетями различных типов. VoIP-шлюзы можно разделить на многоканальные и одноканальные:...
Телефонная клавиатура на компьютере
Виртуальная клавиатура выручит Вас, когда выйдет из строя основное физическое устройство ввода, полностью или частично ( поломается несколько клавиш )....
Усиление сигнала интернета на даче своими руками
С наступление дачного сезона, я озадачился установкой хорошего скоростного интернет на даче, у нас голосовая связь работает без проблем, а...
Adblock detector