Задача "Водолей"

@PG94 · Регистрация: 15.01.2012

Студворк — интернет-сервис помощи студентам

Вот условие:

У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:
Наполнить сосуд A (обозначается >A).
Наполнить сосуд B (обозначается >B).
Вылить воду из сосуда A (обозначается A>).
Вылить воду из сосуда B (обозначается B>).
Перелить воду из сосуда A в сосуд B (обозначается как A>B).
Перелить воду из сосуда B в сосуд A (обозначается как B>A).
Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полностью наполняется.
Программа получает на вход три натуральных числа A, B, N, не превосходящих 10⁴Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible. Количество операций в алгоритме не должно превышать 10⁵. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 10⁵ операций.

Некоторые соображения:

если 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 и повторяем цикл наполнения

Это пока всё, что пришло на ум. Нужна помощь в реализации на языке и главное в подсчёте операции и вкл. этого элемента условия в решение. Спасибо.

@Dani · 25.08.2012, 12:24

PG94, теория графов и поиск в ширину в частности Вам в помощь. А хотя, если постараться, то и перебор сляпать можно.

@neske · 25.08.2012, 12:35

есть ссылка на задачу?

@Dani · 25.08.2012, 12:36

или тесты

@ramybozy · 25.08.2012, 14:36

Наверно, лучше посчитать, какие объемы вообще можно получить:
1) Если A=B, то тогда задача решается лишь в случае N=A.
2) Если A не равное B, то тогда пусть ради определенности A < B. В этом случае мы можем получить все объемы равные {kA: 0 < k <= A / B}, а также все объемы равные {B - kA : 0 < k <= A / B}.
Других решений задача не имеет.

@PG94 · 25.08.2012, 16:32 **[ТС]**

Задача взята отсюда и является школьной:
ссылка на задачку
Думаю, что и решено должно быть соответствующим, но, быть может, и не самым оптимальным.

valeriikozlov · 26.08.2012, 22:21

Сообщение от 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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	25.08.2012, 12:24
	PG94, теория графов и поиск в ширину в частности Вам в помощь. А хотя, если постараться, то и перебор сляпать можно. 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	25.08.2012, 12:35
	есть ссылка на задачу? 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	25.08.2012, 12:36
	или тесты 0

@ramybozy 9 / 9 / 1 Регистрация: 01.07.2012 Сообщений: 138
	25.08.2012, 14:36
	Наверно, лучше посчитать, какие объемы вообще можно получить: 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 [ТС]
	Задача взята отсюда и является школьной: ссылка на задачку Думаю, что и решено должно быть соответствующим, но, быть может, и не самым оптимальным. 0