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

Задача "Водолей" - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
25.08.2012, 12:21     Задача "Водолей" #1
Вот условие:
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:
Наполнить сосуд A (обозначается >A).
Наполнить сосуд B (обозначается >B).
Вылить воду из сосуда A (обозначается A>).
Вылить воду из сосуда B (обозначается B>).
Перелить воду из сосуда A в сосуд B (обозначается как A>B).
Перелить воду из сосуда B в сосуд A (обозначается как B>A).
Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полностью наполняется.
Программа получает на вход три натуральных числа A, B, N, не превосходящих 104 Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible. Количество операций в алгоритме не должно превышать 105. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 105 операций.
Некоторые соображения:
  • если N>A и N>B, то невозможно
  • если А=B и N%A!=0, то невозможно
  • если N=A или N=B, то наполняем равный
  • определяем какой сосуд больший(v=max), а какой меньший(v=min)
  • Повторяем >min, min>max пока max!=N или сосуд полностью не заполнится
  • Если max полон, min пуст, а N литров мы так и не получили, то ответ - невозможно
  • Если же min не пуст, то max>,min>max и повторяем цикл наполнения
Это пока всё, что пришло на ум. Нужна помощь в реализации на языке и главное в подсчёте операции и вкл. этого элемента условия в решение. Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2012, 12:21     Задача "Водолей"
Посмотрите здесь:

C++ по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно
C++ Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64"
C++ Создать класс комплексных чисел и ввести операции: "+", "-", "*", "/".
Чтения структуры из файла (описать структуру с именем "ORDER": "счет плательщика"; "счет получателя"; "сумма, переводится банковской операцией") C++
C++ С++ консольное приложение win32, матерится на первое "pow" после "if", а на "system" говорит что неопределён.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
25.08.2012, 12:24     Задача "Водолей" #2
PG94, теория графов и поиск в ширину в частности Вам в помощь. А хотя, если постараться, то и перебор сляпать можно.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,689
25.08.2012, 12:35     Задача "Водолей" #3
есть ссылка на задачу?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
25.08.2012, 12:36     Задача "Водолей" #4
или тесты
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
25.08.2012, 14:36     Задача "Водолей" #5
Наверно, лучше посчитать, какие объемы вообще можно получить:
1) Если A=B, то тогда задача решается лишь в случае N=A.
2) Если A не равное B, то тогда пусть ради определенности A < B. В этом случае мы можем получить все объемы равные {kA: 0 < k <= A / B}, а также все объемы равные {B - kA : 0 < k <= A / B}.
Других решений задача не имеет.
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
25.08.2012, 16:32  [ТС]     Задача "Водолей" #6
Задача взята отсюда и является школьной:
ссылка на задачку
Думаю, что и решено должно быть соответствующим, но, быть может, и не самым оптимальным.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2012, 22:21     Задача "Водолей"
Еще ссылки по теме:

C++ В массиве структур студент с полями "ИМЯ" "ВОЗРАСТ" "УСПЕВАЕМОСТЬ" выполнить сортировку по успеваемости по возрастанию
C++ Вставить пробел после каждого символа "." "," "!" или "?", если за этими символами не следует пробел
Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.08.2012, 22:21     Задача "Водолей" #7
Цитата Сообщение от ramybozy Посмотреть сообщение
2) Если A не равное B, то тогда пусть ради определенности A < B. В этом случае мы можем получить все объемы равные {kA: 0 < k <= A / B}, а также все объемы равные {B - kA : 0 < k <= A / B}.
Других решений задача не имеет.
Имеет и очень много.
Например А=5, В=18.
Возможные N (обозначаю наливание и переливание воды как написано в условии задачи):
>A
A>B // N=5 в сосуде B
>A
A>B // N=10 в сосуде B
>A
A>B // N=15 в сосуде B
>A
A>B // N=2 в сосуде А
B>
A>B
>A
A>B // N=7 в сосуде B
>A
A>B // N=12 в сосуде B
>A
A>B // N=17 в сосуде B
>A
A>B // N=4 в сосуде A
B>
A>B
>A
A>B // N=9 в сосуде B
>A
A>B // N=14 в сосуде B
>A
A>B // N=1 в сосуде А
и т.д.
если продолжить дальше, можно увидеть, что если A=5, B=18 то можно набрать любое количество литров в пределах 1..18
Yandex
Объявления
26.08.2012, 22:21     Задача "Водолей"
Ответ Создать тему
Опции темы

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