Запишите число 2016 в фибоначчиевой системе счисления

Запишите число 2016 в фибоначчиевой системе счисления

Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 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).

Леонардо Пизанский Фибоначчи. Благодаря книге Фибоначчи “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, то нам достаточно сложить веса тех разрядов, где стоят единицы.

Читайте также:  Болты для крепления монитора

Определение

Последовательность Фибоначчи определяется следующим образом:



Несколько первых её членов:

История

Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci) (также известный как Леонардо Пизанский (Leonardo Pisano)). Однако именно благодаря математику 19 века Люка (Lucas) название "числа Фибоначчи" стало общеупотребительным.

Впрочем, индийские математики упоминали числа этой последовательности ещё раньше: Гопала (Gopala) до 1135 г., Хемачандра (Hemachandra) — в 1150 г.

Числа Фибоначчи в природе

Сам Фибоначчи упоминал эти числа в связи с такой задачей: "Человек посадил пару кроликов в загон, окруженный со всех сторон стеной. Сколько пар кроликов за год может произвести на свет эта пара, если известно, что каждый месяц, начиная со второго, каждая пара кроликов производит на свет одну пару?". Решением этой задачи и будут числа последовательности, называемой теперь в его честь. Впрочем, описанная Фибоначчи ситуация — больше игра разума, чем реальная природа.

Индийские математики Гопала и Хемачандра упоминали числа этой последовательности в связи с количеством ритмических рисунков, образующихся в результате чередования долгих и кратких слогов в стихах или сильных и слабых долей в музыке. Число таких рисунков, имеющих в целом долей, равно .

Числа Фибоначчи появляются и в работе Кеплера 1611 года, который размышлял о числах, встречающихся в природе (работа "О шестиугольных снежинках").

Интересен пример растения — тысячелистника, у которого число стеблей (а значит и цветков) всегда есть число Фибоначчи. Причина этого проста: будучи изначально с единственным стеблем, этот стебель затем делится на два, затем от главного стебля ответвляется ещё один, затем первые два стебля снова разветвляются, затем все стебли, кроме двух последних, разветвляются, и так далее. Таким образом, каждый стебель после своего появления "пропускает" одно разветвление, а затем начинает делиться на каждом уровне разветвлений, что и даёт в результате числа Фибоначчи.

Вообще говоря, у многих цветов (например, лилий) число лепестков является тем или иным числом Фибоначчи.

Также в ботанике известно явление »филлотаксиса». В качестве примера можно привести расположение семечек подсолнуха: если посмотреть сверху на их расположение, то можно увидеть одновременно две серии спиралей (как бы наложенных друг на друга): одни закручены по часовой стрелке, другие — против. Оказывается, что число этих спиралей примерно совпадает с двумя последовательными числами Фибоначчи: 34 и 55 или 89 и 144. Аналогичные факты верны и для некоторых других цветов, а также для сосновых шишек, брокколи, ананасов, и т.д.

Для многих растений (по некоторым данным, для 90% из них) верен и такой интересный факт. Рассмотрим какой-нибудь лист, и будем спускаться от него вниз до тех пор, пока не достигнем листа, расположенного на стебле точно так же (т.е. направленного точно в ту же сторону). Попутно будем считать все листья, попадавшиеся нам (т.е. расположенные по высоте между стартовым листом и конечным), но расположенными по-другому. Нумеруя их, мы будем постепенно совершать витки вокруг стебля (поскольку листья расположены на стебле по спирали). В зависимости от того, совершать витки по часовой стрелке или против, будет получаться разное число витков. Но оказывается, что число витков, совершённых нами по часовой стрелке, число витков, совершённых против часовой стрелки, и число встреченных листьев образуют 3 последовательных числа Фибоначчи.

Читайте также:  Фото молодых людей 35 лет

Впрочем, следует отметить, что есть и растения, для которых приведённые выше подсчёты дадут числа из совсем других последовательностей, поэтому нельзя сказать, что явление филлотаксиса является законом, — это скорее занимательная тенденция.

Свойства

Числа Фибоначчи обладают множеством интересных математических свойств.

Вот лишь некоторые из них:

Из предыдущего равенства при вытекает:

Из предыдущего равенста по индукции можно получить, что

всегда кратно .

Верно и обратное к предыдущему утверждение:

если кратно , то кратно .

По отношению к алгоритму Евклида числа Фибоначчи обладают тем замечательным свойством, что они являются наихудшими входными данными для этого алгоритма (см. "Теорема Ламе" в Алгоритме Евклида).

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

Теорема Цекендорфа утверждает, что любое натуральное число можно представить единственным образом в виде суммы чисел Фибоначчи:

где , , , (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:



причём ни в каком числе не могут идти две единицы подряд.

Нетрудно получить и правило прибавления единицы к числу в фибоначчиевой системе счисления: если младшая цифра равна 0, то её заменяем на 1, а если равна 1 (т.е. в конце стоит 01), то 01 заменяем на 10. Затем "исправляем" запись, последовательно исправляя везде 011 на 100. В результате за линейное время будет получена запись нового числа.

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

Формула для n-го числа Фибоначчи

Формула через радикалы

Существует замечательная формула, называемая по имени французского математика Бине (Binet), хотя она была известна до него Муавру (Moivre):

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

Сразу можно заметить, что второе слагаемое всегда по модулю меньше 1, и более того, очень быстро убывает (экспоненциально). Отсюда следует, что значение первого слагаемого даёт "почти" значение . Это можно записать в строгом виде:

где квадратные скобки обозначают округление до ближайшего целого.

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

Матричная формула для чисел Фибоначчи

Нетрудно доказать матричное следующее равенство:

Но тогда, обозначая

Таким образом, для нахождения -го числа Фибоначчи надо возвести матрицу в степень .

Вспоминая, что возведение матрицы в -ую степень можно осуществить за (см. Бинарное возведение в степень), получается, что -ое число Фибоначчи можно легко вычислить за c использованием только целочисленной арифметики.

Периодичность последовательности Фибоначчи по модулю

Рассмотрим последовательность Фибоначчи по некоторому модулю . Докажем, что она является периодичной, и причём период начинается с (т.е. предпериод содержит только ).

Докажем это от противного. Рассмотрим пар чисел Фибоначчи, взятых по модулю :

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

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

Читайте также:  Мобильный яндекс браузер реклама

Как известно, последовательность Фибоначчи начинается с двух чисел и 1 и каждый последующий член последовательности получается как сумма двух предыдущих. Например, третий член последовательности это 1 (1=1+), четвёртый — 2 (2=1+1), пятый — 3 (3=2+1) и т.д.

i 1 2 3 4 5 6 7 8 9
Fib(i) 1 1 2 3 5 8 13 21 34

Рисунок 1 — Первые числа последовательности Фибоначчи

Эта последовательность проявляется очень часто и в нашей жизни и в природе и имеет большое значение. А знаете ли Вы, что все положительные целые числа можно представить как сумму чисел из последовательности Фибоначчи? Более того, все натуральные числа можно представить при помощи последовательности Фибоначчи, причём без повторений. Например: 13 может быть представлено из указанного множества как <13>, <5,8> или <2,3,8> а 17 представлено как <1,3,13> или <1,3,5,8>. Так как все числа обладают этим свойством (может у Вас есть желание доказать это?), то этот набор является хорошим способом для использования в качестве "базы" (основания системы счисления) для представления чисел. Но, как мы видели выше, некоторые числа могут быть представлены более чем одним способом суммой чисел из последовательности Фибоначчи. Как нам выйти из этой ситуации? Очень просто! Для этого достаточно наложить ограничение, что для предоставления числа нельзя использовать два соседних элемента из последовательности Фибоначчи! Это ограничение объясняется тем, что сумма двух соседних членов последовательности Фибоначчи сама является членом последовательности Фибоначчи.

Теперь, когда мы знаем всё изложенное выше, мы можем предложить хороший способ предоставления любого целого положительного числа. Для этого мы будем использовать двоичную последовательность (только нулей и единиц). Например, 17 = 1 + 3 + 13 (мы должны помнить, что нельзя использовать два последовательных числа Фибоначчи). Будем использовать ноль в записи, если очередное число из последовательности Фибоначчи не используется, и единицу для тех что используются. Тогда, 17 = 100101 (ведущие нули должны быть опущены). На рисунке 2 подробно показано, как получена эта запись и что означают нули и единицы в приведённой выше записи. Для лучшего понимания этой схемы обратим внимание на тот факт, что не использование двух соседних чисел Фибоначчи означает, что двоичная последовательность не будет иметь двух подряд идущих единиц. Используя приведённое представление числа, мы будем говорить, что мы используем Фибоначчиеву систему счисления и записывать его как 17 = 100101 (fib).

17= 1 1 1
13+3+1= 13 8 5 3 2 1

Рисунок 2 — Объяснение представления числа 17 в Фибоначчиевой системе счисления

Ваша задача состоит в записи заднного десятичного числа в Фибоначчиевой системе счисления.

Входные данные

В первой строке входных данных задано единственное натуральное число N, указывающее на количество примеров в тесте (1N500).

Следующие N строк содержат по одному положительному целому числу, не превышающему 100 000 000. Числа могут быть поданы в произвольном порядке.

Выходные данные

Вы должны вывести по одной строке для каждого из N чисел, полученных во входных данных, в следующем формате: "DEC_BASE = FIB_BASE (fib)". DEC_BASE это заданное оригинальное число в десятичной системе счисления, а FIB_BASE соответственно — его представление в Фибоначчиевой системе счисления. Образец вывода приведён в примере выходных данных.

Ссылка на основную публикацию
Драйвера для philips s309
Home » Philips » Philips S309 USB Drivers Download Philips S309 official USB drivers for your Android smartphone. You will...
Герметик для питьевой воды
Силиконовые материалы всегда востребованы в хозяйстве. Особое внимание уделяется местам, где проводится герметизация мест, контактирующих с едой. Для таких целей...
Гзм 155 1 характеристики
1. Номинальный диапазон воспроизводимых частот, Гц 20-20000 31,5-16000 20-20000 20-17000 20-18000 20-20000 20-20000 20-20000 10-25000 10-25000 2. Прижимная сила звукоснимателя,...
Драйвера для видеокарты ати радеон
Драйверы Radeon Software/Catalyst для видеокарт AMD (ATI): AMD Radeon Software/Catalyst для Windows 10 Драйверы AMD Radeon Software/Catalyst для настольных и...
Adblock detector