ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alex Danchenko                       2:450/242.27   07 Apr 2003  12:17:15
 To : Artur Mogozov
 Subject : Покрытие поля
 -------------------------------------------------------------------------------- 
 

 
  | Как-то <06 Апр 03, 15:42>, Artur Mogozov писал All насчет "Покрытие поля".
  AM>  Задача. Дано поле (максимум 9x9). Есть плитки 2x1, и уголки (квадраты
  AM> 2x2 без одной клетки). Hеобходимо подсчитать количество способов
  AM> укладки поля плитками.
 
 Один из методов решения такой задачи следующий (добавим еще условие того, что
 некоторые клетки поля могут быть изначально заполнены). Заметим, что постановка
 любой фигуры влияет только на 2 строки. Поэтому рассмотрим сначала только 2
 строки, причем первая строка заполнена некоторым образом (число от 0 до 511), а
 вторая - пустая. Теперь найдем количество вариантов полного заполнения первой
 строки с помощью деталей, так чтобы вторая строка равнялась j (j - число,
 битовое представление которой совпадает со второй строкой). Таким образом
 получаем матрицу A, элемент которой A[i,j] = количеству полного щаполнения
 строки = i, при которых следующая строка будет равняться j, если до этого она
 была пустой. Сформировать эту матрицу можно различными методами (наверное пойдет
 даже обычный перебор).
 
 Теперь рассмотрим функцию F[i,j], где значение функции - количество полного
 заполнения первых i-1 строк мозаики, при которых i-ая строка = j. Ответ задачи =
 F[n+1,0]. Теперь выясним, как посчитать значение функции. Предположим, что мы
 знаем все значения функции для i<=k. Hайдем значение функции для i=k+1.
 
 F[i,v or l]=Сумме(F[i-1,j]*A[j,v]), где j = от 0 до 2^m-1, l - значение i-ой
 строки мозаики (считаем, что значение n+1 строки = 2^m-1), а v такие, что v and
 l = 0.
 То есть, рассматривая i-ую строку = j, мы умножаем значение функции F[i,j] на
 количество вариантов полного заполнения строки этой строки, так чтобы следующая
 строка в результате была равной v, притом таким образом, чтобы возможно было
 выполнить такое заполнение, то есть v and l = 0. Тогда получившаяся следующая
 строка равна v or l.
 
 Hадеюсь, примерно понятно объяснил. ;)
 
  Yours sincerely
  Alex Danchenko (DAle)
 
 --- GoldED+/W32 1.1.5-20010807
  * Origin: FAMI hostel (2:450/242.27)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Покрытие поля   Artur Mogozov   06 Apr 2003 15:42:57   Покрытие поля   Alex Danchenko   07 Apr 2003 12:17:15