1632
правки
Изменения
м
rollbackEdits.php mass rollback
{| border="0"
|align="left" colspan="4"|
*<tex>\mathtt{GrayCode}</tex> {{---}} двумерный массив типа '''boolean''', в котором <tex>\mathtt{GrayCode[a, b]}</tex> {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея.,*<tex>\mathtt{p}</tex> {{---}} Счетчик количества уже имеющихся кодов,*<tex>\mathtt{t}</tex> {{---}} Показывает количество кодов в <tex>(a-1)</tex>-м коде Грея.
<code>
buildCode(n):
Для кода длиной <tex>1</tex> бит утверждение проверяется непосредственно.
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i</tex> выполняется <tex>е\enskip enspace M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
Для любого <tex>x < 2^n</tex> выполняется <tex>\enskip enspace L_x = 0M_x</tex> и, по условию, равно
<tex>L_x = 0(x_{n-1}x_{n-2} \dots x_{0} \oplus 0x_{n-1}x_{n-2} \dots x_{1})</tex> раскрыв скобки, получим новое выражение <tex>L_x</tex>:
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex>
Для любого <tex>x \geqslant 2^n</tex> выполняется <tex>\enskip enspace L_x = 1</tex><tex>M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть
<tex>L_x = 1(\overline {x_{n-1} x_{n-2} \dots x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2} \dots x_{1}})</tex> что по свойству '''xor''' (<tex>\neg x \oplus \neg y = x \oplus y</tex>) равно
