497
правок
Изменения
→Избыточное представление чисел
где <tex> d_i \in \{0, 1, ..., b\} </tex>, <tex> i \in \{0, 1, ..., n\} </tex>
}}
{{Определение
|id=
|neat =
|definition=
Назовем <tex>b</tex>-арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными <tex>b</tex> , найдется цифра, отличная от <tex>b-1</tex>.
}}
{{Определение
|id=
|neat =
|definition=
Пусть <tex>L(i)</tex> — номер разряда, отличного от <tex>b-1</tex> и ближайшего слева от <tex>i</tex>-го разряда в регулярном <tex>b</tex>-арном избыточном представлении <tex>d = d_n, ... d_0</tex>.
<br>
Определим <tex>L'(i)</tex> следующим образом:
*<tex>L'(i) = L(i)</tex> , если <tex>d_i \in \{b-1, b-2\}</tex> и <tex>d(L(i))=b</tex>;
*<tex>L'(i)</tex> — произвольное число <tex>>i</tex>, если <tex>d_i \in \{b-1, b-2\}</tex> и <tex>d(L(i))<b-1</tex>;
*<tex>L'(i)</tex> — не определено, если <tex>d \notin \{b-1, b-2 \}</tex> .
<br>
Величину <tex>L'(i)</tex> будем называть прямым указателем.
}}
===фиксация цифры===
Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, (Fix(i)) назовем операцию, заключающуюся в обнулении цифры <tex>d_i</tex> и инкрементировании цифры <tex>d_{i+1}</tex>, при этом если <tex>i=n</tex> , то полагаем d_{i+1} = 1. При каждом выполнении операции фиксации будем обновлять значение <tex>L'(i)</tex>. Очевидно, при <tex>b>2</tex> операцию <tex>Fix(i)</tex> можно выполнить следующим образом:
<code>
if(<tex>d_i</tex>=b)
<tex>d_i</tex>:=0;
<tex>d_{i+1} =d_{i+1}</tex> + 1;
if(<tex>d_{i+1}</tex>=b-1)
L'(i):=L'(i+1)
else
L'(i):= i+1;
</code>
===инкремент===
Инкрементирование <tex>i</tex>-й цифры избыточного представления <tex>d</tex> <tex>Inc(i)</tex> можно выполнить так:
<code>
Fix(i);
if(<tex>d_i</tex> = b - 1) or (<tex>d_i</tex> = b - 2)
Fix(L'(i));
d_i:=<tex>d_i</tex>+1;
Fix(i);
</code>
==Корневой счетчик==
