Изменения

== Пример ==

Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <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>.

'''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>-й бит равен единице).

Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть <tex>pr_2</tex> (и только он) получается из <tex>pr_1</tex>, который, в свою очередь, получается из <tex>pr_0</tex>. Тогда имеются такие соотношения: <tex>d[pr_0, pr_1] = 1</tex>, <tex>d[pr_1, pr_2] = 1</tex>. Отождествить <tex>pr_1</tex> и <tex>pr_2</tex> {{---}} это, по сути, заменить эти два соотношение на одно, то есть теперь <tex>d[pr_0, pr_1] = 0</tex> и <tex>d[pr_1, pr_2] = 0</tex>, но <tex>d[pr_0, pr_2] = 1</tex>, и так далее.

Таким образом, возможно сокращение профилей не менее чем вдвое. Дальнейшие оптимизации мы оставляем читателю.

В итоге получаем асимптотику <tex>O(2^nnm)</tex>. Она значительно лучше всего, что мы получали до сих пор, и это серьезный повод использовать изломанный профиль вместо обычного.