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

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

Войти
Регистрация
Восстановить пароль
 
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
#1

Задача типа Водолей - C++

16.12.2013, 00:55. Просмотров 391. Ответов 0
Метки нет (Все метки)

Есть задача типа Водолей.

Дано n посудин емкостью по k_1, k_2,...,k_n каждая.
Нужно набрать P литров жидкости.

Допустимые действия:
- набирать воду до упора из бесконечного источника в любой сосуд.
- переливать из любого сосуда в любой пока один из них не будет полным ил пустой.
- выливать воду из сосуда

Найти минимальное количество действий для того чтоб в любом сосуде было нужное количество жидкости.


Подскажите в какую сторону копать. На первый взгляд это поиск в ширину на графе. Но как его организовать (и сам граф и тем более поиск). Перебор кажется не подойдет ибо не известно изначальное количество сосудов.

Если задача слишком сложная можно решить частичный вариант из 3 сосудов

Пример:
3 - сосуда
4 6 9 - их емкости
7 - нужное количество

минимальный твет кажется 4

* 4 6 9
0 0 0 0 (начальное состояние)
1 4 0 0 (наполнить 4-литровый)
2 0 4 0 (перелить из 4 все в 6-литровый)
3 0 4 9 (наполнить 9-литровый)
4 0 6 7 (перелить до заполнения из 9-и в 6-литровый до заполнения)
в 9-литровом профит)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2013, 00:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача типа Водолей (C++):

Задача "Исполнитель Водолей" - C++
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять...

Задача "Водолей" - C++
Вот условие: Некоторые соображения: если N>A и N>B, то невозможно если А=B и N%A!=0, то невозможно если N=A или N=B, то...

Исполнитель Водолей - C++
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять...

Задача типа double.C++ - C++
Сделать тип doubl который возвращает квадратный корень произведения первого на второй.(произведение не должно быть отрицательным). Не...

C++ задача. Функция типа int - C++
Разработать функцию типа int. которая возвращает меньшее среди кубов двух параметров.

Задача без использования типа string - C++
Слова текста из малых латинских букв записаны не менее чем через один пробел; БЕЗ ИСПОЛЬЗОВАНИЯ КОНСТРУКЦИИ STRING: а) написать программу...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2013, 00:55
Привет! Вот еще темы с ответами:

Задача на описание функции Power2(A, N) вещественного типа - C++
Описать функцию Power2(A, N) вещественного типа, находящую величину Aв степени N (A — вещественный, N — целый параметр) по следующим...

Задача наописание функции IsLeapYear(Y) логического типа - C++
Описать функцию IsLeapYear(Y) логического типа, которая возвращает True, если год Y (целое положительное число) является високосным, и...

Возврат объекта шаблонного типа от типа Type из специализации шаблона метода от того же типа - C++
Доброго времени суток, пишу класс содержащий несколько std::set от разных типов, нужно сделать метод возвращающий указатель на нужное...

Задача на описание функции Leng(x_A, y_A, x_B, y_B) вещественного типа - C++
Описать функцию Leng(xA, yA, xB, yB) вещественного типа, находящую длину отрезка AB на плоскости по координатам его концов:|AB| =((x_a-x_b...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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