Re: Триомино
От: 67108864 http://ajtkulov.blogspot.com
Дата: 07.04.13 18:19
Оценка: 1 (1)
K>Задача наверное многим знакома. Да и вряд ли сложна для вас (в отличие от меня). Взято из книги А. Левитина. Интересно, сколько у вас времени ушло на решение этого задания.

K>

K>Триомино. Триомино — элемент мозаичного заполнения в форме L, образованный тремя квадратами шахматной доски. Задача состоит в покрытии триомино шахматной доски размером 2^n (2 в степени n) на 2^n с одной вырезанной в произвольном месте клеткой. Триомино должны покрывать все клетки, за исключением вырезанной, без пропусков и перекрытий. Разработайте декомпозиционный алгоритм для решения этой задачи.


K>В книжке был рисунок. Так, на всякий случай, как выглядит триомино:

K>. . . .
K>. O . .
K>. O O .
K>. . . .
K>. . . .

таже штука работает и в n-мере (предыдущий вариант, n = 2). Триомино = куб 2^n без одной клетки. Требуется разбить n-мерный куб размером 2^k, в котором также нет одной клетки.
Решается аналогично.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.