55
правок
Изменения
Нет описания правки
<code>
'''function''' genBinAntiGray(n: '''int'''):
'''for''' i = 1 '''to ''' 2 ** (n - 1)
v = getMirrorGray(i, n)
print(v)
Обозначим за <tex>G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex>\overline G_i</tex> — его инверсию.
Тогда вектора будут располагаться в таком порядке:
:... <tex>\dots</tex> <br>
:<tex>G_i</tex> <br>
:<tex>\overline G_i</tex> <br>
:<tex>\overline G_{i+1}</tex> <br>
:<tex>G_{i+2}</tex> <br>
:...<tex>\dots</tex>
<tex>G_i</tex> и <tex>\overline G_i</tex> отличаются во всех битах. <br>
Если <tex>G_i</tex> и <tex>G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex>G_i</tex> совпадает с <tex>G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex>\overline G_i</tex> и <tex>G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
{{Определение
|definition=
'''Троичный код антигрея''' (англ. ''Trinary Anti-Gray Code'') {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
}}
В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
=== Алгоритм генерации ===
Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить сначала сам этот вектор, потом <tex>2</tex> его поразрядных циклических сдвига (каждый отдельный бит увеличиваем на <tex>1</tex>).
<br>Например, если мы имеем вектор <tex>021</tex>, то вы выведем: <tex>021</tex>, <tex>102</tex>, <tex>210</tex>.
<code>
'''function''' genTernAntiGray(n: '''int'''):
'''for''' v = <000..0> '''to ''' <022..2> <span style="color:Green"> // троицчные троичные вектора длины <tex>n</tex> </span> '''for'''int i = 0 '''to ''' 2
print(v)
digitCircleShift(v)
Обозначим <tex>i</tex>-ый троичный вектор как <tex>G_i^0</tex>, его первый и второй циклический сдвиги как <tex>G_i^1</tex> и <tex>G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
:... <tex>\dots</tex> <br>
:<tex>G_i^0</tex> <br>
:<tex>G_i^1</tex> <br>
:<tex>G_i^2</tex> <br>
:<tex>G_{i+1}^0</tex> <br>
:...<tex>\dots</tex>
<tex >G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах. <br>
Если говорить о векторах как о троичных числах, то <tex>G_{i+1}^0</tex> получено из <tex>G_i^0</tex> прибавлением единицы, это значит, что у <tex>G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex>G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex>G_{i}^2</tex> получено из <tex>G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex>G_{i+1}^0</tex> некоторые биты такие же, как в <tex>G_{i}^0</tex>, остальные на единицу больше; в числе <tex>G_{i}^2</tex> все биты на один меньше по сравнению с <tex>G_{i}^0</tex>, значит <tex>G_{i}^2</tex> и <tex>G_{i+1}^0</tex> различны во всех битах.
