Комментарии 29
никогда не понимал, как самуэль джексон так быстро ее решил в экстремальной ситуации. я сидел тупил минут 5.
о, превью изменилось. ну теперь мой камент не имеет смысла. спасибо, автор.
Казалось бы такая мелочь, а решение уже совсем другое (если вообще есть)
Правильная постановка задачи, уже половина решения.
формально если канистры симметричные, то, канистру наклонить и выливать воду пока она своей поверхностью не "рассечет" канистру по диагонали от одного края на днище до диаметрально противоположного края на верхнем срезе. Вернуть канистру в нормальное положение. то мы получим четко пол канистры. 5/2=2,5л, 3/2=1,5л, 2,5+1,5=4л, но такое решение упирается в симметрию формы
если вообще есть
Я так полагаю, что есть ещё какая-то пустая безразмерная ёмкость, в которую нужно будет отлить вторые 4 литра? Тогда
<3, 5, 0> : [1->3] :
<0, 5, 3> : [2->1] :
<3, 2, 3> : [1->3] :
<0, 2, 6> : [2->1] :
<2, 0, 6> : [3->2] :
<2, 5, 1> : [2->1] :
<3, 4, 1> : [1->3] : <0, 4, 4>где <...> — векторы состояния (объём воды в емкостях 1, 2 и 3),
и [x->y] — переходы "перелить из x в y сколько можно"
Пустая ёмкость должна вмещать больше 6 литров (если ровно 6, то решение можно укоротить на один шаг)
не далее как пару недель назад я пытался написать именно общее (N ведер, X1...XN объемы, вектор начального состояния, вектор целевого состояния) решение задачи с ведрами на Прологе. Не осилил, хотя технически ничего сверхсложного, вроде бы.
А ещё — я не вижу в этой статье вообще ничего содержательного про dot. Только "породил текст прогой на С, скормил его проге на dot, получил SVG". Мало! Как минимум нужно описать, почему вообще dot, а не какая-нибудь утилита для генерации SVG.
dot поразительно похож на популярные языки разметки uml типа Mermaid или PlantUML, никогда не ощущал особых проблем при переходе между ними. Ценность dot разве что в том, что рендеринг графа может быть осуществлен с помощью разных средств визуализации и что сам dot может рендерить громадные графы. Правда, ценность последнего сомнительна.
Взять и налить в 5-литровую емкость 5л. жидкости, а затем из нее наполнить 3-литровую емкость. В первой емкости останется два литра. Выливаете жидкость из обоих емкостей и повторяете процесс. Так мы отмеряли 4 л. В условиях задачи не сказано, что эти литры должны быть в этих емкостях, а не на полу, так что все правильно. Если что, ответить вам скоро не смогу из-за кармы. Нет, доту мы не знаем, мы и так эти задачки щелкаем за минуту.
В крепком орешке именно что сказано - надо было поставить на весы 4кн чтобв отключить бомбу.
Вылить 3л в 5л первый раз, во второй раз в трехлитровой останется 1 литр. Опорожнить пятилитровую. Вылить в нее литр из трешки и налить еще одну трешку.
Налить в пятилитровку. Перелить в трёхлитровку. В пятилитровке останется два, вылить на землю из трёхлитровки, налить из пятилитровки оставшиеся два литра в трёшку и снова наполнить пятилитровку. Отлить из пятилитровки в трёхлитровку литр воды. В пятилитровке останется ровно четыре литра.
Не всякая задача имеет решение.
Можно половину 5 литров слить и половину 3 литров слить. :)
Хорошо тому живётся, кто в уме умеет считать интеграл по объему и у кого глаз-ватерпас ;)
Половину можно вылить, например, из цилиндрической ёмкости, но в условии ни слова о форме..
Кстати, вспомнилась не совсем стандартная задачка на переливания
язык программирования? серьёзно?
Этот пункт я пропущу так как таблица получится циклопических размеров. По правилу умножения 24*5=120 строкТаблица получится ровно на 24 строки. Каждая строка содержит все переходы из одного состояния, а состояний у вас 24.
Я так понимаю для состояния возможны действия: наполнить из источника 5, наполнить изисточника 3, слить 5, слить 3, перелить 5 в 3, перелить 3 в 5. Но для некоторых состояний не всё действия возможны, например, когда сосуд пуст, сливать его бессмысленное, нового состояния не возникнет.
Обозначим состояния через sXY, где X — количество воды в 5-литровой бутыли, Y — количество воды в 3-литровой. Входные символы (действия) обозначим как E5 — опустошить 5-литровую бутыль, E3 — опустошить 3-литровую, F5 — заполнить 5-литровую, F3 — заполнить трёхлитровую, 5T3 — перелить из 5-литровой в 3-литровую, 3T5 — из 5-литровой в 3-литровую бутыль.
Тогда таблица переходов будет выглядеть так:
+-----+-----+-----+-----+-----+-----+-----+
| | E5 | E3 | F5 | F3 | 5T3 | 3T5 |
+-----+-----+-----+-----+-----+-----+-----+
| s00 | s00 | s00 | s50 | s03 | s00 | s00 |
| s01 | s01 | s00 | s51 | s03 | s01 | s10 |
| s02 | s02 | s00 | s52 | s03 | s02 | s20 |
| s03 | s03 | s00 | s53 | s03 | s03 | s30 |
| s10 | s00 | s10 | s50 | s13 | s01 | s10 |
| s11 | s01 | s10 | s51 | s13 | s02 | s20 |
| s12 | s02 | s10 | s52 | s13 | s03 | s30 |
| s13 | s03 | s10 | s53 | s13 | s13 | s40 |
| s20 | s00 | s20 | s50 | s23 | s02 | s20 |
| s21 | s01 | s20 | s51 | s23 | s03 | s30 |
| s22 | s02 | s20 | s52 | s23 | s13 | s40 |
| s23 | s03 | s20 | s53 | s23 | s23 | s50 |
| s30 | s00 | s30 | s50 | s33 | s03 | s30 |
| s31 | s01 | s30 | s51 | s33 | s13 | s40 |
| s32 | s02 | s30 | s52 | s33 | s23 | s50 |
| s33 | s03 | s30 | s53 | s33 | s33 | s51 |
| s40 | s00 | s40 | s50 | s43 | s13 | s40 |
| s41 | s01 | s40 | s51 | s43 | s23 | s50 |
| s42 | s02 | s40 | s52 | s43 | s33 | s51 |
| s43 | s03 | s40 | s53 | s43 | s43 | s52 |
| s50 | s00 | s50 | s50 | s53 | s23 | s50 |
| s51 | s01 | s50 | s51 | s53 | s33 | s51 |
| s52 | s02 | s50 | s52 | s53 | s43 | s52 |
| s53 | s03 | s50 | s53 | s53 | s53 | s53 |
+-----+-----+-----+-----+-----+-----+-----+И откуда тут взять 120 строк?
Ой, я видел шикарное видео на канале mathologer - наглядное решение этой задачи в графичечком виде.
А нет ли у Вас чего-то вроде IAR Visual State(?), чтобы по псевдокоду Dot получить исходник на C? Будет разом и алгоритм и исходник.
Dot хорош что отличная инфраструктура для разработчиков, на любой платформе. Ну и то что ему лет 50 наверное и всё давно отполировано и исправлено.
Из свежего, для рисования диаграмм популярен Mermaid, его можно скажем вставлять в .md файлы на GitHub.
Такого рода задачи легко решаются при помощи теории групп. Мало того, именно при помощи теории групп вы сможете доказать, что задача вообще имеет решение. Числа 5 и 3 взаимно просты, а значит вы легко сможете получить любое значение: 1, 2, 3, 4, 5 литров. А вот для комбинации 6, 3 получить 2 литра уже не получится. Попробуйте доказать это или опровергнуть самостоятельно.
И не нужно строить никаких гигантских таблиц и конечных автоматов. Яркий пример, когда знания математики программистам нужны.
Можно решить через треугольную диаграмму. Сумма высот от любой точки треугольника постоянна, все достижимые переливанием состояния лежат на краю диаграммы. Ну и ограничения по объемам легко добавить, срезав вершину
Мы в университете решали на прологе/хаскелле через поиск (bfs/dfs) в пространстве состояний - примерно как у вас только таблица переходов нигде не хранится, а переходы из одного состояния в другой задаются как раз допустимыми действиями. Там и литры и волки с козлами и капустой и т д - все решается примерно по одинаковой методике и одинаково легко. Жаль с шахматами такое уже не прокатывает.
Задача про две ёмкости для жидкости