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

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

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

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

25.08.2012, 12:21. Просмотров 2698. Ответов 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 и повторяем цикл наполнения
Это пока всё, что пришло на ум. Нужна помощь в реализации на языке и главное в подсчёте операции и вкл. этого элемента условия в решение. Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2012, 12:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача "Водолей" (C++):

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

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

6
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
25.08.2012, 12:24 #2
PG94, теория графов и поиск в ширину в частности Вам в помощь. А хотя, если постараться, то и перебор сляпать можно.
0
neske
1502 / 869 / 84
Регистрация: 26.03.2010
Сообщений: 2,982
25.08.2012, 12:35 #3
есть ссылка на задачу?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
25.08.2012, 12:36 #4
или тесты
0
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}.
Других решений задача не имеет.
0
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
25.08.2012, 16:32  [ТС] #6
Задача взята отсюда и является школьной:
ссылка на задачку
Думаю, что и решено должно быть соответствующим, но, быть может, и не самым оптимальным.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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
1
26.08.2012, 22:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2012, 22:21
Привет! Вот еще темы с ответами:

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Создать иерархию классов "Фирма", "Бухгалтер", "Сотрудник", "Зарплата" - C++
Само по себе понятие &quot;зарплата&quot; не особенно конкретное: оно включает и почасовую, и ставочную зарплату, и комиссионные, и процент с продаж....


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

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

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