Задачки
#1
Опубликовано 14 Январь 2008 - 14:08
<inso> ночь, мост, стоит четыре человека
<inso> им нужно перейти по мосту на другой берег
<inso> за 17 минут
<inso> фонарик один на четверых, без него идти нельзя
<inso> по мосту одновременно может идти не более двух человек в одну сторону
<inso> фонарик перекинуть с одного на другой берег нельзя
<inso> люди идут с разной скоростью. первому надо 1 минуту чтобы перейти, второму - 2, третьему - 5, четвертому - 10
<inso> если по мосту идут два человека, то идут они со скоростью самого медленного
<inso> ну и собственно вопрос, как их всех перевести на другой берег за 17 минут
Тому, кто предложит математическое решение для общего случая - бонусный плюс)
Никаких хистростей вроде убить самого медленного или посадить его на плечи или поставить посередине на мост кого-нибудь не принимаются. Строго по условию решать)
#2
Опубликовано 14 Январь 2008 - 14:27
B - 2
C - 5
D - 10
1) пошли A+B=2 минуты - осталось 15
2) А назад с фонарем - 1 минута - осталось 14
3) пошли C+D=10 минут - осталось 4
4) уже пришедший туда B взял у них фонарь и пошел обратно - 2 минуты - осталось 2
5) пошли А+В=2 минуты - ура!
Люблю математику.
#3
Опубликовано 14 Январь 2008 - 14:45
#4
Опубликовано 14 Январь 2008 - 14:49
а алгоритм такой - определить 2 самых быстрых людей, перевести через мост. из переведенных выбрать самого быстрого и отправить обратно с фонарем. передать фонарь и перевести через мост 2 остальных. затем из переведенных выбрать опять же самого быстрого (в случае из задачи это будет второй человек из первой пары) и отправить обратно. третьим переходом через мост опять перейдет первая (быстрая) пара.
#5
Опубликовано 14 Январь 2008 - 14:58
Есть у меня одна старая задачка. не совсем математическая, но интересная (в свое время поломал голову)).
Боян, конечно, но...
Ну и математические задачки сейчас тоже поищу, помню, в школе училка по математике любила нам их давать...
Изменено: Master Mind, 14 Январь 2008 - 14:58
#6
Опубликовано 14 Январь 2008 - 15:07
составляется таблица: в столбцах дом-напиток-сигареты-домашнее животное, в строчках национальность.
занятно, но просто =)
#7
Опубликовано 14 Январь 2008 - 15:35
Самое трудное в ней - лень излагать весь процесс решения.
Так что только подсказка, если кому надо:
-----------------------------------
Родилась идея текстовой онлайн-игры по СХ с головоломками. Может, такая уже есть?
Изменено: Sherrri, 14 Январь 2008 - 15:41
#8
Опубликовано 14 Январь 2008 - 16:59
#9
Опубликовано 14 Январь 2008 - 17:06
#10
Опубликовано 14 Январь 2008 - 17:14
Развивающая задачка для маленьких Пирамидхэдов: откуда взялся вырезанный квадратик на пирамиде?
Так я у вас спрашиваю
#11
Опубликовано 14 Январь 2008 - 17:26
Говорю же - для маленьких Пирамидхэдиков в детском садике эта задачка.
Изменено: Sherrri, 14 Январь 2008 - 18:35
#12
Опубликовано 14 Январь 2008 - 17:34
За счёт разницы углов у треугольников появляеццо дырко. Они там просто не подобны, насколько я помню :-)
#13
Опубликовано 14 Январь 2008 - 17:57
черт, не успел..
а алгоритм такой - определить 2 самых быстрых людей, перевести через мост. из переведенных выбрать самого быстрого и отправить обратно с фонарем. передать фонарь и перевести через мост 2 остальных. затем из переведенных выбрать опять же самого быстрого (в случае из задачи это будет второй человек из первой пары) и отправить обратно. третьим переходом через мост опять перейдет первая (быстрая) пара.
Для общего случая. Пусть N - кол-во людей. t1, t2,...,tn их скорости. Как составить алгоритм _поиска минимального времени_ решения задачи в таком случае, причем за O(n)?
//----
Задачу про ханойские башни все знают?)
В общем, у нас есть три шпиля. Два пустых, на одном нанизаны N дисков, допустим N = 3. Диски разного диаметра, нанизаны в виде пирамиды, от большего вверх к меньшему. Нужно переложить диски на любой другой шпиль в точно таком же виде. Причем нельзя ни в каком случае ложить больший диск на меньший. За раз только один диск можно перекласть.
Для тех, кто в математику не хочет ударятся - при N = 3 сколько перекладываний минимум нужно сделать?
Для тех, кто хочет, сколько для N дисков вообще.
#14
Опубликовано 14 Январь 2008 - 18:08
#15
Опубликовано 14 Январь 2008 - 18:18
Для тех, кто в математику не хочет ударятся - при N = 3 сколько перекладываний минимум нужно сделать?
7 перекладываний.