Изменения

{{Определение|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>, где кроме 0 и 1 допустима 2 <tex>n</tex> обозначает количество разрядов в записи числе, <tex>d_i</tex> {{---}} <tex>i</tex>&ndash;й разряд числа.== Алгоритм ==''Примечание: этот алгоритм работает не за истинное <tex>O(1\leqslant i \leqslant n)</tex>. Например, чтобы прибавить причем <tex>d_i \in \{0,1 к 0111...111, нужно 2\}</tex> и <tex>O(\sum\limits_{i=1}^n)d_i \cdot 2^{i-1} = N.</tex> действий.''}}

Имеется числоЗаметим, записанное что в избыточной двоичной этой системе счисленияпредставление числа неоднозначно, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0например представление <tex>212</tex> эквивалентно <tex>1100</tex>.

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

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

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

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

# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.# Если <tex>d_1= Пример ==Рассмотрим пример для каждого варианта1</tex>, добавление то добавить в начало списка <tex>1 происходит в 3 разряд</tex>.

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

д) <tex>10020_(\dotsc 212\dotsc) \overset{2Inc} {\Rightarrow 10200_{2longmapsto}(\dotsc 220\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>1020_(\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 1000_overset{2Inc} {\longmapsto}(\dotsc 11)</tex> повторение алгоритма для 4 разряда, по варианту б .: Появление новой двойки:: <tex>1000_(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.:: <tex>(\Rightarrow 2000_dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2}\dotsc 0\dotsc 20\dotsc 2)</tex>(частный случай предыдущего).

ж) <tex>2020_{2} \Rightarrow 2000_{2}</tex> повторение алгоритма для 4 разрядаТаким образом мы видим, по варианту а что <tex>2000_{2} \Rightarrow 11000_{2}0</tex>всегда сохраняется.

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

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

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

г{{Определение|id=regular_rr|definition= Назовем представление '''регулярным''' (англ. ''regular'') Так как в текущем разряде было 1, в следующем 2, то уже запасено 3 монеты и еще 2 наши. 3 монеты потратим, что если между двумя разрядами равными <tex>b</tex> есть хотя бы следующему за 2 разряду установить 1, разряду с 2 установить один разряд отличный от <tex>b-1, текущему установить 0. Останется 2 монеты, которые распределятся между двумя единицами</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, в следующем 0образуя новое регулярное ИП, представляющее то уже запасено 2 монеты. Одну монету потратим на изменение предыдущего разрядаже число, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разрядечто и <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такой, в следующем что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, то уже запасено 3 монетыравен <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>.

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

Получается 2 монет достаточно для прибавления 1 к любому разряду== См. также ==* [[Амортизационный анализ]]* [[Представление целых чисел: прямой код, тогда наш алгоритм работает в среднем за <tex>O(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]