Дано пять комнат, соединенных дверьми. В двух комнатах 4 двери, в трех — 5. Нужно пройти через все двери по одному разу. Просто пройти через все 16 дверей.
Павлик, если память (ну или переводчики, составители, редакторы советских времен ;))) мне не изменяют - то в классической задаче требования вернуться в исходную точку не было? ;) Там подоплекой была "обзорная экскурсия" - именно "посетить" каждый мост и полюбоваться на его красоты по одному лишь разу. А потом хоть трава не расти. :))) Может надо было приехать на один вокзал, прогуляться и уехать дальше совсем с другого вокзала? ;))) В любом случае, задачка точно Эйлеровская и ноги у всех вопросов обхода графов разной четности по легенде растут именно из нее. Протест отклоняется. ;)
Павлик 2013-03-16 18:45:27 пишет:
Это про Эйлеров цикл, нам можно начать и закончить в разных местах... так что, сорь кокос но ты неправ...
Админ: так какое Ваше решение? :)
Reds 2013-03-12 17:20:25 пишет:
Стоило бы уточнить, откуда начинаем идти, и где должны оказаться в конце. Иначе, стартуя снаружи, вполне себе можно пройти все 16 дверей, оставшись в одной из пяти-дверных комнат.
разве такое возможно? ведь комнат с нечетным количеством дверей 3! ведь если начать снаружи такой комнаты то, независимо от траектории, завершишь внутри... а чтоб выйти надо начинать изнутри - если б было две, тогда можно начать изнутри 1й и завершить внутри 2й...
Админ: :) так и есть
Гость 2013-03-06 18:24:45 пишет:
Дверей по изначальному условию 2*4 и 3*5 в сумме 24. А пройти надо через 16,в этом то и подвох:-)
Админ: А картинка у Вас отоброжается? Посчитайте двери, поймете ситуацию.
:))) На самом деле, комнат-то шесть. Шестая "комната" - то ли двор, то ли балкон, то ли что еще там. И в ней 9 дверей. ;) То бишь, имеем классическую задачу Эйлера о семи мостах: четыре нечетных вершины = такой граф нерешаем. ;)