БЕСКОНЕЧНЫЙ поезд 2 | САМОЕ эффективное решение? (ну почти)

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

[@1000подписчиковвпаблике]

Дааа ааа Даааавааай Ураааааа

[@skif1787]

Ваша стратегия после каждого второго разворота начиная с 4 не может определить точно значение вагонов в двух случаях, собственно после 4 разворота это 5 и 6 вагонов. Проблема в том что в этих случаях вы понимаете что достигли размера поезда в одном и том же вагоне, в первом с права вагоне от стартового. И вам нужно еще как минимум пройти по кругу чтобы понять, размер поезда. Лечится это легко, Если вы двигаясь в этом направление будете включать свет, то в стартовом выключайте, и на оборот. Таким Вы в случае 5 вагонов узнаете о размере поезда в стартовом вагоне, а в случае 6 в левом от стартового

[@mathster314]

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

[@skif1787]

@@mathster314 давай сначала, после первого разворота мы точно знаем что вагонов больше 1, после второго разворота мы знаем что вагонов больше 2, после третьего что больше 4, т.е информацию о 5 вагонов мы получим только после четвертого разворота. Но из-за того что мы не выключили свет в стартовом вагоне, о том что мы прошли весь поезд мы узнаем только в пройдя после разворота 6 вагонов, но 5 или 6 вагонов нам не понятно. на видео все это видно, и так будет повторятся каждый раз, когда вы будете возвращается со стороны светлых вагонов.

[@mathster314]

​@@skif1787мы когда возвращаемся то считаем вагоны и когда появляется несостыковка, т.е. вместо светлого вагона тёмный, то мы считаем, что прошли длину поезда

[@skif1787]

@@mathster314 все верно, мы ищем не стыковку с нашей схемой. Для удобства 1- свет горит 0- не горит. Давай с начала мы зажгли свет и пошли на право и погасили, получилось 10. Если мы вернёмся и увидим что свет не горит, то вагонов всего 1. Если нет проходим ещё вагон и зажигаем свет, получаем 110. Теперь через два перехода назад мы сможем понять что вагонов 2(больше не можем) не поняли проходим ещё 2 и гасим получаем 11000. Возвращаясь мы сможем понять, что вагонов 3 или 4 соответственно если в третьем вагоне свет не горит и если в третьем горит, а в четвёртом нет. Больше понять нет возможности. Продолжаем движения ещё на 4 вагона и получаем 111111000. И вот тут то и проблема, мы ещё не исключили вариант 5 вагонов, но в нашей схеме и так в 6 вагонах горит свет, т.е. Ни как не понять, что вагонов 5, сделав 5 переходов с крайнего левого, а на шестом переходе мы поймём, что точно прошли весь поезд, но 5 или 6 вагонов не поймем