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

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

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

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

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

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

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

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

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

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

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

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

Необходимо создать минимальный проект-образец в DEV C++ C++
Для каждого массива определить минимальный по модулю элемент C++
Массивы, нужно определить минимальный элемент, вывести его значение и индекс... C++
C++ Разработать программу «Стоимость компьютера», позволяющую вычислять стоимость комплекта для АРМ различных специалистов
Разработать программу «Стоимость компьютера», позволяющую вычислять стоимость комплекта для АРМ различных специалистов C++
Вычисление степени, в которую необходимо возвести 2 для получения числа, которое <= заданному числу C++
C++ Необходимо определить длину строки, вывести строку, которая состоит из двух символов, чередующиеся длины n
C++ Для каждой строки матрицы определить минимальный элемент, среди которых найти максимальный
C++ Вывести информацию о товарах, имеющихся на складе в количестве более ста и определить них суммарную стоимость
C++ В массиве необходимо удалить элементы, индекс которых кратен 4, сохранив прежним порядок оставленных членов
C++ Определить порядок получения подписей минимизирующий сумму уплаченных взяток
Определить минимальное количество школьников для получения заданного распеределения оценок C++

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

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

Но у этой задачи есть маленький подводный камень, а именно, должно быть заведено глобальное множество уже пройденных чиновников, что исключает повторную обработку этих чиновников. Сложность алгоритма - линейна по суммарному числу элементов в наборе.
Yandex
Объявления
13.10.2016, 15:07     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.
Ответ Создать тему
Опции темы

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