Дан коридор в форме окружности. Через равные промежутки в нем расположены комнаты, в которых можно включать или выключать свет. В начале в некоторых комнатах свет включен, в некоторых нет. Как человеку, находящемуся в коридоре узнать число комнат?

задан 30 Сен '12 18:15

10|600 символов нужно символов осталось
2

Пронумеруем комнаты по порядку целыми неотрицательными числами. Пусть сначала наш человек находится в нулевой комнате. На $%i$%-м ($%i=1,2,...$%) шаге алгоритма человек двигается в порядке возрастания индексов на $%2^i$% комнат, попутно переключая свет во всех комнатах от $%1$% до $%2^i$% включительно. Затем он делает $%2^i$% шагов обратно (т.е. возвращается в нулевую комнату), ничего не трогая. Если свет в исходной точке не поменялся, значит количество комнат $%n>2^i$%, переходим на следующий шаг. Если же свет в исходной точке поменялся, то $%2^{i-1} < n \leq 2^i$%, и нам остается только выяснить, сколько же их конкретно.
Для этого делаем $%2^i$% шагов в одном направлении, попутно везде выключая свет. Таким образом мы гарантированно выключим свет во всём коридоре. Затем, включаем свет в текущей комнате и идем по коридору, пока заново не наткнемся на комнату с зажженным светом. Сколько сделали шагов - столько и комнат

ссылка

отвечен 30 Сен '12 19:20

Зачем брать степени двойки? Можно просто на i-ом шаге двигаться до i-ой комнаты. Тогда вторя часть алгоритма не нужна.

(30 Сен '12 19:24) dmg3

Ваш вариант, безусловно, легче алгоритмически, но Вы сравните, сколько топать бедному человечку! По моему варианту - O(n), по вашему - O(n^2). В общем, я подошел к этой проблеме, как программист, а не как математик =)

(30 Сен '12 19:29) chameleon
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×835
×76

задан
30 Сен '12 18:15

показан
560 раз

обновлен
30 Сен '12 19:29

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru