Изменения

{{Определение|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-1} = N.== Алгоритм ==</tex>Имеется число, записанное в избыточной двоичной системе счисления, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0.}}

Разберем случаи добавления единицы:* a) Если 1 нужно добавить к 2Заметим, то что в текущем разряде установить 1этой системе представление числа неоднозначно, в следующем 1.* б) Если 1 нужно добавить к 1 и в следующем разряде 0, то в текущем разряде установить 2.* в) Если 1 нужно добавить к 1 и в следующем разряде 1, то в текущем разряде установить 0, повторить алгоритм для следующего разряда.* г) Если 1 нужно добавить к 1 и в следующем разряде 2, то в следующем за двойкой разряде установить 1, в разряде с двойкой установить 1, в текущем установить 0.* д) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 0, то в предыдущем разряде установить 0, в текущем 2.* е) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 1, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.* ж) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 2, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.* з) Если 1 нужно добавить к 0 и в предыдущем разряде не 2, установить в текущем разряде 1например представление <tex>212</tex> эквивалентно <tex>1100</tex>.

== Доказательство Счетчик Кнута ==Покажем, что инвариант не нарушится.

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

Во втором случае# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если в следующем разряде 0таковой имеется, то предыдущий установится в заменить последовательность <tex>(\dotsc d_{i+1}d_i \dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0, текущий в 2 и так как в следующем 0 инвариант не нарушится. Если в следующем разряде не 0, то предыдущий установится в 0 и алгоритм запустится от следующего\dotsc)</tex># Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.

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

а) # Если <tex>200_d_{2} \Rightarrow 1100_{2i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.

в) <tex>1100_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разрядаПроблемой может оказаться появление двух последовательных двоек, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>при этом первое правило может породитьтройку. То есть недопустима следующая ситуация:

г) <tex>2100_(\dotsc 22\dotsc) \overset{2Inc} {\Rightarrow 11000_{2longmapsto}(\dotsc 30\dotsc)</tex>.

е) <tex>1020_{2} (\dotsc 212\dotsc) \Rightarrow 1000_overset{2Inc}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2\longmapsto} (\dotsc 220\Rightarrow 2000_{2}dotsc)</tex>

жПричем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.Однако если между любой парой двоек всегда будет находиться хотя бы один<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариантподдерживается после инкремента, рассмотрев возможные ситуации:: Число двоек не изменяется:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.:: <tex>(\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2) </tex>.:: <tex>2020_(\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).:: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.: Пропадает одна двойка:: <tex>(\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.:: <tex>(\dotsc 02) \Rightarrow 2000_overset{2Inc} {\longmapsto}(\dotsc 11)</tex> повторение алгоритма для 4 разряда, по варианту а .: Появление новой двойки:: <tex>2000_(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.:: <tex>(\Rightarrow 11000_dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2}\dotsc 0\dotsc 20\dotsc 2)</tex>(частный случай предыдущего).

з) Таким образом мы видим, что <tex>010_{2} \Rightarrow 110_{2}0</tex> всегда сохраняется.

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

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

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

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

г{{Определение|id=b_ary_rr|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричным избыточным представлением''' ('''ИП''', англ. ''b-ary redundant representation'') Так как , которое похоже на представление в текущем разряде было 1счетчике Кнута, в следующем 2но основание системы может быть произвольным, то уже запасено 3 монеты и еще 2 наши. 3 монеты потратиместь <tex>d_i \in \{0, что бы следующему за 2 разряду установить 1, разряду с 2 установить \dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, текущему установить 0где <tex>b</tex> {{---}} основание. Останется 2 монетыОно позволяет прибавить единицу к любому разряду, которые распределятся между двумя единицами.то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex>}}

д{{Определение|id=regular_rr|definition= Назовем представление '''регулярным''' (англ. ''regular'') Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 0, то уже запасено 2 монеты. Одну монету потратим на изменение предыдущего разряда, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разрядеесли между двумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.}}

е{{Определение|id=fixup|definition= Операция '''исправления''' (англ. ''fix'') Так как разряда <tex>d_i=b</tex> в текущем разряде было регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, в предыдущем разряде 2, в следующем 1образуя новое регулярное ИП, представляющее то уже запасено 3 монеты. Одну монету потратим на изменение предыдущего разряда, одну сохраним с единицейже число, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монетачто и <tex>d</tex>.}}

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

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

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

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

* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]] == Источники информации ==* 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, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 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* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]