Изменения
→Пример
Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <tex>i</tex>-ю горизонталь сверху вниз, она переходит на предыдущую вертикаль и спускается до низу.
Профилем будет пара <tex><(p, i>)</tex>, в <tex>p</tex> будет информация о <tex>n + 1</tex> маленьком квадратике слева от базовой линии, имеющем с ней общие точки; <tex>i</tex> обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер <tex>i + 1</tex>. Горизонтали будем нумеровать с нуля, так что <tex>i</tex> пробегает значения от <tex>0</tex> до <tex>n - 1</tex>.
Для двух профилей <tex>pr1pr_1</tex> = <tex><p1(p_1, i1>i_1)</tex> и <tex>pr2 pr_2 = <p2(p_2, i2>i_2)</tex> положим <tex>d[pr1pr_1][pr2pr_2] = 1</tex> если и только если:
Легко заметить, что количество профилей увеличилось в <tex>2n</tex> раз (добавилось число от <tex>1</tex> до <tex>n</tex> и еще один бит). Но зато количество переходов резко сократилось с <tex>2^n</tex> до <tex>2</tex>.
<font color=green>//Для профиля (p, i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..n - 1)</font>
<font color=green>/ Функция bit(x,i), возвращающая единицу или ноль или i-й бит в двоичной записи числа x/</font>
print_all_links(int p, int i):
'''if''' <tex>\mathtt{bit}(\mathtt{p, i + 1}) = \mathtt{0}</tex>
'''if''' <tex>i = n - 1</tex>
'''println'''('(", (<tex>p - (2 << i)) << 1</tex>, " ", 0, ")")
'''else'''
'''println'''("(", p - (2 << i), ', ', i + 1, '>')
'''else'''
'''if''' <tex>\mathtt{bit}(\mathtt{p, i}) = \mathtt{0}</tex>
'''if''' <tex>i = n - 1 </tex>
'''println'''('<', p << 1, ', ', 0, '>')
'''else'''
'''println'''('<', p + (1 << i), ', ', (i + 1) mod n, '>')
'''if''' <tex>i < n - 1</tex> && <tex>\mathtt{bit}(\mathtt{p, i + 2}) = \mathtt{0}</tex>
'''println'''("(", <tex>p + (4 << i)</tex>, " ", <tex>i + 1</tex>, ")")
== См. также ==
