Загадка про поезд

[undefined]

Имеется кольцевой участок железной дороги.На нем стоит состав вагонов, тоже замкнутый в кольцо.В каждом вагоне есть лампочка и переключатель, который её включает/выключает.Вы появляетесь в рандомном вагоне. Лампочки тоже включены рандомно.По составу можно свободно перемещаться и переключать переключатели.Требуется придумать алгоритм действий для определения числа вагонов.Решение не единственно.Предлагайте варианты.

Добавлено через 1 минуту
да, забыл - окна в вагонах тонированы под ноль т.е. что снаружи - не видно

[zCHESNOKz]

не знаю как алгоритм, но узнать количество вагонов думаю это просто.
1. выключаем все лампочки;
2. включаем одну;
3. начинаем счет, и идем по поезду
4. профит!

или

3. начинаем счет, и идем по поезду, включая каждую

[dark256]

Мне это напоминает задачу определения высоты башни с помощью барометра :)

Идем по вагонам, выкручивая все лампочки подряд. Пока не кончатся. Число вагонов == числу лампочек.

[undefined]

не знаю как алгоритм, но узнать количество вагонов думаю это просто.
1. выключаем все лампочки;
Для этого надо знать что ты круг уже один прошел.Вагонов может быть сколь угодно много

Добавлено через 6 минут
Мне это напоминает задачу определения высоты башни с помощью барометра
Да еще одно условие: никаких пометок в вагонах делать нельзя максимум можно помечать стейтом лампочки.

[GBee]

включить везде, потом везде выключить.

[undefined]

так в том то и проблема чтоб определить когда все включены/выключены.Поезд то кольцевой :)

[illuzor]

1) Отключить первую попавшуюся включённую.
2) Идти вперёд и считать вагоны.
3) Проходя по по вагонам трогать все попадающиеся выключенные. Если одна из выключенных будет тёплой, значит это и есть точка отсчёта. Количество вагонов будем тем, какое насчитал

[undefined]

не катит
Вагонов может быть сколь угодно много

Добавлено через 4 минуты
вроде пограммерский форум,но никто не хочет думать алгоритмически.Повторюсь решение - это алгоритм!

[dark256]

Задача сводится к определению захода на второй круг.
Так?
Соотв. решением мне видится :
1. Сводим все к общему состоянию - все выкл.
2. Убеждаемся, что такое состояние ДОСТИГНУТО.
3. Включаем одну лампочку и делаем круг, пока не наткнемся на неё же.

Но если вагонов миллиард, и ты все выключаешь, и натыкаешься на последовательность из 100 подряд выключенных лампочек - п.2. даст ошибочное срабатывание... Хотя все равно мы идем и считаем далее...

Не, я не умею алгоритмически думать.

[undefined]

2. Убеждаемся, что такое состояние ДОСТИГНУТО.
Как этого достигнуть, если в процессе обхода может встретиться сколь угодно большая последовательность выключенных лампочек?

Добавлено через 4 минуты
Хотя все равно мы идем и считаем далее...
и? когда остановиться то?

[MikroAcse]

Выкручиваем лампочку и начинаем отсчет ;)

[undefined]

Да еще одно условие: никаких пометок в вагонах делать нельзя максимум можно помечать стейтом лампочки.
А еще можно навалить кучу в вагоне :)

[MikroAcse]

Тогда, на самом деле, задача является немного глуповатой.
Ведь, получается, даже лампочки трогать нельзя (теплые или нет).

[undefined]

Ведь, получается, даже лампочки трогать нельзя
Именно.
Повторяю задача на алгоритмическое мышление.

[GBee]

Нам нужен маркер первого вагона.
то есть для начала нужно сходить назад - выключить вагонов 10. Потом вернутся вперед и маркировать вагоны светом. 1 включаем, два выключаем, 3 вагона включаем, 4 выключаем, а потом все отключаем до упора, пока не наткнемся на 10 выключенных, потом 1+2-3+.
То есть строим уникальную последовательность. Правда на миллиарде при изначальном разбросе может получится похожая, но я что-то сомневаюсь.

[undefined]

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

[dark256]

Как этого достигнуть, если в процессе обхода может встретиться сколь угодно большая последовательность выключенных лампочек?

Добавлено через 4 минуты

и? когда остановиться то?

Так вот это я и не вижу как придумать.
Разве что выстраивать некую сигнатуру-последовательность, наткнувшись на которую мы сможем однозначно распознать её как маркер. Но на достаточно большой выборке даже сгенерировання последовательность случайно может возникнуть - известная байка о миллиарде обезъян с печатными машинками.

Соотв.: решения нет. Угадал?

[MikroAcse]

Учитывая абсолютную случайность, это всё же плохой вариант.

Повторяю задача на алгоритмическое мышление.
По-моему алгоритма тут нет и быть не может. Любая последовательность может быть сгенерирована случайно. А без маркеров тут не справиться.

[undefined]

Решение не должно быть привязано к каким-то числам.Иначе оно не универсально.

Добавлено через 1 минуту
По-моему алгоритма тут нет и быть не может.
Это не верное утверждение.

Добавлено через 2 минуты
Соотв.: решения нет. Угадал?
не угадал

[dark256]

Жесть. Ну, тогда переться по вагонам и на основе какого-нть ряда фурье методом аппроксимации выстраивать формулу зависиомсти наличия света от номера вагона. Как только вся зависимость в формуле будет представлена, формула начнет двать точный результат, что и будет считаться завершением круга.
Далее число членов ряда == числу вагонов.

[miramax]

Что-то как-то подозрительно, что никто не решил.
выключаем свет в нулевом вагоне

n = 0;
while (true)
n++
идём влево на n
если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов return n+1
вагон -n - выключаем свет

возвращаемся в начальную точку на +n вагонов, в нулевой вагон
идём вправо на n вагонов
влючаем свет

возвращаемся в исходную точку на -n вагонов.


Отдельно обработать случай для 1 и двух вагонов.

[undefined]

вот только для составления ряда надо знать сколько в нем членов :)

Добавлено через 1 минуту
miramax,верно загуглил?)

[miramax]

Какого ряда ?
В моём псевдокоде есть только одна переменная - n

[undefined]

это сложность порядка O(N^2) получается.Интересно есть ли более оптимальные решения?

Добавлено через 31 секунду
Какого ряда ?
это я дарку отвечал

[miramax]

это сложность порядка O(N^2) получается.Интересно есть ли более оптимальные решения?

Почему же ? мы линейно ходим по массиву влево и вправо по вектору, выключая и включая свет по одному разу за проход. сложность - n*2
Можем хранить ссылку на последний левый и правый вагоны после каждого прохода.

[undefined]

ну да, тут можно оптимизировать с т.з. языка.Но для реального человека, перед которым стоит задача сложность нахождения ответа будет побольше т.к. придется таки честно все отбегать(считаем проход вагона+переключение лампочки за элементарную операцию).Насчет N^2 я не уверен.

[miramax]

Ок. Соль в том , что то что мы точно включали и выключали должны пересечься в какой-то точке.
посылаем двух человек влево.
Один за ход включает два вагона и двигается дальше, второй ВЫключает по одному и двигает дальше.
первый проверяет предыдущий вагон. Если предыдущий вагон - включен - значит они встретились.

[dark256]

Нда. А теперь алгоритмически опредлим - жив ли кот в ящике Шредингера.
Когда правильный ответ будет опубликован - черкните плиз в личку кто-нть.
Следить за темой стало скучно.

[undefined]

вообщем упрощено так:
Последовательно проверяем гипотезы что в составе N вагонов:
проверка гипотезы что в составе n вагонов:
идем в одну сторону n вагонов и всюду выключаем свет.В n+1-ом -включаем.Возвращаемся назад на n+1 вагонов.Если в первом свет включен - значит в составе и было n - вагонов.Если нет - повторяем проверку для n+1 и т.д. до победного конца.

[miramax]

вообщем упрощено так:
Последовательно проверяем гипотезы что в составе N вагонов:
проверка гипотезы что в составе n вагонов:
идем в одну сторону n вагонов и всюду выключаем свет.В n+1 -включаем.Возвращаемся назад на n+1 вагонов.Если в первом свет включен - значит в составе и было n - вагонов.Если нет - повторяем проверку для n+1 и т.д. до победного конца.

Чем это отличается от псевдокода ? Я забыл умножить n на два, перед return ) Т.к. проходов "гипотез" будет в два раза меньше
n = 0;
while (true)
n++
идём влево на n
если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов return n+1
вагон -n - выключаем свет

возвращаемся в начальную точку на +n вагонов, в нулевой вагон
идём вправо на n вагонов
влючаем свет

возвращаемся в исходную точку на -n вагонов.
Задачка пустяк ) давай ещё =)

[undefined]

где границы цикла?Я вот до сих пор не могу вникнуть как он работает

[miramax]

Сообщение от miramax
n = 0;
while (true)
{
n++
идём влево на n
если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов
return n*2+1
вагон -n - выключаем свет

возвращаемся в начальную точку на +n вагонов, в нулевой вагон
идём вправо на n вагонов
влючаем свет

возвращаемся в исходную точку на -n вагонов.
}

Согласен - вариант, с проверкой нулевого вагона - понятнее

[Korchy]

Я наверное совсем тупой не умею мыслить алгоритмически, но совершенно не понимаю, чем решение с псевдокодом в принципе отличается от вариантов предложенных ранее.

[undefined]

а какие раньше варианты были? Потрогать лампочку?Решения нет?

Добавлено через 10 минут
Сообщение от miramax
n = 0;
while (true)
{
n++
идём влево на n
если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов
return n*2+1
вагон -n - выключаем свет

возвращаемся в начальную точку на +n вагонов, в нулевой вагон
идём вправо на n вагонов
влючаем свет

возвращаемся в исходную точку на -n вагонов.
}

Согласен - вариант, с проверкой нулевого вагона - понятнее

И все же сложность тут квадратичная т.к. имеется вложенный цикл(идём влево на n).

[alatar]

Вот самый вменяемый алгоритм (http://dxdy.ru/post724580.html#p724580).

[Psycho Tiger]

Мне понравилось решение @miramax. Кратко и понятно. Оптимизировать – смысла нет, в реальной жизни можно в вагоне, например, блевануть, в программировании – поставить другие метки.

[undefined]

тем не менее у него квадратичная сложность

[Psycho Tiger]

Неуверен насчет квадратичной, возможно больше.
Но кого это волнует? :D Включай по 10 лампочек за раз и наворачивай круги, раз ты оказался в таком поезде.

Если мы говорим о программировании, то, формализовано, у нас двусвязный список и чтобы посчитать вагоны – достаточно сравнивать ссылки/указатели вагонов с линейной сложностью. Нет указателей? Иметь указатель на "текущий" вагон и на "первый" и с линейной сложностью "телепортироваться" из вагона в вагон.