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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
#1

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

25.08.2012, 12:21. Просмотров 2464. Ответов 6
Метки нет (Все метки)

Вот условие:
У исполнителя “Водолей” есть два сосуда, первый объемом 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++ В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" C++
Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) C++
C++ Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс"
Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
25.08.2012, 12:24     Задача "Водолей" #2
PG94, теория графов и поиск в ширину в частности Вам в помощь. А хотя, если постараться, то и перебор сляпать можно.
neske
1455 / 822 / 68
Регистрация: 26.03.2010
Сообщений: 2,809
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++ Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления"
Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" C++
C++ Задача "Исполнитель Водолей"

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru