Комбинаторные алгоритмы. Backtracking. Пробирки

Имеется три пробирки по 100 мл, первые две пробирки с рисками (метками). Риски совпадают. Изначально, первая пробирка имеет 100 мл, другие пусты. Требуется написать программу, которая выясняет, можно ли отделить в третьей пробирке один миллилитр. Количество и сами риски задаются пользователем.

Как сказано в заголовке, здесь надо использовать комбинаторные алгоритмы. Думаю, можно как-то через backtracking решить.
Я не рассчитываю на код. Объясните пожалуйста, хотя бы на псевдокоде или хотя бы на пальцах алгоритм решения задачи.

У самого есть несколько вариантов, но не знаю, как связать это, и возможно ли сделать как-то рекурсивно.
Первое, что можно рассмотреть: граф, изображающий возможные состояния набора из трех пробирок и возможные переходы между ними. Но тут другой вопрос встает: как его правильно построить?

Второй вариант: льем во вторую пробирку до первой риски (или выливаем из первой до риски, не важно, думаю), сверяем, будет ли разница в один мл. Если нет, выливаем из второй в третью. Потом льем опять из первой во вторую. И так до конца повторяем, пока либо не найдем ответ, либо не закончится жидкость. А вот что потом...
Что-то мне это напомнило ханойские башни...

Может, у кого есть/были наработки или кто сможет подсказать алгоритм, помогите разобраться!

0

Сообщение от Metall_Version можно делить емкость пополам . и отнимать и добавлять известное количество жидкости. тут реально комбинаторика . нужно просто такими способами дойти до любого объема этой последовательности (2.4.8.16.32.64)

Как делить пополам? На глаз? Пользователь, к примеру, задал значения рисок: 3 20 41 70 в первой пробирке и 5 15 61 80 во второй. Как пополам-то делить?

Сообщение от Евгений В Мне только не понятно, как тут привязать уровень к расчетам. Тогда нужно вводить высоту. Т.е. не очень понятна эта часть: Цитата Сообщение от ctreloknik риски задаются пользователем

Что непонятно? Пользователь сам задал, какие метки есть. Хотя бы одна, но должна быть. Собственно, выше написано, как может быть размечено.

Добавлено через 2 минуты

Сообщение от Евгений В ctreloknik, Посмотрите здесь http://atpp.vstu.edu.ru/cgi-bi... id_prb=204

Спасибо, перед созданием темы, я прошерстил инет и видел этот материал. В том то и беда, что не знаю, как правильно сделать этот граф.

0

я думаю число можно еще больше уменьшить. но оно все равно не будет ровно 1

Добавлено через 2 минуты

Сообщение от ctreloknik Как делить пополам? На глаз? Пользователь, к примеру, задал значения рисок: 3 20 41 70 в первой пробирке и 5 15 61 80 во второй. Как пополам-то делить?

а как решать задачу не зная условия ? .. вы точнее скажите на каких отметках есть риски ... Или же риски мы сами ставим . А то - решите мне то не знаю что
а делить можно и без рисок я постами выше это очень подробно описал .

0

Сообщение от Metall_Version я думаю число можно еще больше уменьшить. но оно все равно не будет ровно 1

Вот, почти такое же условие: http://atpp.vstu.edu.ru/cgi-bi... id_prb=204
Разве что я могу задать (как оказалось уже сегодня), разные метки на двух пробирках. Да не суть важно это.
Вот представьте, что вам заказчик дал такое ТЗ (в моем случае, это препод). Вы же не будете к нему приходить с пробирками и на глазах у него это переливать?

Добавлено через 1 минуту

Сообщение от Metall_Version Или же риски мы сами ставим . А то - решите мне то не знаю что а делить можно и без рисок я постами выше это очень подробно описал .

Сказал же, пользователь сам задает отметки (они же риски). Перечитайте еще раз вот это: "Пользователь, к примеру, задал значения рисок: 3 20 41 70 в первой пробирке и 5 15 61 80 во второй." (В милилитрах, конечно же)

0

Сообщение от ctreloknik Вот представьте, что вам заказчик дал такое ТЗ (в моем случае, это препод).

зачем браться за задания в которых не компетентен. в данном случае это математика.

я без понятия честно говоря как решить такую задачу .когда входные данные не известны даже.

Добавлено через 1 минуту

Сообщение от ctreloknik Сказал же, пользователь сам задает отметки (они же риски). Перечитайте еще раз вот это: "Пользователь, к примеру, задал значения рисок: 3 20 41 70 в первой пробирке и 5 15 61 80 во второй." (В милилитрах, конечно же)

я думал пользователь это я или тот кто решает задачу. то есть я могу на свое усмотрение задавать риски . теперь понятно все удачи вам в этой задачке

0

Сообщение от Metall_Version зачем браться за задания в которых не компетентен. в данном случае это математика. я без понятия честно говоря как решить такую задачу .когда входные данные не известны даже.

если бы я сам брал задачу - одно дело, другое, когда тебе ее самому дают, ибо это лаба. никакая это не математика.
какие еще данные на вход? не знаю, в какой раз говорю, но пользователь сам вводит, какие метки есть у пробирок. все! дальше тыкает кнопочку и программа считает, есть ли там решение.
пример данных входа:
Риски 1 пробирки: 3 20 41 70
Риски 2 пробирки: 5 15 61 80

0

Сообщение от ctreloknik Риски 1 пробирки: 3 20 41 70 Риски 2 пробирки: 5 15 61 80

1) допустим, у нас есть бесконечный резервуар и у нас есть риска на 100 мл.
рассмотрим действия которые мы можем сделать.
- набрать первую до риски и отлить до меньшей риски во второй
входные данные - 3, 20, 41, 70, отнимаем 5, 15, 61, 80(если можем)
отливаем от полной : 95, 85, 39, (20 исключаем, есть такая отметка)
от 70 : 65, 55, 9
от 41: 36, 29
от 20: 15, 5 - исключаем так как есть такие отметки
- набрать вторую до риски и долить до края от первой, тогда входные данные будут такие:
входные данные - 3, 20, 41, 70, отнимаем 95, 85, 39, 20(если можем)
от 100: получим значения рисок второй пробирки - не надо
от 70: 31 и 50
от 41 : 2 и 20(не сохраняем)

вот и вырисовался алгоритм.
1) создаем какой-то класс для сохранения действий(Action например)
2) создаем словарь: Dictinary<int, Action> чтоб хранить все возможные значения, которые можем получить
3) заполняем словарь входными данными - значения рисок пробирок
4) выполняем определенное действие над каждым значением в словаре - в результате получаем новое значение для словаря: новый ключ(к-во мл) и новый путь для этого. если в словаре есть ключ с меньшим количеством действий - то не сохраняем, если с большим - то заменяем.
5) циклически выполняем действия пока не получим искомое значение - путь(порядок действий) к нему уже сохранен

Добавлено через 2 минуты
P.S. не претендую на эффективность алгоритма, наверняка можно найти более эффективное решение. например, построение графа и поиск пути по нему.

1