theJam.ru

Логические задачиВ тёмном лесу

16 марта 2011 | Добавил: atlakatl

Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
Задача взята с такого же плодово-ягодного, как и наш thejam.ru, сайта.

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
Метки

Комментариев: 27

  1. noxwelle пишет:

    Пройти прямо на 1 км и по кругу?

  2. NLO пишет:

    это самый явный вариант.
    но хотелось бы мне посмотреть на мальчика, который умеет отмерять расстояние, в точности равное 1км, причем ровно по прямой (обычно же люди при хотьбе заворачивают в сторону менее сильной ноги), да ещё и при этом умеет ходить по точной окружности радиуса 1км (!!!), но при этом, вот досада, заблудился в лесу :)))

  3. atlakatl пишет:

    noxwelle, такой вариант работает. Получается длина пути максимум 1 + 2π ~ 7,2831… км. Но есть путь лучше.

    NLO, это же не пособие для туриста, а математика. В задаче мальчик может двигаться хоть по гиперболическому синусу. )

  4. NLO пишет:

    тогда вариант такой:
    сначала идти на север (2)^0.5 (квадратный корень из 2) км,
    на юг ((2)^0.5) - 1 км,

    на юго-запад (2)^0.5 км,
    на запад ((2)^0.5) - 1 км,
    на восток ((2)^0.5) - 1 км,

    на юго-восток (2)^0.5 км,
    на юг ((2)^0.5) - 1 км,
    на север ((2)^0.5) - 1 км,

    на северо-восток (2)^0.5 км,
    на запад ((2)^0.5) - 1 км,

    итого: 8*2^0.5 - 6 ~ 5.31км

  5. atlakatl пишет:

    Не понял Ваши эволюции. Прошли корень(2) на север. Зачем возвращаться по тому же пути на (корень(2)-1), это же не даёт никакой информации? Дальше аналогично.

    Подсчёт расстояния тоже загадка. В маршруте 10 корней из 2, у Вас – 8.

    Уточняю:
    Дорога абсолютно прямая и достаточно длинная.

  6. Iris пишет:

    Существует 4 точки, где пересекаются все дороги - углы квадрата, в который вписан круг километрового радиуса. Если идти сначала в один угол, потом по периметру в остальные, максимальный путь будет таким же как ходьба по кругу, но вероятность быстрее найти дорогу - больше.

  7. Korney G пишет:

    Такой вариантик:
    Мальчик идёт прямо 1 километр. А затем идёт по окружности с центром в точке первоначального пребывания и радиусом 1 километр. Но проходит не полную окружность, а 3/4 оной. Останавливается и идёт в том направлении, куда глаза глядят, то есть по касательной в той точке, в которой остановился. Проходит 1 километр и стопроцентно натыкается на дорогу. В итоге траектория его движения напоминает букву G, а проходит он:
    1) 1 километр до точки на окружности
    2) (3/4)*2*Pi*1 по окружности
    3) 1 километр по касательной.
    Итого: 2+3*Pi/2.
    Это чуть меньше, чем 1+ 2*Pi.
    Это решение я получил, построив описанный квадрат.
    С треугольником решение получается хуже.
    В решении Iris ответ получается тоже чуть хуже - 2^(1/2)+6, но лучше, чем самое первое. А вероятность точно такая же - 100%.

  8. Korney G пишет:

    Ан нет, обманул. 2^(1/2)+6~7,4, так что решенеие хуже первого.

  9. atlakatl пишет:

    Korney G:

    Вариант Iris Вы подсчитали верно, двигаться по 4-й стороне квадрата не надо:

    S = корень(2) + 6 ~ 7,4142…

    Ваш вариант

    S = 2 + п * 3/2 ~ 6,7124…

    верен и пока минимален. Но есть решение лучше!

  10. blez пишет:

    Вписать круг в квадрат. Дойти от центра до угла квадрата ( корень(2) ), далее дойти до точки пересечния с кругом ( 1 ), далее пройти пол окружности ( Пи ) и потом опять от точки касания до вершины (1).

    Итого: корень(2) + 1 + Пи + 1 = 6.555806215962888

    В тёмном-тёмном лесу.... где трепещут осины... пожувать трынь-травы... и кратчайший путь обеспечен.

  11. atlakatl пишет:

    Новый рекорд, автор Ogra! S = корень(2) + 1 + п + 1 ~ 6,5558…

    Обратите внимание, Ogra сразу выходит за пределы окружности. В этом направлении ещё стоит поюзать.

  12. Korney G пишет:

    Даже не знаю, как объяснить.....
    Описываем квадрат и правильный треугольник. Нижняя сторона квадрата лежит на нижней стороне треугольника. Идём из центра в точку пересечения левой стороны треугольника и верхней стороны квадрата. Этот путь равет (2*3^(1/2))/3. Затем по касательной (т.е. по верхней стороне квадрата) до круга. Это - (3^(1/2))/3. Теперь до пересечения окружности с биссектрисой (медианой, высотой) треугольника, проведенной из левого угла. Тут получается 4*Pi/3. А теперь - по касательной в этой точке до пересечения с левой стороной треугольника. Этот отрезок тоже равен (3^(1/2))/3. Итого, путём нехитрых преобразований, получаем в точности: 4/3*(Pi+3^(1/2))~6,4981.
    Фух.....

  13. Korney G пишет:

    А если идти сначала также, но по окружности не до точки пересечения с медианой, а до касания с перпендикуляром к левой стороне, то получится 1+3^(1/2)+7*Pi/6 ~ 6,39724. Так-то лучше.

  14. Korney G пишет:

    Автор! Эй! Ну что там?

  15. atlakatl пишет:

    Извиняюсь, закрутился.

    Итак, выходим из центра на 2*3^(1/2)/3, затем по касательной до пересечения с окружностью 3^(1/2)/3, затем по окружности 7/6*п, затем по касательной 1.
    Итого
    S = 2*3^(1/2)/3 + 3^(1/2)/3 + 7/6*п + 1 ~ 6,3972…

    Новый рекорд, автор Korney G!

    Рекорд, похоже, окончательный. Не совсем понятно, как он получился. Почему первый отрезок именно такой длины? Все остальные построения после его получения вроде бы понятны.

  16. Ogra пишет:

    Дайте чертеж, нихрена не понял ;)

  17. Владислав пишет:

    А не легче ли...
    1км на запад, 2км на восток, 1км на север, 2км на юг. итого 6км и мы пересекаем все 4 стороны описанного вокруг окружности квадрата, то есть дорога в любом случае найдена.

  18. atlakatl пишет:

    Владислав:
    Если дорога будет с западной стороны окружности и не строго вертикальна, то мальчик её не найдёт.

  19. ojoko пишет:

    идем 1км в любом направлении. поворачиваем под 135 градусов (т.е. под 45 гр. к уже пройденному пути), идем 1.41км. поворачиваем на 90гр. в сторону отправной точки, идем 1.41км. снова тоже самое, еще 1.41км. Итого: 1+3*1.41=5.23 Не ходите по лесу кругами.

  20. ojoko пишет:

    Если не понятно, то, ориентируясь по сторонам света, ответ будет такой.
    1. Нужно пройти 1км, например, на северо-восток.
    2. Затем развернуться на юг и пройти 1,41км.
    3. Развернуться на запад и пройти 1,41км.
    4.Развернуться на север и пройти 1,41км.
    Максимальный путь 5,23км.

  21. atlakatl пишет:

    Ojoko, нарисуйте окружность. Нарисуйте штук 10 касательных к ней. Это возможные дороги. Теперь смотрим на ваш маршрут. Все 4 отрезка находятся внутри круга, касаясь окружности только в 4 –х точках. Найти дорогу так можно только при большой удаче.

  22. Федор пишет:

    Пришел к тому же ответу что и Корней. Зато могу пояснить откуда я его взял)))
    За основу был взят вариант в котором (в декартовой системе координат с центром в начальном положении мальчика) идем в точку (-1;-1) потом по касательной вверх, потом огибаем полуокружность по часовой стрелке и вниз до точки (1;-1).

    Я рассмотрел что будет если изначально идти не в точку (-1;-1) а в точку (х;-1) при условии х принадлежит [-1,0] и нашел минимум по х. он достигается при x=-(1/3)^0.5. Т.е. путь будет
    (0;0)---по прямой--->(-(1/3)^0.5; -1)---по прямой--->(-(3^0.5)/2; -1/2)---по окр-ти по часовой стрелке--->(1; 0)---по прямой--->(1;-1)

  23. Buh пишет:

    Идем по прямой 1.4142... км.
    Если нет дороги, возвращаемся по этой же тропинке через точку выхода по прямой на 2 * 1.41 км.
    Т.е. идем в один угол квадрата и потом в противоположный.
    Максимум 4.24 км

  24. Buh пишет:

    Сорри. Отправил не дочитав условия

  25. Алексей пишет:

    А Владислав прав...

    "Владислав пишет:
    6 апреля 2011 в 13:02
    А не легче ли...
    1км на запад, 2км на восток, 1км на север, 2км на юг. итого 6км и мы пересекаем все 4 стороны описанного вокруг окружности квадрата, то есть дорога в любом случае найдена."

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать