Задачка про муравья

← →
КаПиБаРа © (2005-09-09 09:35) [0]

Слепой муравей очутился посередине прямолинейной трассы шириной L. Как ему следует двигаться, чтобы гарантированно (и как можно скорее) достигнуть одной из обочин?

← →
MBo © (2005-09-09 09:42) [1]

муравью известна ширина дороги?

← →
КаПиБаРа © (2005-09-09 09:46) [2]

MBo © (09.09.05 9:42) [1]
Вы должны ему путь проложить.

← →
boalse © (2005-09-09 09:47) [3]

Ну дык... прямо к обочине???? В чём подвох???

← →
Macrodens © (2005-09-09 09:48) [4]

Прислушаться к шуму проезжающих машин и потом идти перпендикулярно проходящему звуку.

← →
Sergey13 © (2005-09-09 09:49) [5]

Строго от разделительной полосы короткими перебежками. 8-)

← →
linesoft © (2005-09-09 09:50) [6]

Судя по всему, неизвестна.
Алгоритм от этого будет зависеть

← →
КаПиБаРа © (2005-09-09 09:51) [7]

boalse © (09.09.05 9:47) [3]
Он не знает где обочина

Macrodens © (09.09.05 9:48) [4]
Машин как назло нет

Sergey13 © (09.09.05 9:49) [5]
Строго от разделительной полосы короткими перебежками
Он слепой.

← →
linesoft © (2005-09-09 09:51) [8]

>Ну дык... прямо к обочине???? В чём подвох???
Он слепой, наверно

← →
MBo © (2005-09-09 09:53) [9]

>КаПиБаРа © (09.09.05 09:46) [2]
>MBo © (09.09.05 9:42) [1]
>Вы должны ему путь проложить.
Это я понимаю, но существенно разные задачи -
1) муравей знает, что до обочины L/2
2) не знает

← →
КаПиБаРа © (2005-09-09 09:54) [10]

linesoft © (09.09.05 9:50) [6]
Ширина трассы L дана, что бы определить максимально длинный путь по предложенному вами алгоритму. Оценивается именно максимально длинный путь.

← →
КаПиБаРа © (2005-09-09 09:54) [11]

MBo © (09.09.05 9:53) [9]
Знает.

← →
Lexer © (2005-09-09 09:56) [12]

Если муравей заранее измерил дорогу и знает её ширину (w), то он пойдет прямо в любом направлении на расстояние 0,5^0,5 * W , если не дойдет, то повернет на 90 градусов и максимум пройдет 2^0,5 * W.

Тока это если муравей шибко умный. :)

← →
Lexer © (2005-09-09 09:59) [13]

Ответ: максимум 0,5^0,5 * W + 2^0,5 * W

← →
MBo © (2005-09-09 09:59) [14]

У меня пока ~2.07 L получается

← →
Котик Бегемотик (2005-09-09 10:00) [15]

Вероятно муравью при его размерах совсем необязательно быть слепым :)

Ему нужно двигаться в любом направлении на расстояние L/2 и если не достиг еще обочины то повернуть на 90 градусов и двигаться пока не встретит обочину.

← →
Котик Бегемотик (2005-09-09 10:03) [16]

Во блиннн... пока писал сколько ответов появилось :)
Хотя первое что пришло в голову - это спросить другого муравья :) он то слепой но не глухой же :)))

← →
Думкин © (2005-09-09 10:03) [17]

> MBo © (09.09.05 09:59) [14]

Ну да. (1+Пи)/2.
Может и короче есть?

← →
Lexer © (2005-09-09 10:03) [18]

[15] Котик Бегемотик (09.09.05 10:00)

При таком варианте и при очень неудачных обстоятельствах он не дойдет до обочины за всю свою жизнь,
машины в счет не беру =)

← →
КаПиБаРа © (2005-09-09 10:04) [19]

MBo © (09.09.05 9:59) [14]
Много

← →
КаПиБаРа © (2005-09-09 10:05) [20]

Lexer © (09.09.05 9:59) [13]
Меньше

← →
Котик Бегемотик (2005-09-09 10:06) [21]

Уточненная версия :)
Нужно двигаться в любом направлении на расстояние Sqrt(2)*(L/2) и далее по сценарию...

← →
MBo © (2005-09-09 10:06) [22]

Похоже, 1.78L (1+Pi/4)

← →
КаПиБаРа © (2005-09-09 10:09) [23]

MBo © (09.09.05 10:06) [22]
много

← →
Владислав © (2005-09-09 10:09) [24]

А он по окружности может двигаться? :)
Пи * L / 2

← →
КаПиБаРа © (2005-09-09 10:10) [25]

Владислав © (09.09.05 10:09) [24]
Может, но это длинный путь

← →
Труп Васи Доброго © (2005-09-09 10:13) [26]

Ну до одной из обочин он дойдёт гарантированно и по прямой. Вероятность того что он пойдёт параллельно дороге равна 0. А вот как быстрее? Ну скорее всего по окружности радиуса L/2.

← →
Думкин © (2005-09-09 10:14) [27]

> Владислав © (09.09.05 10:09) [24]

похоже, так.

← →
Труп Васи Доброго © (2005-09-09 10:18) [28]

Только как вот СЛЕПОЙ может идти по окружности?!?!? Откуда он вообще знает что такое окружность и как она выглядит?

← →
Котик Бегемотик (2005-09-09 10:19) [29]

Это же муравей а не циркуль ...
Представьте - КАК муравью размером 3 мм описать ПРАВИЛЬНУЮ окружность радиусом примером 3 метра ?
Хотя как ему ТОЧНО отмерить расстояние L/2 я тоже не представляю...

Пройти минимум на расстояние L/2 в любую сторону, потом по окружности центр у которой в начальной точке движения.

> Это же муравей а не циркуль ...

Сказано же:

> Вы должны ему путь проложить.

2 * L / cos(45 градусов)
:)

> Есть более короткий путь.
Имеется в виду более короткий путь в самом худшем случае?

ну по спирали, допустим все время уходя влево. Формулу забыл лет 15 назад

> ну по спирали, допустим

Путь ещё длиннее чем у меня получится :))

> ну по спирали, допустим

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

конечно, спирали бывают разные. мне помнится только слово эпициклоида. радиус у спирали разве есть? Ну, допустим, 2 шага вперед, один влево

Задачка про муравья Найти похожие ветки