Изменения
Опечатка. Слово "дувумя" исправлено на "двумя".
{{Определение|id=knuth_counter|definition= '''Счетчик Кнута''' (англ. ''Сounter Knuth's Counter'') {{--- }} структура данных, представленная избыточной двоичной системой счисления, где в которой добавление единицы к любому разряду числу и вычитание единицы выполняется за <tex>O(1)</tex>.}}
Причем количество единиц между двойками может быть любое, в) Так как в текущем разряде было 1итоге это приведет к появлению тройки.Однако если между любой парой двоек всегда будет находиться хотя бы один<tex>0</tex>, то прибавив наши монеты к запасенной получим 3такой ситуации не возникнет. Одну потратимПокажем, что бы установить этот инвариантподдерживается после инкремента, рассмотрев возможные ситуации:: Число двоек не изменяется:: <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>(\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) \overset{Inc} {\longmapsto} (\dotsc 11)</tex>.: Появление новой двойки:: <tex>(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0, оставшиеся \dotsc 20\dotsc 2 потратим на повторение алгоритма для следующего разряда)</tex> (частный случай предыдущего).
{{Определение|id=regular_rr|definition= Смотри Назовем представление '''регулярным''' (англ. ''regular''), если между двумя разрядами равными <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>, образуя новое регулярное ИП, представляющее то же число, что и <tex>d</tex>.}} Чтобы добавить <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>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <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). Такое представление позволяет увеличивать произвольный разряд на единицу за константноевремя. Обновление указателя вперед происходит следующим образом: когда <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>. == См. также ==
* [[Амортизационный анализ]]
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]] == Источники информации ==* 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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]