12
правок
Изменения
м
==Теорема Цекендорфа (англ. ''Zeckendorf's theorem'')==
→Источники информации: links fixed
Целое число ''x'' в ''b''-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':
: <tex>x = \sum_sum\limits_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leqslant a_k \leqslant (b-1)</tex>.
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ичном представлении <tex>x</tex> была также ненулевой.
Наиболее употребляемыми в настоящее время позиционными системами являются:
* <tex>1 </tex> — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);* <tex>2 </tex> — двоичная (в дискретной математике, информатике, программировании);* <tex>8 </tex> — восьмеричная;* <tex>10 </tex> — десятичная (используется повсеместно);* <tex>12 </tex> — двенадцатеричная (счёт дюжинами);* <tex>16 </tex> — шестнадцатеричная (используется в программировании, информатике).
==Смешанные системы счисления==
'''Смешанная система счисления''' (англ. ''mixed radix numeral systems'') является обобщением <tex>b</tex>-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:
: <tex>x = \sum_sum\limits_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.
'''Фибоначчиева система счисления''' основывается на [https://en.wikipedia.org/wiki/Fibonacci_number числах Фибоначчи].
: <tex>x = \sum_sum\limits_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\ldots f_0</tex> не встречается две единицы подряд.
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\ldots </tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum_k sum\limits_k \varepsilon_k F_k,\ \varepsilon_k\in\{0,1\}</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k \geqslant 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
{{Теорема
|id=th1
|author=Цекендорф
|statement=
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
== Источники информации ==
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F/ Системы счисления]* [https://ru.wikipedia.org/wiki/%D0%A1A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F/ Фибоначчиева система счисления]* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A6%D0%B5%D0%BA%D0%B5%D0%BD%D0%B4%D0%BE%D1%80%D1%84%D0%B0/ Теорема Цекендорфа] [[Категория: Теория чисел]]
