Помогите кто сможет написать прогу на с++.

[ned]

Помогите кто сможет написать прогу на с++.
Задача следующего содержания: Вася положил на стол N выпуклых K-гранников и N различных типов наклеек, каждой по K штук . Кто-то наклеил наклейки на грани, по одной на грань. Расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.
Всем откликнувшимся респект и уважуха, и естественно вознаграждение. Заранее спасибо.

 

[KmeT]

Так как, не определенны условия видимости, примем вырожденный случай- не видна только грань, на котрой стоит многогранник.

Условие не опеределяет количество наклеек каждого типа и не гарантирует что на каждом многограннике не может быть несколько наклеек одного типа.

Отсюда, имхо, следуте использовать какой-нибудь метод усеченного перебора.
Первый пришедший на ум алгоритм таков:
Для каго-то одного типа(хотя стоит сначала опредлить тип наклеек, которых меньше всего и\или которые расположены на наименьшем количестве многогранников, этим можно сущщественно уменьшить перебор) находим все комбинации удовлетворяющие условию видимости.

Далее проверяем только эти полученные коотдинаты на других типах и постепеноо отсеивам не подходящие.

Найдеюсь данный флуд будет полезен, если бы не сессия, может быть и запостил исходник

 

[DAle]

<!--QuoteBegin-ned+21:12:2005, 16:45 -->
<span class="vbquote">(ned @ 21:12:2005, 16:45 )</span><!--QuoteEBegin-->Помогите кто сможет написать прогу на с++.
Задача следующего содержания: Вася положил на стол N выпуклых K-гранников и N различных типов наклеек, каждой по K штук . Кто-то наклеил наклейки на грани, по одной на грань. Расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.
Всем откликнувшимся респект и уважуха, и естественно вознаграждение. Заранее спасибо.

[snapback]28643" rel="nofollow" target="_blank[/snapback]​

[/quote]

Переформулируем задачу.
...Расставить многогранники таким образом, чтобы все многогранники стояли на гранях с наклейками различных типов.

Построим двудольный граф. Первая доля графа - многогранники, вторая - типы наклеек. Если на многогранник i наклеена наклейка типа j, то строим ребро между вершиной i первой доли и вершиной j второй доли графа.
Теперь находим совершенное паросочетание в построенном двудольном графе. То есть паросочетание мощности N. Его ребра и будут являться ответом задачи.

Построение максимального паросочетания в двудольном графе задача стандартная и избитая, так что google в руки.