58. Круглый поезд

Хорошая задачка
Я такой вариант придумал:
Машинист выбирает "нулевой" вагон. Зажигает в нём свет (или оставляет зажжённым).
Далее он идёт в определённом направлении от этого вагона (скажем, по часовой стрелке) и считает количество пройденных вагонов до тех пор, пока не встретит первый "зажжённый" вагон. Тогда он гасит в нём свет и идёт обратно, отсчитывая запомненное число, чтобы остановиться точно в нулевом вагоне. Если в нём свет горит -- операция повторяется. Если нет -- то запомненное число и есть искомое количество вагонов.

Так и есть.

Интересно, можно ли быстрее.

Вродебы быстрее нельзя..
Ибо пришёл к такому же решению.

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

Sweety
Нулевой вагон - условное понятие. Его определяешь сам - любой вагон.

Sweety
И что? В решение вчитайтесь.

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

Ууу, нет.
Раз уж учитываете теорию вероятностей, так учитывайте её грамотно.
Есть такая теорема, которая, в частности, говорит:
Если записать случайное число в виде десятичной (бесконечной) дроби, то ЛЮБАЯ сколь угодно длинная заранее заданная последовательность цифр встретится в этой записи БЕСКОНЕЧНОЕ число раз.

eruditor
Акцент был на "практической" :) Иначе и ваше решение не имеет смысла, если число вагонов устремить к бесконечности.

Моё решение имеет смысл при любом числе вагонов.

С практической точки зрения, вы никогда, принципиально, не ответите на вопрос чему равно это ваше "определённое" количество, которое нужно проверить.

eruditor
Метод неполной индукции на практике имеет куда большее значение часто, чем та же теория вероятностей. :)

Меня одного плющит? или как?
Похоже Sweety в такой же прострации ... "до тех пор, пока не встретит первый "зажжённый" вагон" - мне интерес принцип (свойство) по которому машинист определит что это "нулевой" вагон", если он его помнит по каким-то другим признакам, то вообще ему этот свет и не нужен !!! Поясните решение для особо непонятливых.

Специально "для особо непонятливых"...
ВНИМАТЕЛЬНО прочитайте решение. Там все очень подробно расписано.

Если не поможет, нарисуйте для наглядности схему поезда и ЕЩЁ раз прочитайте...

Уточнение решения
Машинист не знает даже примерного количества вагонов, сколько их, 10, 100, 1000? Для того, чтобы создать "настоящую" точку отсчета, точнее вагон, необходимо сделать её уникальной. А правильнее - исключить теорию вероятностей и построить математическую последовательность. Например, выбираем условно "нулевой" вагон, оставляем в нем зажженным свет, в следующем втором вагоне свет выключаем (1), в третьем свет включаем, в четвером и пятом выключаем (2), в шестом включаем, в седьмом, восьмом и девятом (3) выключаем и т.д. При этом ведем счет вагонов. Как только добрались до построенной нами последовательности, отсчет заканчиваем.

"Как только добрались до построенной нами последовательности"?..
Опишите поточней, что это за момент.

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

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

у меня есть еще вариант, правда тоже долгий, но верный
Нужно выбрать условный нулевой вагон(предположим свет там горит). Далее двигаться от него сначала вправо на 1 вагон и включить там свет(или оставить включенным), вернуться в нулевой (просто отсчитав один вагон назад) - и пойти влево на 1 вагон, там свет оставить выключенным. Потом точно так же, только проходить уже по 2, по 3 и так далее вагонов туда и обратно, каждый раз начиная отсчет с нулевого. Предположим, там 10 вагонов, не считая нулевого. Тогда машинист включив свет в шестом вагоне справа, вернется в нулевой, пойдёт отсчитывать шесть вагонов налево, и окажется, что свет включен в пятом вагоне, то есть в том, где он его однажды его уже выключал. Значит, вагонов 10+нулевой. Если без нулевого число вагонов нечетное, всё будет так же, только машинист наоборот увидит выключенный свет там, где он его уже включал.

???
а нельзя сначала выключить везде свет, а потом по одному включать таким образом считая?

можно совместить решение eruditor'a и lynx
тогда будет немного быстрее.
Нужно выбрать условный нулевой вагон(предположим свет там горит). Далее двигаться от него сначала вправо на 1 вагон и включить там свет(или оставить включенным) - вот тут первое изменение - мы идем вправо пока не встретим вагон без света(пусть он n-нный). Затем включаем в нем свет, также возвращаемся до 0 вагона и идем влево пока не встретим вагон с включенным светом(k-тый вагон). идем опять вправо на n вагонов а потом еще направо пока не встретим вагон без света ну и т.д. по решению lynx

пропустил
после "встретим вагон с включенным светом(k-тый вагон)" - возвращаемся к 0 вагону а потом только идем вправо на n вагонов

to Kelly
нельзя никак определить что мы выключлили свет "везде" так как неизвестно количество вагонов. на все рассуждения типа "ну возьмем большое число например 1000 и выключим свет у тысячи вагонов" можно ответить - "а если вагонов больше 1000?"

Fibonacci, все мы так рады, что вы поделились с нами этой новостью.

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

2 Basta
так можно невзначай выключить и вагон №1

ларчик просто открывался
а что мешает сделать следующее:
1) вырубить везде свет
2) выбрать любой вагон и там его включить
3) посчитать вагоны, двигаясь в любую сторону, пока не наткнется на горящий вагон

ларчик просто открывался
А как можно узнать, что свет вырублен ВЕЗДЕ? Число вагонов бесконечно.

А как можно посчитать вагоны, если их бесконечно? ХD

Еще решение
шаг 0) Включаем свет в вагоне, в котором находимся, и считаем его нулевым.
шаг 1) Присваиваем i=1 и далее в каждый момент помним текущее значение i.
шаг 2) Идем сначала на i вагон вперед и выключаем там свет.
шаг 3) Возвращаемся в нулевой вагон (помня i - на сколько вагонов нужно вернуться) - свет должен гореть.
шаг 4) Идем на i вагон назад и выключаем там свет. считаем сколько вагонов прошли.
шаг 5) Возвращаемся в нулевой вагон (помня i - на сколько вагонов нужно вернуться) - свет должен гореть.
шаг 6) i=i+1, идем на шаг 2.

Если при прохождении алгортима мы вернулись в нулевой вагон, а там свет не горит - то СТОП!!!! количество вагонов в поезде = i

Долго, но можно вместо машиниста компьютер пустить, ему все равно, он железный :-)
Хотя, может еще лампочка перегореть :-)

Написано до тебя уже давно! Читай посты других участников!!!

2 //7777777 Число вагонов бесконечно
Тогда как их можно посчитать ?

Практическое (варварское)решение
Бьем лампочку или ломаем выключатель в 0-м вагоне и - вперед!

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

Принципы решения
Решений может быть несколько, но есть общие принципы, на которых они построены:
1. При первом проходе по составу машинист никогда не может надежно определить, прошел он уже стартовый вагон или еще нет. При этом машинист не может точно полагаться на оставленную в одном или нескольких вагонах сигнатуру (например, 5 вагонов с включенным светом), поскольку состав может быть большим и в нем любая сигнатура неоднократно может встретиться по теории вероятности. Но оставить сигнатуру в начале состава все равно необходимо, поскольку машинист должен как-то предположить, что в этой части он уже был, чтобы не бегать по кольцу до бесконечности.
2.Допустим машинист идет по составу и предположил, что некоторый вагон является стартовым (совпала сигнатура, в том числе, свет в этом вагоне). 100% способ для машиниста проверить, что он уже был в этом вагоне, состоит в том, что он должен переключить в этом вагоне свет (включить, если выключен и выключить, если включен), вернуться назад - в вагон, который, по его мнению, тот же самый, и увидеть - переключен там свет или нет. Если свет переключен, то он нашел дошел до стартового вагона и знает общее число вагонов в составе. Если свет не переключен, то нужно продолжать поиск сигнатуры

Рещение есть. приблизительное... но не сложное.
Проводнику нужно лишь выглянуть в окно из вагона при выключенном свете(так просто лучше видно) и на вскидку прикинуть примерное расстояние до вагонов напротив. так как вагонов очень много отклонение от перпендикулярности полученного таким образом диаметра круга бужет невелико и им можно будет пренебречь. Зная диаметр мы можем вычислить длину окружности. и разделив ее на длинну вагона (а она стандартна) получим их количество.

В таком случае все зависит от точности глазомера проводника

2BuBBa
По моему чистой воды бред.
>>так как вагонов очень много,
то можно и не увидеть "вагонов напротив".

2 igar
Ты можеш представить себе такой поезд? Я нет. Но даже в этом случае длина поезда строго ограничено 44 тысячами километрами и даже в ЭТОМ случае число вагонов будет конечна. Не доводите до абсурда задачу. если вагонов напротив невидно(?) то как можно узнать что поезд сцеплен покругу? принять наверу? нет...

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

total
Может, вы удосужитесь прочитать написанное выше, прежде чем писать что-то своё?

Без заморочек
Машинист может оставить какую-либо свою вещь в нулевом вагоне, а затем идти и считать вагоны, пока не наткнется на оставленную вещь!

Все проще
При первом проходе везде включать свет. При втором в одном из вагонов свет выключить и считать вагоны пока не наткнется на вагон с выключенным светом.

Beaver прав)
либо сначало включить либо выключить во всех свет, затем выбрать один и изменить в нем состояние лампы, соответственно от него и вести отсчет

Тактика следующая:
1. В начальном вагоне выключаем свет (нулевой вагон).
2. Идем вправо до тех пор пока не встретим вагон с выключенным светом (обозначим как N-ый вагон) и включаем свет.
3. Идем влево до нулевого вагона. Если вагон включен, значит всего N вагонов. Если нулевой вагон выключен, то следующий шаг.
4. Идем влево от нулевого вагона и включаем свет везде, пока не встретим N-ое количество включенных вагонов подряд (т.к. справа от нулевого вагона есть N-ое количество включенных вагонов).
5. Идем дальше пока не встретим выключенный вагон. Включаем его. Запомнили сколько теперь вагонов прошли слева, обозначаем как N-ое количество.
6. Повторяем шаги с 3 по 5 только в другую сторону. И так далее вправо-влево-вправо-влево. Пока не найдем точное количество вагонов.

Можно усовершенствовать предыдущий способ. Когда включаешь свет в N-ом вагоне и собираешься возвращаться к нулевому вагону, то можно проверить (N+1)-ый вагон.
А. Если он выключен как и N-ый вагон и зная что с другой стороны нулевого вагона свет должен быть включен, то можно не возвращаться до нулевого вагона, а идти дальше, начав отчет "N-ых включенных вагонов с другой стороны" заново.
Б. Если вагон включен. То возвращаемся к нулевому вагону. Если он выключен, то идем дальше включая свет в вагонах до тех пор пока не встретим N-ое количество подряд включенных вагонов, где (N+1)-ый вагон выключен.

Можно посто пройти включая свет во вссех вагонах:-)

И как ты определишь что включил свет уже во всех вагонах и дальше по пути нет вагонов с выключенным светом?

Если вагонов не много. Просто выключить свет, и идти считать вагоны, пока в выключенном вагоне не попадутся теплые лампочки:)

Я бы сломал выключатель, либо зафиксировал его в среднем положении. Затем просто надо идти и включать свет считая , чтобы не споткнуться)

Есть два варианта с вагонами, их либо чётное количество либо нечётное.
Итак, считаем вагоны группами по два и маркируем 1-свет есть, 0-света нет (например в первом нет света в следующем есть — 01)
Например: 11/01/10/10/10/1 — это поезд с 11 вагонами. При последовательном прохождении мы получим устойчивый сигнал вида 31222323111 — этот сигнал пришёл с "шумом", т.к количество цифр в нём нечётное, а следовательно это и есть количество элементов, т.е 11. В случае если сигнал без шума (чётное количество вагонов) — например группа 11/01/10/10/10 выдаёт сигнал 31222 — то сложив полученные цифры получим 10 вагонов. Следует помнить, что мы считаем физические объекты, а значит наличие 0 в сигнале без шума — это 2 (2-а вагона без света). Задача решена в два линейных прохода 1 массивом.

Что за «устойчивый сигнал» такой? Повторяющийся? Никакое количество повторений одной и той же последовательности не даёт гарантий, что эта последовательность будет повторяться и далее.

1. Противоречие в задаче:
Несколько вагонов сцеплены между собой по кругу. Количество вагонов может быть ну очень большим.
2. Внимательно читаем вопрос:
Он может только включать или выключать свет в вагонах. Как ему это сделать?
Ответ: Включить свет или выключить свет включателем!

Я придумал более быстрое решение. Не n * n переходов, а только 5 * n (или меньше)

// Initialising
int i, n = 1;
boolean direction = true;
Turn lihgt off

// Loop starts
while (true) {

// Turn n lamps off and one on
for (i = 0; i <= n; i++) {
moveTo(train, direction);
Turn lihgt off
}
Turn lihgt on

// Change direction
direction = !direction;

// Double n
n <<= 1;
System.out.println("I check light in " + n + " carriages in " + (direction?"right":"left") + " direction");

// Check for light in the n carriages
for (i = 1; i <= n; i++) {
moveTo(train, direction);
If lihgt is on then break (exit from loop)
}

// Loop ends
if (i < n) break;
}

// Show the results
System.out.println("I think, the number of carriages is " + i);

Я так понимаю, отличие от варианта #2 в том, чтобы ходить туда-сюда не до первого встреченного вагона, а забегами по [m]2^n[/m] вагонов? Но насколько оно быстрее, зависит от того, как изначально включен свет. Если весь поезд тёмный, то решение #2 найдёт ответ всего за один проход туда-сюда.

Что если…
1 включить свет в первом, К = 1.
2. Доходим до К — того вагона (считая от нулевой точки, включая первый вагон) с включенным светом, попутно включая свет в выключенных К вагонах.
3. Идем дальше и отсчитываем К включенных (без нас) вагонов — если таковых не насчитывается и мы встречаем выключенный свет, то это не наша комбинация, включаем свет и повторяем с пункта 2. Если же мы насчитали К включенных (без нас) вагонов, выключаем в последнем (N = 2К -том вагоне) свет и возвращаемся к К-тому вагону и проверяем его. Если он выключен — то вагонов в кольце К, если включен, то возвращаемся к 2К-тому вагону и повторяем пункт 2. Размер проходов вперед будут расти минимум в прогрессии 2 степнь М, где М — число проходов вперед, в худшем варианте включенного света во всех вагонах. Возвращаться для проверки мы будем только на половину уже пройденного пути.

Самый простой способ — это включаем свет в текущем вагоне, переходим вправо. Если там света нет то идем далее вправо. Как только при движении вправо наткнулись на вагод со светом — выключаем его и возвращаемся влево до исходного вагона. Если в исходном вагоне свет погас — то все. Иначе снова идем вправо.
Но этот вариант может быть слишком долгим. Можно с целью оптимизации по ходу движения создавать постоянно увеличивающиеся в размере цепочки вагонов что-то типа 1101001000100001000001....... Тогда придется меньше бегать туда-сюда из-за встретившейся случайной первоначальной комбинации, которая сходна с началом нашей ключевой цепочки.
А вообще в реальности сцепить вагоны в кольцо довольно трудное задание (если даже не невозможное)

Вроде бы гарантированное решение для любого кол-ва вагонов.
Делаем метку произвольной сложности. Например, 11100100111.
Идем вправо, пока не встретим такое сочетание вагонов. Выключаем в среднем вагоне свет, т.е. меняем 11100100111 на 11100000111.
Возвращаемся влево к нашей оригинальной метке и проверяем ее. Если она не изменилась, значит нам надо стереть дубликат и продолжать этот цикл.
Если оригинальная метка изменилась, то мы гарантированно прошли весь круг.

По сути это тот же вариант, что тут уже предлагали, просто я добавил проверку, не является ли встреченная комбинация оригинальной меткой.

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

Где гарантии, что эта последовательность точек и тире не встретится нигде в изначальном состоянии поезда?

Сигнатура это хорошо. Надо только учесть, что она не может быть длинней состава. Какова минимальная длина? Кольцо из 1-ого вагона невозможно. Кольцо из двух вагонов трудно себе представить. Допустим, что кольцо из трех вагонов с большой натяжкой, но возможно. Тогда сигнатура 110 (нулевой вагон светлый-1, первый вагон светлый-1, второй вагон темный-0). Вишенка в другом. Машинист отправляется искать сигнатуру, считая количество пройденных вагонов N. Когда находит, то найденную изменяет произвольным образом и возвращается на N вагонов обратно. Если в исходных 3-х вагонах ничего не изменилось, значит состав длиннее N. Он гасит в них свет и идет к месту, где поменял сигнатуру. Теперь это НОВАЯ точка отсчета. Здесь он может установить сигнатуру длинной N (1...10). Начиная с N+1 -ого вагона, ищет новую сигнатуру вышеуказанным способом. Если через М вагонов он ее найдет и это еще не длина состава, то устанавливает новую точку отсчета с сигнатурой длинной N+M и т.д. Понятно, что чем длиннее сигнатура, тем больше ненужных последовательностей она отфильтровывает.