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

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
'''Фибоначчиева система счисления''' — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д.
 
'''Фибоначчиева система счисления''' — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д.
 
'''Последовательность Фибоначчи''' определяется следующим образом:
 
'''Последовательность Фибоначчи''' определяется следующим образом:
F0 = 0
+
[[Изображение:Ф0.png]]
F1 = 1,
+
[[Изображение:Ф1.png]]
Fn = Fn-1 + Fn-2.  
+
[[Изображение:Фн.png]]
 +
 
Несколько первых её членов :  
 
Несколько первых её членов :  
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
+
[[Изображение:Нескпер.png]]
  
 
''' История'''  
 
''' История'''  
Строка 36: Строка 37:
 
[[Изображение:Суммчислфиб.png]]
 
[[Изображение:Суммчислфиб.png]]
  
где k1 \ge k_2+2, k_2 \ge k_3+2, \ldots, k_r \ge 2 (т.е. в записи нельзя использовать два соседних числа Фибоначчи).
+
где k1 >= k2+2, k2 >= k3+2, ... , kr >= 2 (т.е. в записи нельзя использовать два соседних числа Фибоначчи).
  
 
Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:
 
Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:
 +
 +
[[Изображение:Отсюдаслед.png]]
 +
[[Изображение:Отсюдаслед2.png]]
 +
[[Изображение:Отсюдаслед3.png]]
 +
 +
причём ни в каком числе не могут идти две единицы подряд.
 +
 +
Нетрудно получить и правило прибавления единицы к числу в фибоначчиевой системе счисления: если младшая цифра равна 0, то её заменяем на 1, а если равна 1 (т.е. в конце стоит 01), то 01 заменяем на 10. Затем "исправляем" запись, последовательно исправляя везде 011 на 100. В результате за линейное время будет получена запись нового числа.
 +
 +
Перевод числа в фибоначчиеву систему счисления осуществляется простым "жадным" алгоритмом: просто перебираем числа Фибоначчи от больших к меньшим и, если некоторое [[Изображение:Некоторое.png]] , то [[Изображение:Фк.png]] входит в запись числа [[Изображение:Ннн.png]], и мы отнимаем [[Изображение:Фк/png]]от [[Изображение:Ннн/png]] и продолжаем поиск.

Версия 11:02, 20 сентября 2011

Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д. Последовательность Фибоначчи определяется следующим образом: Ф0.png Ф1.png Фн.png

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

История

Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci) (также известный как Леонардо Пизанский (Leonardo Pisano)). Однако именно благодаря математику 19 века Люка (Lucas) название "числа Фибоначчи" стало общеупотребительным. Впрочем, индийские математики упоминали числа этой последовательности ещё раньше: Гопала (Gopala) до 1135 г., Хемачандра (Hemachandra) — в 1150 г.

Свойства

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

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

   * Соотношение Кассини: 
     Кассини.png
   * Правило "сложения": 
     Сложение.png
   * Из предыдущего равенства при k = n вытекает: 
     Из предыд равенства.png
   * НОД-равенство: 
     Нод равенство.png

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

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

Суммчислфиб.png

где k1 >= k2+2, k2 >= k3+2, ... , kr >= 2 (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

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

Отсюдаслед.png Отсюдаслед2.png Отсюдаслед3.png

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

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

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

Личные инструменты
наши друзья
http://аудиохрестоматия.рф/