Задача про бесконечный поезд

Question

Задача про бесконечный поезд

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

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

Как посчитать количество вагонов?

Answer 1

E A Количество меток устанавливается в зависимости от количества вагонов, такие метки можно сделать из 20 вагонов, из 100, хоть до бесконечности увеличивать число вагонов, как только мы попадаем в такую последовательность мы проверяем, является ли она той которую мы создали

Я не говорю, что решение идеальное, оно оптимальное, то есть его реализация быстрее других алгоритмов, и при этом погрешность очень мала(при количестве вагонов больше 100), в случае с меньшим числом вагонов алгоритм Nell 42 действительно подходит больше

Answer 2

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

Answer 3

Окей, тогда можно включить свет следующим образом(1 - в вагоне включен свет, 0 - выключен):

101001000100001000001

Т.е. включать свет через вагон, затем через 2, через 3
И когда мы снова попадём в эту последовательность мы снова получаем ответ в виде количества вагонов + вероятность того что в каком-то участке вагона свет будет включен также крайне мала, для последовательности сверху она не превышает 1 на 4'000'000'000'000 случаев

Answer 4

В таком случае не хватит времени, чтобы обсчитать все вагоны)))

А если серьезно, то такую последовательность можно увеличить до 1'000'000 вагонов, и вероятность появления такой же последовательности будет равно 0(точнее это число стремится к нулю)

Answer 5

E A такой способ является демонстрацией жадного алгоритма, так как мы ищем оптимальное решение, а не идеальное

При моем подходе по поезду достаточно сделать два круга, первый устанавливаем метки, второй проверяем наши эти метки или нет(если нет, то чуть больше двух кругов выходит) и этот алгоритм подходит при большом числе вагонов(если мы подсчитали, что вагонов мало(к примеру меньше 100)), то пользуемся алгоритмом Nell 42

Производительность алгоритма Nell 42 высчитывается немного сложнее, при помощи арифметической прогрессии, в одну сторону мы идём 1, 2, 3, 4 и так до n вагонов, и в обратную сторону в первоначальный вагон, и в другую сторону также(только до вагона n - 1), теперь считаем:
Sn(в одну сторону) = (1 + n) * n
Sn-1(в другую сторону) = n * (n - 1)
В общем:
2n^2

и теперь сравни 2n и 2n^2

Answer 6

Можно в любом вагоне включить свет(но только в одном), и начать отсчёт из этого вагона, как только снова окажемся в вагоне с включенным светом, прекращаем считать, и это будет ответом

Answer 7

А как понять, что это именно тот вагон, в котором включили свет, а не другой с включенным светом ранее?

Answer 8

А если попали в такую же последовательность, но она оказалось не наша? Вероятность крайне мала, но допустима.

Answer 9

Я написал что такая вероятность появления такой же последовательности крайне мала и равна 1 случаю на 4 триллиона

Answer 10

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

Answer 11

Спросить у машиниста

Answer 12

Машинист не знает =)

Answer 13

В общем попробовать так: обозначить стартовый вагон ( наш) допустим включенным светом, и как предлагали выше ходить в одну сторону и постоянно увеличивать количество пройденных вагонов. Ввключая в них свет и считаем. Пример: пошли в одну сторону на 1 вагон, вернулись и пошли в другую сторону на 1 вагон, т.е. от 0 - начального делаем -1.Потом идем на 2/-2, 3/-3 и до того момента, пока не нарушится соотношение n/-n и тогда задача будет решена

Answer 14

Не совсем понятно. Можете чуть подробнее?

Answer 15

Мой способ хоть и имеет погрешность один на 10е1000000(то же что 10 в степени 1000000) случаев(что вообще незначительно), но все же более эффективный, чем алгоритм Nell 42 , что является примером жадного алгоритма

Answer 16

Roma Butaku
ваше решение # 2 кажется достаточно правильным. по сути метка ваша достаточно уникальна, но представьте, вы дошли до конца 101001000100001000001 и тут група из 7 вагонов пошла, ми установили 0000001 и тут реально уже "последний вагон", поскольку далее реально идет снова
101001000100001000001..
Но, по вашому алгоритму ми что должни делать?
Правильно, устанавливать 00000001 и т.д
Информацию (положения виключателя),сделанние шаги, надо еще как-то сохранять и интерпретировать, иначе можем пройти по кругу так и не поняв

Answer 17

Можно, но повторение последовательности не гарантирует того, что такая последовательность единственная. Их может быть 2 и более, например.

Answer 18

Найти один вагон, включить в нем свет и идти до момента, пока не вернёшься в вагон с включенным светом.

Второй вариант: помечать вагон в котором есть свет "1", а без света "0" и записывать себе куда либо результаты, и периодически проверять значения на совпадение.

Answer 19

Есть один вариант.
Можно ходить с блокнотом и не трогать переключатели света.
В блокноте помечать вагоны со включенным светом, как А , с выключенным - В.
Как только последовательность начнёт повторяться - значит нужно закончить.
Посчитать количество букв в изначальный последовательности - это кол-во вагонов.

Answer 20

Kosarevsky Dmitry , если тебе смущает погрешность, то пользуйся алгоритмом Nell 42, он единственный верный алгоритм без погрешности