Архив форумов ЦИТФорума

[Мираж]

Ребята, помогите!!!
Есть задачка тут, помогите решить, плиз..
В общем, профессор стоит в темноте у бесконечной стенки, имея в руках хиленький фонарик и зная, что где-то в этой стенке имеется дверь, которую ему необходимо найти. С какой от него стороны находится дверь - неизвестно
Допустим, n- число шагов, которое необходимо чтобы дойти до двери.
Мне надо придумать алгоритм, который находит дверь за время тета(n)

Был тут алгоритм -
- пойти i шагов вправо и вернуться
- пойти i шагов влево и вернуться
- увеличить i
... пока не найдешь дверь. (Стартуем при ай=1, ессесно)
Но этот алгоритм бежит за тета-н-в-квадрате.

Помогите!!!!
Заранее благодарствую!

[Гость]

Что мешает n раз по 1 шагу вправо потом вернутся и так же влево?

[GREA]

2>
<4
8>
<16
32>
....
Может получится.
Я не проверял, но это довольно стандартный прием для подобного рода задач. В любом случае напиши сюда о результатах.

[grayrat]

что-то мне подсказывает что нужно не по степеням двойки а по ряду Фибоначчи, т.е.
>1
<2
>3
<5
>8
и.т.д.
Во всяком случае метод золотого сечения эффективней метода половинного деления.


А как бы ты сам действовал на месте проффессора представь...

[GREA]