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

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

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

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

25.08.2012, 12:21. Просмотров 2605. Ответов 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++
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять...

Задача "Гонки по улицам" (обход ориентированного графа) - C++
Здравствуйте,помогите с задачей,если можно с комметарием,чтобы разобраться.Спасибо На рисунке ниже изображен пример плана улиц для гонки....

Задача из книги "Програмирование - принципы и практика использования C++" - C++
Кто читал ету книгу, помогите разобратся с задачей с 12 главы. Никак не могу скомпилировать простую программу. Вот ее код: #include...

Задача "Максимальный подпалиндром" не могу поймать ошибку. - C++
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется...

Создать класс Account. Задача из книги Дейтелов "Как програмировать на С++" - C++
Начал изучение С++, прочитал главу "Введение в классы и объекты" в книге Дейтелов "Как програмировать на С++", ничего не поняв прочитал её...

задача по С++ "Мастям игральных карт условно присвоены следующие порядковые номера" - C++
Мастям игральных карт условно присвоены следующие порядковые номера:пики-1, трефы-2 , бубны-3, червы-4. Достоинству карт присвоены...

Задача "Дан номер года. Найти число дней в этом году." - C++
Дан номер года. Найти число дней в этом году. Указание. В современном (григорианском) календаре каждый год номер которого делиться на 4,...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
25.08.2012, 12:24     Задача "Водолей" #2
PG94, теория графов и поиск в ширину в частности Вам в помощь. А хотя, если постараться, то и перебор сляпать можно.
neske
1474 / 841 / 74
Регистрация: 26.03.2010
Сообщений: 2,889
25.08.2012, 12:35     Задача "Водолей" #3
есть ссылка на задачу?
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 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++
Дано натуральное число n. Найти сумму цифр числа, находящихся на четных позициях (старшая цифра числа находится на первой позиции). ...

в чем ошибка? задача на "сортировку массива" - C++
Подскажите в чем ошибка в коде. Я должен отсортировать массив по убыванию элементов. #include &lt;iostream&gt; #include &lt;conio.h&gt; ...

Динамическое программирование, задача "Уменьшение числа" - C++
Имеется натуральное число N (1 &lt;= N &lt;= 106). За один ход с ним можно произвести следующие действия: Вычесть единицу Разделить на два ...

Задача на "закрашивание" некоторых элементов матрицы - C++
Имеется матрица чисел 0 и 1 - это некое изображение 0 - белый 1 - черный цвета. Если единицы образуют собой какую нибудь замкнутую область...


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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 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     Задача "Водолей"
Ответ Создать тему
Опции темы

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