Изменения
Перейти к навигации
Перейти к поиску
Строка 67:
Строка 67: − + + + + + +
→Использование в теории информации: + юпана
Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <math>a\ge 1</math> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <math>n\ge 2</math> верно неравенство: <math>F_n \le a < F_{n+1}</math>. Таким образом, <math>a = F_n + a'</math>, где <math>a'=a-F_n\ <\ F_{n-1}</math>, так что разложение числа <math>a'</math> уже не будет содержать слагаемого <math>F_{n-1}</math>.
Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <math>a\ge 1</math> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <math>n\ge 2</math> верно неравенство: <math>F_n \le a < F_{n+1}</math>. Таким образом, <math>a = F_n + a'</math>, где <math>a'=a-F_n\ <\ F_{n-1}</math>, так что разложение числа <math>a'</math> уже не будет содержать слагаемого <math>F_{n-1}</math>.
=== Использование в теории информации ===
=== Использование ===
==== Юпана ====
[[File:Yupana 1.GIF|thumb|Юпана]]
Предполагают, что некоторые разновидности [[Юпана|юпаны]] ([[абак]]а [[инки|инков]]) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен<ref>{{cite web|author=Antonio Aimi, Nicolino De Pasquale|url=http://web.archive.org/web/*/http://www.quipus.it/english/Andean%20Calculators.pdf|title=Andean Calculators|accessdate=2009-12-12}}</ref>.
==== В теории информации ====
На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код]] для натуральных чисел (1, 2, 3…), использующий последовательности [[бит]]ов. Поскольку комбинация <tt>11</tt> запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи.
На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код]] для натуральных чисел (1, 2, 3…), использующий последовательности [[бит]]ов. Поскольку комбинация <tt>11</tt> запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи.
Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз <tt>1</tt> (см. таблицу). То есть, кодовая последовательность имеет вид:
Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз <tt>1</tt> (см. таблицу). То есть, кодовая последовательность имеет вид: