Народ, может кто подскажет, как решается эта задачка. А то никак не получается алгоритм найти.

На столе стоит стакан, основанием которого является квадрат 3х3, а высота равна h. Рассмотрим куб 2х2х2, из которого выкинули некоторые кубики 1х1х1 (не все). Назовем это фигурой. Есть набор из n фигур. Возникает вопрос: сколькими способами можно разместить фигуры в стакане так, чтобы полностью его заполнить, при этом фигуры не разрешается поворачивать или отражать.

Здравствуйте, Аноним, Вы писали:

А>Народ, может кто подскажет, как решается эта задачка. А то никак не получается алгоритм найти.

А>На столе стоит стакан, основанием которого является квадрат 3х3, а высота равна h. Рассмотрим куб 2х2х2, из которого выкинули некоторые кубики 1х1х1 (не все). Назовем это фигурой. Есть набор из n фигур. Возникает вопрос: сколькими способами можно разместить фигуры в стакане так, чтобы полностью его заполнить, при этом фигуры не разрешается поворачивать или отражать.

Решение навскидку (не очень шустрое).

Будем рассматривать двумерные "слои" стакана, то есть квадраты 3*3. Заметим, что любая фигура находится лишь в двух слоях. Поэтому мы можем заполнять слои стакана по очереди, при чем так, что после заполнения очередного слоя, следующий за ним будет заполнен частично, а остальные будут полностью пустые.

Существует 2^9 вариантов частичного заполнения слоя. Занумеруем эти варианты от 0 до 2^9-1, назовем это число состоянием. Теперь просчитаем для каждого состояния i количество способов полного заполнения текущего слоя и получения на следующем слое состояния j. То есть получим

F(i,j) = количеству вариантов полного заполнения слоя из начального состояния i (при чем следующий слой изначально пуст) и получения на следующем слое состояния j.

Находить значения этой функции можно по-разному, можно попробовать построить значения перебором, однако это может быть слишком медленно. Либо привлечь подобный рассматриваемому алгоритм на меньшей размерности.

Затем просчитаем значение функции G

G(i,j) = количество вариантов полного заполнения первых i слоев и получения состояния j на i+1 слое

G(0,j) = 1, j = 0
G(0,j) = 0, j > 0 
G(i,j) = СУММ(G(i-1, k)*F(k,j)), i > 0

Ответом задачи будет являться G(h+1, 0).

Сорри, если сильно сумбурно, ночь на дворе

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Аноним, Вы писали:

А>>Народ, может кто подскажет, как решается эта задачка. А то никак не получается алгоритм найти.

А>>На столе стоит стакан, основанием которого является квадрат 3х3, а высота равна h. Рассмотрим куб 2х2х2, из которого выкинули некоторые кубики 1х1х1 (не все). Назовем это фигурой. Есть набор из n фигур. Возникает вопрос: сколькими способами можно разместить фигуры в стакане так, чтобы полностью его заполнить, при этом фигуры не разрешается поворачивать или отражать.

_DA>Решение навскидку (не очень шустрое).

_DA>Будем рассматривать двумерные "слои" стакана, то есть квадраты 3*3. Заметим, что любая фигура находится лишь в двух слоях. Поэтому мы можем заполнять слои стакана по очереди, при чем так, что после заполнения очередного слоя, следующий за ним будет заполнен частично, а остальные будут полностью пустые.

_DA>Существует 2^9 вариантов частичного заполнения слоя. Занумеруем эти варианты от 0 до 2^9-1, назовем это число состоянием. Теперь просчитаем для каждого состояния i количество способов полного заполнения текущего слоя и получения на следующем слое состояния j. То есть получим

_DA>F(i,j) = количеству вариантов полного заполнения слоя из начального состояния i (при чем следующий слой изначально пуст) и получения на следующем слое состояния j.

_DA>Находить значения этой функции можно по-разному, можно попробовать построить значения перебором, однако это может быть слишком медленно. Либо привлечь подобный рассматриваемому алгоритм на меньшей размерности.

_DA>Затем просчитаем значение функции G

_DA>G(i,j) = количество вариантов полного заполнения первых i слоев и получения состояния j на i+1 слое

_DA>

_DA>G(0,j) = 1, j = 0
_DA>G(0,j) = 0, j > 0 
_DA>G(i,j) = СУММ(G(i-1, k)*F(k,j)), i > 0
_DA>

_DA>Ответом задачи будет являться G(h+1, 0).

_DA>Сорри, если сильно сумбурно, ночь на дворе

Спасибо за решение )) Только вот тут проблема одна: не факт, что слои можно заполнять полностью, ибо фигуры могут быть такой формы, что полное заполнение слоя невозможно, если конечно там не присутствуют фигуры 1х1, которые могут встать в любую "дырку".

Здравствуйте, Аноним, Вы писали:

[skipped]

А>Спасибо за решение )) Только вот тут проблема одна: не факт, что слои можно заполнять полностью, ибо фигуры могут быть такой формы, что полное заполнение слоя невозможно, если конечно там не присутствуют фигуры 1х1, которые могут встать в любую "дырку".

Если нельзя будет заполнить слой полностью из начального состояния i, то соответствующие значения функции F(i,j) будут равны 0 для любого j. Или я что-то не так понял?

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Аноним, Вы писали:

_DA>[skipped]

А>>Спасибо за решение )) Только вот тут проблема одна: не факт, что слои можно заполнять полностью, ибо фигуры могут быть такой формы, что полное заполнение слоя невозможно, если конечно там не присутствуют фигуры 1х1, которые могут встать в любую "дырку".

_DA>Если нельзя будет заполнить слой полностью из начального состояния i, то соответствующие значения функции F(i,j) будут равны 0 для любого j. Или я что-то не так понял?

Вероятно я что-то не понимаю. Если значение ф-ии = 0, то слой вообще остаётся пустым?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, _DAle_, Вы писали:

_DA>>Здравствуйте, Аноним, Вы писали:

_DA>>[skipped]

А>>>Спасибо за решение )) Только вот тут проблема одна: не факт, что слои можно заполнять полностью, ибо фигуры могут быть такой формы, что полное заполнение слоя невозможно, если конечно там не присутствуют фигуры 1х1, которые могут встать в любую "дырку".

_DA>>Если нельзя будет заполнить слой полностью из начального состояния i, то соответствующие значения функции F(i,j) будут равны 0 для любого j. Или я что-то не так понял?

А>Вероятно я что-то не понимаю. Если значение ф-ии = 0, то слой вообще остаётся пустым?

Значение функции — это количество вариантов. Если заполнить слой невозможно, то и количество вариантов заполнения будет равно нулю.

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, _DAle_, Вы писали:

_DA>>>Здравствуйте, Аноним, Вы писали:

_DA>>>[skipped]

А>>>>Спасибо за решение )) Только вот тут проблема одна: не факт, что слои можно заполнять полностью, ибо фигуры могут быть такой формы, что полное заполнение слоя невозможно, если конечно там не присутствуют фигуры 1х1, которые могут встать в любую "дырку".

_DA>>>Если нельзя будет заполнить слой полностью из начального состояния i, то соответствующие значения функции F(i,j) будут равны 0 для любого j. Или я что-то не так понял?

А>>Вероятно я что-то не понимаю. Если значение ф-ии = 0, то слой вообще остаётся пустым?

_DA>Значение функции — это количество вариантов. Если заполнить слой невозможно, то и количество вариантов заполнения будет равно нулю.

Извиняюсь, сам ступил. Забыл, что стакан полностью надо заполнить