1. Спонсор публикаций Marketplace codeby. Сервис, который так долго ждали. При расчетах используем биткоин. Первый товар уже в продаже: Консультация на тему ИБ от Ondrik8

    Скрыть объявление
  2. Спонсор публикаций Marketplace codeby. Сервис, который так долго ждали. При расчетах используем биткоин. Второй товар маркетплейса: Надёжная обфускация вашей программы от PingVinich

    Скрыть объявление

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

Тема в разделе "Общие вопросы по С и С++", создана пользователем ned, 21 дек 2005.

Статус темы:
Закрыта.
  1. ned

    ned Гость

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

    KmeT Гость

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

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

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

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

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

    DAle Гость

    Репутация:
    0
    <!--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 в руки.
     
Загрузка...
Похожие Темы - Помогите кто сможет
  1. Celts
    Ответов:
    12
    Просмотров:
    3.222
  2. Gamlet
    Ответов:
    0
    Просмотров:
    2.075
  3. Gamlet
    Ответов:
    9
    Просмотров:
    5.302
  4. number27
    Ответов:
    0
    Просмотров:
    77
  5. Rina
    Ответов:
    0
    Просмотров:
    92
Статус темы:
Закрыта.

Поделиться этой страницей