Что-то как-то подозрительно, что никто не решил.
выключаем свет в нулевом вагоне n = 0; while (true) n++ идём влево на n если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов return n+1 вагон -n - выключаем свет возвращаемся в начальную точку на +n вагонов, в нулевой вагон идём вправо на n вагонов влючаем свет возвращаемся в исходную точку на -n вагонов. Отдельно обработать случай для 1 и двух вагонов. |
вот только для составления ряда надо знать сколько в нем членов :)
Добавлено через 1 минуту miramax,верно загуглил?) |
Какого ряда ?
В моём псевдокоде есть только одна переменная - n |
это сложность порядка O(N^2) получается.Интересно есть ли более оптимальные решения?
Добавлено через 31 секунду Цитата:
|
Цитата:
Можем хранить ссылку на последний левый и правый вагоны после каждого прохода. |
ну да, тут можно оптимизировать с т.з. языка.Но для реального человека, перед которым стоит задача сложность нахождения ответа будет побольше т.к. придется таки честно все отбегать(считаем проход вагона+переключение лампочки за элементарную операцию).Насчет N^2 я не уверен.
|
Ок. Соль в том , что то что мы точно включали и выключали должны пересечься в какой-то точке.
посылаем двух человек влево. Один за ход включает два вагона и двигается дальше, второй ВЫключает по одному и двигает дальше. первый проверяет предыдущий вагон. Если предыдущий вагон - включен - значит они встретились. |
Нда. А теперь алгоритмически опредлим - жив ли кот в ящике Шредингера.
Когда правильный ответ будет опубликован - черкните плиз в личку кто-нть. Следить за темой стало скучно. |
вообщем упрощено так:
Последовательно проверяем гипотезы что в составе N вагонов: проверка гипотезы что в составе n вагонов: идем в одну сторону n вагонов и всюду выключаем свет.В n+1-ом -включаем.Возвращаемся назад на n+1 вагонов.Если в первом свет включен - значит в составе и было n - вагонов.Если нет - повторяем проверку для n+1 и т.д. до победного конца. |
Цитата:
Цитата:
|
Часовой пояс GMT +4, время: 15:38. |
Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.