|
Дан коридор в форме окружности. Через равные промежутки в нем расположены комнаты, в которых можно включать или выключать свет. В начале в некоторых комнатах свет включен, в некоторых нет. Как человеку, находящемуся в коридоре узнать число комнат? задан 30 Сен '12 18:15 
dmg3 |
|
Пронумеруем комнаты по порядку целыми неотрицательными числами. Пусть сначала наш человек находится в нулевой комнате. На $%i$%-м ($%i=1,2,...$%) шаге алгоритма человек двигается в порядке возрастания индексов на $%2^i$% комнат, попутно переключая свет во всех комнатах от $%1$% до $%2^i$% включительно. Затем он делает $%2^i$% шагов обратно (т.е. возвращается в нулевую комнату), ничего не трогая. Если свет в исходной точке не поменялся, значит количество комнат $%n>2^i$%, переходим на следующий шаг. Если же свет в исходной точке поменялся, то $%2^{i-1} < n \leq 2^i$%, и нам остается только выяснить, сколько же их конкретно. отвечен 30 Сен '12 19:20 
chameleon Зачем брать степени двойки? Можно просто на i-ом шаге двигаться до i-ой комнаты. Тогда вторя часть алгоритма не нужна.
(30 Сен '12 19:24)
dmg3
Ваш вариант, безусловно, легче алгоритмически, но Вы сравните, сколько топать бедному человечку! По моему варианту - O(n), по вашему - O(n^2). В общем, я подошел к этой проблеме, как программист, а не как математик =)
(30 Сен '12 19:29)
chameleon
|