Изменения

{{Определение|id=knuth_counter|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за <tex>O(1)</tex>.}}

{{Определение|id=knuth_counter|definition= Неотрицательное целое число <tex>N</tex> в ''избыточной двоичной системе счисления'' записывается в виде последовательности разрядов <tex>d_n d_{n-1} \dotsc d_2 d_1</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex> {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0,1,2\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^i = N.

== Алгоритм Счетчик Кнута == ==== Описание алгоритма ====

Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный список [[Cписок]] позиций двоек в числе. Тогда чтобы найти младший разряд равный двум нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов в правилах необходимо выполнять следующее:

# : Число двоек не изменяется## :: <tex>\dotsc 2\dotsc 0\dotsc 12\dotsc 0 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 1</tex>.## :: <tex>\dotsc 02\dotsc 1 \rightarrow \dotsc 10\dotsc 2</tex>.## :: <tex>\dotsc 2\dotsc 02\dotsc 1 \rightarrow \dotsc 2\dotsc 10\dotsc 2</tex> (частный случай предыдущего).## :: <tex> \dotsc 12 \rightarrow \dotsc 21</tex>.# : Пропадает одна двойка## :: <tex> \dotsc 02\dotsc 0 \rightarrow \dotsc 10\dotsc 1</tex>.## :: <tex> \dotsc 02 \rightarrow \dotsc 11</tex>.# : Появление новой двойки## :: <tex>\dotsc 1 \rightarrow \dotsc 2</tex> (имеется в виду появление единственной двойки).## :: <tex>\dotsc 12\dotsc 1 \rightarrow \dotsc 20\dotsc 2</tex>.## :: <tex>\dotsc 2\dotsc 0\dotsc 12\dotsc 1 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 2</tex> (частный случай предыдущего). Таким образом мы видим, что <tex>0</tex> всегда сохраняется.

{{Определение|id=b_ary_rr|definition=В общем случае подобные счётчики называются ''<tex>b</tex>-ричными избыточными счетчиками'' (''ИС''), которые похожи на счетчик Кнута,но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex> {{---}} основание. Такие счетчики позволяют прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex>за <tex>O(1)</tex>}} {{Определение|id=regular_rr|definition= Назовем такое представление ''регулярным'', если между дувумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от<tex>b-1</tex>.}} {{Определение|id=fixup|definition= Операция ''исправления'' (''fix'') разряда <tex>d_i=b</tex> в регулярной <tex>b</tex>-ричногосчетчика <tex>d</tex> увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает<tex>d_i</tex> в <tex>0</tex>, образуая новый регулярный счетчик, представляющий то же число,что и <tex>d</tex>.}}