Изменения
→Пример
Профилем будет пара <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>.
* Eсли <tex>i < n - 1</tex>, то <tex>i_1 + 1 = i_2</tex>; , иначе <tex>i_2 = 0 </tex>;
* Mожно так положить доминошку, накрывающую квадратик с номером <tex>i + 1</tex>, что после этого в <tex>p_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 <tex>p</tex>, int <tex>i</tex>):
'''if''' <tex>\mathtt{bit}(\mathtt{p, i + 1}) = \mathtt{0}</tex>
'''if''' <tex>i = n - 1</tex>
'''println'''('(", (<tex>((p - (2 << i)) << 1</tex>, " ", <tex>0, ")")</tex>
'''else'''
'''println'''<tex>("(", p - (2 << i)</tex>, ', '" ", <tex>i + 1, ')</tex>')
'''else'''
'''if''' <tex>\mathtt{bit}(\mathtt{p, i}) = \mathtt{0}</tex>
'''if''' <tex>i = n - 1 </tex>
'''println'''<tex>(('<', p << 1)</tex>, ', '" ", <tex>0, ')</tex>')
'''else'''
'''println'''<tex>('<', p + (1 << i)</tex>, ', '" ", <tex>(i + 1) mod % n, ')</tex>')
'''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> При такой реализации существует немало профилей только с одним переходом (например, у которых <tex>(i + 1)</tex>-й бит равен единице). Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть pr2 (и только он) получается из pr1, который, в свою очередь, получается из pr0. Тогда имеются такие соотношения: d[pr0, "pr1]=1, d[pr1, pr2]=1. Отождествить pr1 и pr2 -- это, по сути, заменить эти два соотношение на одно, то есть теперь d[pr0, pr1]=0 и d[pr1, pr2]=0, но d[pr0, pr2]=1, и так далее. Таким образом, возможно сокращение профилей не менее чем вдвое. Дальнейшие оптимизации мы оставляем читателю. В итоге получаем асимптотику 2nn (количество переходов, то есть время на вычисление a[i])"умножить на m равно O(2nnm). Она значительно лучше всего, что мы получали до сих пор, и это серьезный повод использовать изломанный профиль вместо обычного.
== См. также ==
