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

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

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

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

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

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

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

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

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

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

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

Добавлено через 21 час 52 минуты
Актуально(
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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, то сколько минимально может стоить...

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

Но у этой задачи есть маленький подводный камень, а именно, должно быть заведено глобальное множество уже пройденных чиновников, что исключает повторную обработку этих чиновников. Сложность алгоритма - линейна по суммарному числу элементов в наборе.
0
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? погуглил, ничего особого в примерах не используют. но...


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

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

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