1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|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>–й разряд числа <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>
}}
==== Инвариант с нулем ====
Проблемой может оказаться появление двух последовательных двоек, при этом перое первое правило может породитьтройку. То есть недопустима следующая ситуация : <tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>. В свою очередь такая ситуация получается из этой : <tex>(\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex>.
Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.
Однако если между любой парой двоек всегда будет находится находиться хотя бы один<tex>0</tex>, то такой ситуации не возникнет. Покажем, что что этот инвариант
поддерживается после инкремента, рассмотрев возможные ситуации:
: Число двоек не изменяется
==== Пример ====
В таблице можно увидеть как будет изменятья изменяться представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):
{| class="wikitable"
{{Определение
|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> {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</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>.
}}
