Изменения

'''Счетчик Кнута''' (англ. ''Knuth's Counter'') - &mdash; структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к любому разряду числу выполняется за <tex>O(1)</tex>. Неотрицательное целое число <tex>N</tex> в ''избыточной двоичной системе счисления'' записывается в виде последовательности разрядов <tex>d_n d_{n-1} \dotsc d_2 d_1</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <math>d_i</math> &mdash; <tex>i</tex>&ndash;й разряд числа <tex>(1 \le i \le n)</tex>, причем <math>d_i \in \{0,1,2\}</math> и <math>\sum\limits_{i=1}^n d_i \cdot 2^i = N.</math>

ж) <tex>2020_{2} \Rightarrow 2000_{2}</tex> повторение алгоритма для 4 разрядаОригинальный алгоритм представлен в Clancy, по варианту а <tex>2000_{2} \Rightarrow 11000_{2}</tex>Knuth и состоит из двух правил:

з) # Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>010_d_{2i+1} \Rightarrow 110_d_i</tex> на <tex>(d_{2i+1}+1)0</tex># Заменить <tex>d_1</tex> на <tex>d_1+1</tex> .

== Амортизационная оценка алгоритма ==Воспользуемся методом предоплаты. Будем считать, что Чтобы достичь необходимой оценки и не выполнять каждый раз когда мы начинаем выполнять алгоритм мы берем 2 монеткипоиск для первого правила, можно хранить односвязный список позиций двоек в числе. Одна будет тратится на изменение текущего разряда и одна запасатьсяТогда чтобы найти младший разряд равный двум нужно просто взять первый элемент списка. Таким образомТакже, если непосредственно перед изменением значений разрядов в разряде стоит 1, то для него запасена 1 монетка, если стоит 2, то запасено 2 монетки. Проверим все варианты.правилах необходимо выполнять следующее:

а) Так как в текущем разряде было 2# Если <tex>d_{i+1}=1</tex>, то уже запасено 2 монеты, а так же согласно инварианту после 2 стоит 0, тогда возьмем одну из запасенных у двойки монет и потратим их заменить первый элемент списка с <math>i</math> на присвоение следующему разряду <math>i+1</math>, вторую запасенную передадим этой единицеиначе удалить его. Одну монету потратим на установку # Если <tex>d_1=1</tex>, то добавить в текущий разряд начало списка 1, вторую запасем для это единицы.

б) Так как в текущем разряде было 1Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породитьтройку, что недопустимо. Однако если между любой парой двоек всегда будет находится хотя бы один0, то прибавим наши монеты к уже запасенной от единицытакой ситуации не возникнет. Одну монету потратимПокажем, что если это условие с нулем выполняется, то оновыполняется и после инкремента, рассмотрев основные случаи(в обозначениях левой части предполагается что правая двойка самая младшая из всех до инкремента):* <math>\dotsc 2\dotsc 0\dotsc 12\dotsc </math> переходит в <math>\dotsc 2\dotsc 0\dotsc 20\dotsc </math>, при этом в младшем разряде может появиться новая 2-ка и между ней следующей будет хотя бы установить один ноль.* <math>\dotsc 2\dotsc 0\dotsc 02\dotsc </math> переходит в <math>\dotsc 2\dotsc 0\dotsc 10\dotsc </math>, ситуация почти аналогична предыдущей.* <math>\dotsc 202\dotsc </math> переходит в <math>\dotsc 210\dotsc </math>, также гарантируется наличие нуля при появлении двойки в младшем разряде* Появление двух двоек, останется если уже есть ровно одна возможно, тогда <math>\dotsc 12\dotsc 1</math> переходит в <math>\dotsc 20\dotsc 2 монеты</math>, ясно что в этом случае между ними также будет хотя бы один ноль.

в) Так В таблице можно увидеть как в текущем разряде было 1, то прибавив наши монеты будет изменятья представление при применении данных правил десять раз к запасенной получим 3. Одну монету потратим, что бы установить нулю (представления чисел от 0, оставшиеся 2 потратим на повторение алгоритма для следующего разряда.до 10):

г) Так как в текущем разряде было {| class="wikitable"|-! Шаг! Представление! Шаг! Представление|-| 0 | 0| 5 | 21|-| 1, в следующем | 1| 6 | 102|-| 2, то уже запасено 3 монеты и еще | 2 наши. | 7 | 111|-| 3 монеты потратим, что бы следующему за 2 разряду установить 1, разряду с 2 установить 1, текущему установить 0. Останется 2 монеты, которые распределятся между двумя единицами.| 11| 8 | 112|-| 4 | 12| 9 | 121|}

д) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 0, то уже запасено 2 монеты. Одну монету потратим == Обобщение на изменение предыдущего разряда, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разряде.системы с произвольным основанием ==

еВ общем случае подобные счётчики называются ''<math>b</math>-ричными избыточными счетчиками'' (''ИС'') Так как в текущем разряде было , которые похожи на счетчик Кнута,но основание системы может быть произвольным, то есть <math>d_i \in \{0, в предыдущем разряде 21,\dotsc ,b\}</math> и <math>\sum\limits_{i=1}^n d_i \cdot b^i = N</math>, где <math>b</math> &mdash; основание. Такие счетчики позволяют прибавить единицу к любому разряду, то есть увеличить число на <math>b^i</math>за <math>O(1)</math>Назовем такое представление ''регулярным'', если между дувумя разрядами равными <math>b</math> есть хотя бы один разряд отличный от<math>b-1</math>.Операция ''исправления'' (''fix'') разряда <math>d_i=b</math> в следующем регулярной <math>b</math>-ричногосчетчика <math>d</math> увеличивает <math>d_{i+1}</math> на 1и устанавливает<math>d_i</math> в 0, образуая новый регулярный счетчик, представляющий то уже запасено 3 монетыже число,что и <math>d</math>.Чтобы добавить 1 к разряду <math>d_i</math> регулярного ИС <math>d</math>,нужно сделать следующее:# Если <math>d_i=b</math>, исправить <math>d_i</math>. Одну монету потратим на изменение предыдущего разряда# Если <math>d_i=b-1</math> и самый младший значащий разряд <math>d_j</math>, такой, что <math>j>i</math> и <math>d_j \ne b-1</math>, одну сохраним с единицейравен <math>b</math> (т.е. <math>d_j=b</math>), наши две монеты потратим на повторение алгоритма на следующем разрядеприменить операцию исправления к разряду <math>d_j</math>.# Добавить 1 к <math>d_i</math>. Останется одна лишняя монета# Если <math>d_i=b</math>, исправить <math>d_i</math>.

ж) Так как в текущем разряде было 0Для реализации данной схемы, в предыдущем разряде 2мы используем односвязный список разрадов от младшихк старшим. В дополнение каждый разряд <math>d_i</math> равный <math>b-1</math>будет иметь указатель на самый младший разряд <math>d_j</math>, в следующем 2такой, то уже запасено 4 монеты. Одну монету потратим на изменение предыдущего разрядачто <math>j>i</math> и <math>d_j \ne b-1</math>, две сохраним с двойкойесли он равен <math>b</math>, наши две монеты потратим иначе этот указатель будет на повторение алгоритма произвольный разряд <math>d_j</math> (<math>j>i</math>).Теперь, во время увеличения разряда <math>d_i</math> на следующем разряде1, будем проверятьразряд по указателю вперед (п. Останется одна лишняя монета2).

з) Одну монету потратим Такое представление позволяет увеличиать произвольный разряд за константноевремя. Обновление указателя вперед происходит следующим образом: когда <math>d_{i+}</math> становится равен <math>b-1</math> при исправлении разряда <math>d_{i-1}</math>, устанавливаем указатель вперед разряда <math>d_{i}</math> на изменение разряда<math>d_{i+1}</math>, если <math>d_{i+1}=b</math>, либо копируем указатель вперед из <math>d_{i+1}</math> в <math>d_{i}</math>, если <math>d_{i+1}=b-1</math>.При собственно добавлении единицы к разряду <math>d_i</math>, также необходимо обновлять его указатель вперед аналогичным образом, оставшуюся запасем с единицейесли этот разряд становится равен <math>b-1</math>.

Получается 2 монет достаточно для прибавления 1 к любому разряду== Литература ==* H. Kaplan и R. E. Tarjan. New heap data structures. 1998* M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, тогда наш алгоритм работает в среднем за <tex>ODepartment of Computer Sciencr, Stanford University, Palo Alto, 1977.* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (1SODA 96)</tex>'', страницы 52-58. ACM Press, 1996.* H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. ''Proceedings of the 28th Annual ACM Symposium of Computing'', страницы 202-211. ACM Press, 1996

== Смотри Смотрите также ==