Вы находитесь в пустом поезде. Это даже не поезд, а просто вагоны, они сцеплены друг с другом. Все вагоны внутри одинаковы, двери на выход из вагона закрыты, через окна ничего не видно. Вы можете включать и выключать свет в вагоне в котором находитесь, можете сходить в соседний вагон, там тоже можно включать или выключать свет. Вам известно, что вагоны стоят на кольце и сами сцеплены в кольцо, первый вагон сцеплен с последним, ходить по кругу можно сколько угодно. В момент начала решения задачи в каких-то вагонах свет уже горит, в каких-то — не горит.
Лампочки трогать нельзя, они находятся за стеклом, и потому по теплоте лампочек определить включали мы их или нет нельзя.
В вагонах ничего отставлять нельзя.. не знаю почему. просто нельзя)
Ваша задача при помощи управления светом в вагонах и перемещения по ним узнать сколько в этом кольце вагонов.
глупая задачка. нужно сначала сделать круг и добиться чтобы свет был включен через вагон. потом сделать второй круг и выключать(или включать) за собой свет. так и посчитаешь.
необходимо еще одно условие - границы количества вагонов (от 20 до 30 например), ибо если вагонов сильно много или мало, то не получится обеспечить базу для решения задачи (включение/выключение света в определенной последовательности.)
> необходимо еще одно условие - границы количества вагонов (от 20 до 30 например), ибо если вагонов сильно много или мало, то не получится базу для решения задачи (включение/выключение света в определенной последовательности.)
Включаем одну.
Идем вперед, считая вагоны, пока не встретим включенную (в N-ном вагоне).
Выключаем ее и возвращаемся назад в первый вагон.
Если в первом вагоне лампочка не горит - значит, длина состава N-1. Если все равно горит - снова идем вперед, считая вагоны.
> Включаем одну.
> Идем вперед, считая вагоны, пока не встретим включенную (в N-ном вагоне).
> Выключаем ее и возвращаемся назад в первый вагон.
> Если в первом вагоне лампочка не горит - значит, длина состава N-1. Если все равно горит - снова идем вперед, считая вагоны.
даже если количество вагонов довольно большое, нас не ограничивают во времени. соответственно, идя по вагонам бесконечное количество времени - мы включим свет во всех вагонах.
Включаем свет в вагоне, где находимся и идем в заранее выбранном направлении, запоминая пройденное количество вагонов, когда встречаем вагон с включенным светом, выключаем там свет, возвращаемся на пройденное количество вагонов (в изначальный вагон) и смотрим, горит ли там свет, если горит, значит идем еще раз, на этот раз дальше, если погас, значит то кол-во вагонов, которое мы прошли обратно (или туда) и будет искомым.
Сигналом того, что мы сделали полный круг будет изменение положения выключателя в начальном вагоне, когда мы туда вернемся, идя назад.
Идти по вагонам, включая и выключая свет, создавая из лампочек некую конкретную сигнатуру. Когда она полностью повторится - кольцо пройдено. Как-то так.
> Идти по вагонам, включая и выключая свет, создавая из лампочек некую конкретную сигнатуру. Когда она полностью повторится - кольцо пройдено. Как-то так.
Случайно выбранная сигнатура уже может присутствовать на момент начала задания и даже может повторятся энное число раз.
1) Идем по вагонам, записывая ситуацию (0 - темно, 1 - светло) до тех пор, пока не получим первый цикл (2к вагонов, первый отрезок длины к совпадает во вторым).
2) Возвращаемся в первый вагон и выключаем свет в первых к вагонах.
3) Идем дальше и если оказывается, что первый светлый вагон во втором отрезке погашен, значит вагонов всего к.
4) Если оказывается, что во втором отрезке вагоны освещены также, как и до выключения первого отрезка, возвращаемся в первый вагон и переходим к п 1).
Включаем в соседнем вагоне в направлении А свет. Бежим в направлении Б до вагона со светом, считая количество вагонов. Выключаем. Бежим в направлении А и проверяем не выключен ли свет. Если выключен, дано кол-во вагонов. Если нет бежим в направлении Б выключаем первый попавшийся, и считаем до следующего включенного. Цикл повторяется.
А как по-другому, если число вагонов не ограниченно сверху? Если внутри цепи вложенных циклов нет, сразу выйдем на ответ.
И зацикливание невозможно, если число вагонов конечно.
> идём по вагонам и оставляем включеный свет через 1, 2...n вагонов пока не начнут попадаться вагоны с включеным светом через 1,2..n вагонов.
Так могло быть изначально. То есть Вы не зациклились, как Вам кажется, а просто попали н такой участок. И заранее предсказать, какие могут быть участки, невозможно.
> Так могло быть изначально. То есть Вы не зациклились, как Вам кажется, а просто попали н такой участок. И заранее предсказать, какие могут быть участки, невозможно.
Белый Клык предложил единственный способ который на 100% позволяет узнать включал ты свет или нет. В условии количество вагонов любое, т.е. стремящееся к бесконечности, а следовательно может встретиться любая комбинация включено\выключено которую пассажир попытается оставить в кач-ве "метки".
> Это понятно. Но все равно не верится, что невозможен алгоритм эффективней предложенного "пуш-пульного" тык-мыканья.
У него 100% гарантия результата. При этом используется всего один счетчик, значение которого в конце будет являться ответом на заданную задачу. Другие предложенные тут варианты не дают стопроцентной гарантии и предполагают наличие массивов с мусорными данными, которые в результате будут выброшены. Размеры массивов при этом не определены и могут бесконтрольно увеличиваться в размерах - это зло в чистом виде, пусть лучше процессор маслает проходы туда-сюда, он кремниевый, че ему будет.
Есть вопрос по поводу того, как будет эффективнее, ходить все время в одну сторону или при встрече вагона с включенным светом возвращаться и от нулевого идти в противоположную сторону. Вообще эффективность этих двух алгоритмов можно сравнить умными математическими методами и уйдет на это примерно один-два тетрадных листа, но я уже забыл как это делать.
У сортировки пузырьком тоже 100% гарантия результата, что не мешает ей быть самым дерьмовым способом сортировки.
>Другие предложенные варианты тут не дают стопроцентной гарантии
Это очевидно. Но ключевые слова "предложенные тут". Отсюда никак не следует, что более эффективных вариантов не существует в природе.
> > У него 100% гарантия результата.
>
> У сортировки пузырьком тоже 100% гарантия результата, что не мешает ей быть самым дерьмовым вариантом сортировки.
Так точно. Помню была даже у нас специальная лекция, где мы рассчитывали затраты времени на тот или иной алгоритм сортировки. Хотя не, вру, уже не помню :)
> >Другие предложенные варианты тут не дают стопроцентной гарантии
>
> Это очевидно. Но ключевые слова "предложенные тут". Отсюда никак не следует, что более эффективных вариантов не существует в природе.
Ну головастые люди постоянно что-то придумывают для оптимизации различных алгоритмов. А говнокодеры потом все равно используют пузырьковые алгоритмы сортировки!!! Думать лень, от этого голова болит, а процессор кремниевый, пусть маслает, че ему будет!!!!
удостоверяемся что в текущем -1 вагоне свет выключен, и идем в сторону + включая свет и считая вагоны, каждый раз
при включении света добавляем к счетчику число пройденных вагонов после последнего включения.
По кругу конечно можно ходить бесконечно но вагоны будут посчитаны.
> >Другие предложенные варианты тут не дают стопроцентной гарантии
>
> Это очевидно. Но ключевые слова "предложенные тут". Отсюда никак не следует, что более эффективных вариантов не существует в природе.
Простите, возможно я что-то упустиk, если общество так легко согласилось с тем, что "другие предложенные тут варианты не дают стопроцентной гарантии".
Был бs весьма признателен товарищам за описание ситуации, в которой не работает метод, предложенный в посте #25/
> Простите, возможно я что-то упустиk, если общество так легко согласилось с тем, что "другие предложенные тут варианты не дают стопроцентной гарантии".
> Был бs весьма признателен товарищам за описание ситуации, в которой не работает метод, предложенный в посте #25/
Он работает, но предполагает хранение массива данных неизвестного размера, который будет бесконтрольно увеличиваться. Если бы в условиях задачи стояло требование после подсчета вагонов вернуть взад состояние всех лампочек, он был бы бесспорно рабочим. А так он экономит процессорное время и жрет память. Как бы не праздный вопрос что нам нужнее процессорное время или память.
И что?
Если Вагонов два, то:
1) если они оба горят, или оба выключены, то получается внутренний цикл, который к решению не приводит, и мы идём дальше
2) если их состояние разное, то решение за один проход.
Сейчас, сейчас
Лампочки трогать нельзя, они находятся за стеклом, и потому по теплоте лампочек определить включали мы их или нет нельзя.
В вагонах ничего отставлять нельзя.. не знаю почему. просто нельзя)
Ваша задача при помощи управления светом в вагонах и перемещения по ним узнать сколько в этом кольце вагонов.