Задача про БЕСКОНЕЧНЫЙ поезд | Как найти самое ЭФФЕКТИВНОЕ решение???

Рет қаралды 2,375

Күн бұрын

Пікірлер: 22

@skif1787 4 ай бұрын

выключаем в стартовом вагоне свет и идем в любую сторону на 1 вагон. в этом вагоне включаем свет и возвращаемся в стартовый. Если свет горит значит вагон 1. если нет включаем свет в вагоне и идем в противоположную сторону на 2 вагона (так как мы знаем что в нашем вагоне и вагоне взади свет горит). Дошли выключаем свет и движемся назад по пути выключая свет. Если в стартовом вагоне свет не горит, вагонов 2, если горит, гасим идем дальше. В следующем не горит, вагонов 3, иначе гасим свет и идем дальше на число которое только что прошли в этом направление( в данном случае 4) разворачиваемся и двигаемся включая свет начиная с этого вагона . дальше так же. ( ну и конечно можно засекать паттерны и продлевать движение в каждую сторону, пока не встретиться нужный паттерн). в итоге получаем 1+3+7+15+31+63+127+....+n шагов. выходит максимум меньше 5n, среднее где-то 3.7n, где n- число вагонов

@skif1787 4 ай бұрын

если быть точней получаем разброс от 3n-k до 5n-k-2, где n- число вагонов, а k-число разворотов до нахождения количества вагонов n, причем n больше или равно 2^(k-1) и меньше или равно 2^k-1. наибольший коэффициент получаем когда число вагонов-это степень 2, а наименьший когда число вагонов это предыдущее число перед степенью двойки

@bertyshogan6746 2 ай бұрын

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

@DimaVaulin 4 ай бұрын

Интересная задача, но я почему-то думал, что в конце расскажут оптимальное решение)

@Summerfriendly 4 ай бұрын

Проще всего задачу решить в вероятностях. Если выключить свет в первых K вагонах, то шанс случайного совпадения такого отрезка в поезде (1/2)^K. Остальные включаем, пока не встретим искомую комбинацию. Итого нужно пройти N+K+1 вагон до первого включенного после K+i выключенных (i запас на случайное выпадение нескольких выключенных вагонов подряд перед K специально выключенных). Хотя такое решение работает только при KN нужно минимум N шагов чтобы наткнуться на первый включенный после последовательности выключенных, а дальше верификация результата Z шагов по включенным вагонам с (1/2)^Z заданной вероятностью ошибки. При допущении (1/2)^Z=(1/2)^K, в обобщённом случае можно ограничиться количеством N+K+1 шагов.

@nikmy_ 4 ай бұрын

Можно проверять не то, что вагонов 1, 2, 3 и так далее, а что их 1, 2, 4, ..., 2^k. В этом случае, наткнувшись на вагон Х с выключенным светом прежде, чем вернёмся к начальному вагону, можно сказать, что вагон с номером 2^k - это вагон с номером Х, откуда число вагонов равно (2^k - X). Так как мы двигаемся по степеням двойки, мы не сделаем два круга и вывод верный. Для такого подхода операций не больше 1 + 2 + 2^k +...+ * 2^log2(N+1) = 2^(log2(N + 1) + 1) = 2^(log2(N + 1) + log2(2)) = 2N + 2

@nikmy_ 4 ай бұрын

Если известно, что в поезде не более чем C вагонов со включенным светом, можно найти n за nC шагов. Идём до первого с горящим светом, выключаем его, и возвращаемся к начальному. Мы всегда выключаем свет либо в первом, либо в каком-то новом вагоне с изначально включенным светом, поэтому всё корректно.

@ДаниярКамбетбаев 4 ай бұрын

Забыл посчитать что в этом бинарном поиске нужен путь туда и обратно, для всех степеней двойки кроме последней, где путь может быть короче, но в худшем случае всеравно он обратный. И в расчетах геометрической прогессии ошибка 2^(log2n + 1) +(ошибка, нужен минус) 1 Так что итоговая сложность 4k-2 ПС. со скобками тоже ошибка небольшая log2n + 1 а не log2(n+1).

@ДаниярКамбетбаев 4 ай бұрын

И то это не количество операций а сложность, из за того что мы не учитываем round up, так нужно считать (2^(⌈log2n⌉ + 1) - 1) * 2 - 2^ ⌈log2n⌉ + n, что не получится сократить из за ⌈⌉ , но это даст тебе точный ответ количества шагов для любого n. А вот формула 4k - 2 дает точный ответ только для k = степень двойки, можете сами проверить

@alexz6341 4 ай бұрын

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

@ДмитрийПеревалов-ш9в 4 ай бұрын

Берем две переменные N и K. В стартовом вагоне выключаем свет. Далее просто идем прямо, включаем свет в каждом вагоне и записываем пройденное количество в N. Если наткнулись на вагон с включенным светом, то записываем в K и идем дальше. Если в дальнейшем натыкаемся на вагон без света, прибавляем K в N, включаем свет и т.д. В какой-то момент мы пройдем весь поезд и дальше пойдут вагоны с включенным светом, их мы будем записывать в K, а N уже больше никогда не изменится. Таким образом в N у нас будет количество всех вагонов. Получается решение будет за N шагов, но мы никогда не будем уверены в том, что мы прошли все вагоны. Но если в какой-то момент нас спросят, сколько вагонов, мы просто покажем N.

@sheka7170 4 ай бұрын

В первом вагоне включаем, во втором выключаем. В третьем включаем, в четвертом и пятом выключаем. Получается последовательность чисел от 1 до k в единичной системе счисления, образующая код, начинающийся с включенного старт-бита. Как только мы увидем последовательность всего в один выключенный вагон, мы прошли его насквозь. Тогда можно совершить проверку: пойти в обратном направлении, выключая свет везде, кроме первого вагона. Тогда мы убедимся, что мы прошли его весь, а не встретили уникальную последовательность бит в поезде длиной миллиард вагонов. В итоге пройти понадобится 2(N+2) вагонов.

@skif1787 4 ай бұрын

@@sheka7170 не рабочая схема, ваш созданный паттерн может встретится раньше, чем вы дойдёте до стартового вагона

@ДаниярКамбетбаев 4 ай бұрын

У задачи не может быть решения без возвращения назад (ссылаясь к комментарию про две переменные, мы не сможем убедится что последовательность имеет k вагонов без изменения состояния 1 вагона на промежутке k и прохождения пути назад), но такой метод заставляет нас задуматься о том когда стоит делать проверку предположения о том что вагонов k. Предположим что мы для упрощения обьяснения не выключаем свет а записываем последовательность, например 101 (где 1 - включено а 0 - выключено). Тогда после прохождения последовательности 101101 мы можем сделать предположение что вагона всего 3, изменить последнее число в последовательности (получить 101100) и пройти 3 вагона назад, ожидая 0 в третьем шаге. Однако такая схема имеет плохие контр примеры. При прохождении варианта с вагонами в единственном состоянии (например 6 включенных вагонов - 111111) мы сначала сделаем предположение что их 1, потом 2, 3 и т.д. до 6, получив такое же решение что приводится в видео n(n+1) только еще умноженное на 3. Решением будет простейший бинарный поиск, где сначала мы делаем предположение что вагонов меньше 2, проходя 2 шага в одну сторону, изменяем состояние вагона и ждем этого изменения на обратном пути. Если не видим то следующее предположение что их меньше 4, 8 и т.д. увеличивая интервал на 2. Отмечу что их может быть меньше чем наше предположение (не являться степенью двойки, например 7), тогда мы встретим изменение после предположения о 8 вагонах не на 8-ом обратном шагу а на 7). Таким образом мы получаем кол-во требуемых шагов для n вагонов как: (2^0 + 2^1 + 2^2 . . . + 2^(log2n)) * 2, (на два домножаем потому что путь туда - обратно), что является частным случаем геометрической прогрессии: После сокращения получим (2^(log2k+1)-1) * 2 = (2k - 1) * 2 = 4k - 2

@skif1787 4 ай бұрын

все круто если количество вагонов это степень 2, иначе все не так радужно, например для выяснения что вагонов 129 нам нужно пройти 4*128-2+256+129 и того 897 переходов, что равняется 6,94* на число вагонов ( приблизительно). И чем больше степень, тем больше для следующего от ней вагона коэффициент. в общем случае можно записать так: 3*2^(k-1)+n-2 где n-число вагонов, а k- порядковый номер начала движения из стартового вагона. заменим 2^(k-1) на переменную z тогда получаем 3z+n-2 причем n больше или равно z/2+1(иначе нашли бы на прошлом заходе) и меньше или равно z. считаем крайние значения выражая n через z получаем решение с разбросом от 4n-2 до 7n-8

@ДаниярКамбетбаев 4 ай бұрын

Для тех кто хочет сам порешать и поискать как придти к ответу: ответ из следующего видео 4n - 2

@mathster314 4 ай бұрын

а вот и не угадал)

@SlavaArgentina 3 ай бұрын

Я бы насрал посреди вагона. И шёл бы пока не встречу своё дерьмо. В условиях задачи не сказано, что так нельзя. Да моё решение попахивает. Но зато я считаю вагоны за время N+1.