разреза, обходим


разреза, обходим справа, т.е. при движении сверху вниз на каждом шаге либо обходим справа выступающую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует 1, отсутствие обхода - 0. На рисунке сечение выделено «жирной» линией, ему соответствует двоичное число 00100011 (35). Количество различных сечений 2i (пронумеруем их от 0 до 2i-1), где i -длина комнаты. Не будем пока учитывать то, что некоторые из сечений не могут быть получены. Обозначим парой (k,j) комнату с фиксированной длиной i, правый край которой не ровный, а представляет собой сечение с номером k. B[k,j] - количество вариантов укладки паркета в такой комнате. Задача в такой постановке сводится к нахождению B[0,j] - количество укладок паркета в комнате размером (i,j) с ровным правым краем. Считаем, что B[0,0]=1 при любом i, ибо комната нулевой ширины, нулевого сечения и любой
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz