Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
projest
0 / 0 / 0
Регистрация: 16.02.2014
Сообщений: 2
#1

Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. - C++

17.02.2014, 10:52. Просмотров 652. Ответов 4
Метки нет (Все метки)

Добрый день. Задали такое задание:

Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.

Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.

Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.

N<100. Количество наборов для каждого чиновника не превосходит 15.

Огромная просьба написать код. Если трудно, хотя бы обьяснить алгоритм что нужно сделать) Заранее спасибо)

Добавлено через 21 час 52 минуты
Актуально(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.02.2014, 10:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. (C++):

Определить порядок получения подписей минимизирующий сумму уплаченных взяток - C++
Добрый день! Задали такую лабу: Ребят, если не сложно кому, помогите с лабораторной: Есть министерство из N чиновников, где N...

Необходимо определить наилучший путь между указанными городами и вывести его стоимость - Pascal ABC
На пути из города А в город В расположено насколько станций,соединенных между собой железной дорогой. Известно что эти станции не лежат на...

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

Рассчитать, какое количество лет в среднем необходимо ожидать получения квартиры, и вывести на экран весь список с указанием ожидаемого года получения - Turbo Pascal
Имеется список учета нуждающихся в улучшении жилищных условий. Каждая запись этого списка содержит фамилию, имя, отчество и дату постановки...

В натуральном числе n поменять местами порядок цифр для получения наибольшего числа - Turbo Pascal
Вводится какое-то число n, к примеру, 2473, а программа должна поменять порядок следования цифр таким образом, чтобы получилось...

Стоимость лицензии - Windows
Если частное образовательное учереждение хочет поставить и использовать windows и Microsoft Office, то сколько минимально может стоить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ryuk
179 / 177 / 33
Регистрация: 10.06.2011
Сообщений: 871
17.02.2014, 11:00 #2
projest, о том что нужно делать написано у вас в задании. Выкладывайте свои наработки, говорите что не получается и старайтесь сделать что-то самим. Иначе вы здесь долго будете ожидать помощи, тем более с подобной задачей.
stikkas
19 / 19 / 6
Регистрация: 26.01.2014
Сообщений: 56
17.02.2014, 13:40 #3
Цитата Сообщение от projest Посмотреть сообщение
Огромная просьба написать код. Если трудно, хотя бы обьяснить алгоритм что нужно сделать)
берешь взятку и несешь тому, кто тебе эту задачу задал
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
18.02.2014, 15:17 #4
нужно уметь писать простую динамику на дереве.
в задаче говорится, что система чиновников образует дерево. приглядитесь, там об этом говорится) вот здесь:
Цитата Сообщение от projest Посмотреть сообщение
У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.
вопрос на понимание: кто представляет собой корень дерева.
ну теперь напишем динамику на дереве прям по определению. для каждой вершины известно множество переходов - взятка + набор чиновников. будем считать ответ в порядке обхода в глубину. выбираем для каждой вершины лучший для нас вариант перехода. потом, пользуясь этим ответом считаем ответ для вершины-родителя(т.е. начальника). ну и так придем к общему ответу.
farced
19 / 19 / 13
Регистрация: 03.05.2016
Сообщений: 98
13.10.2016, 15:07 #5
Используй стек
Так как могут быть потребованы подписи лишь непосредственных подчиненных, то для любого разумного способа получения лицензии подпись всех подписавших чиновников, кроме первого, используются в одном и только одном наборе. Таким образом, мы можем определить стоимость подписи любого чиновника как минимум по соответствующим ему набором сумм стоимостей подчиненных и взятии для набора. Таким образом, мы получаем простой и эффективный рекурсивный алгоритм определения стоимостей чиновников.

Но у этой задачи есть маленький подводный камень, а именно, должно быть заведено глобальное множество уже пройденных чиновников, что исключает повторную обработку этих чиновников. Сложность алгоритма - линейна по суммарному числу элементов в наборе.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.10.2016, 15:07
Привет! Вот еще темы с ответами:

Защита продукта путем получения лицензии - Программирование
Всем доброго времени суток! Ситуация простая. Написал программу, хочу ее защитить. В связи с эти 3 вопроса: 1. Как можно...

Что необходимо выполнить для получения пересекающихся поверхностей? - MathCAD
Что необходимо выполнить для получения пересекающихся поверхностей?

Ошибка получения лицензии разработчика metro приложений - C# WPF
Хочу попробовать писать программы в новом metro UI. Установил VS 2012 Express for Win8, пытаюсь получить лицензию разработчика (без нее...

AS 3.0 Что необходимо для получения доступа к свойствам mouseX и mouseY? - ActionScript
нужно ли подключать какие-нибудь библиотеки для использования mouseX и mouseY? погуглил, ничего особого в примерах не используют. но...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.10.2016, 15:07
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru