Посчитать вагоны | Логические задачи

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

Посчитать вагоны | Логические задачи: 30 комментариев

  1. а как он заметит, что оно начало повторяться?) если последовательность что-то вроде 101101101101101101101101 и при этом вагонов около мильёна 😉

  2. ыыы, обсудил щас задачу с другом, он написал:
    «Надо запустить поезд и, учтя силу Кориолиса, заметить центростремительное ускорение. Найти радиус кривизны и через него — длину окружности сцепки. А дальше поделить на длину одного вагона.»

  3. Поезд запустить 🙂 клёво конечно, но как?
    Не любитель данеток, просто уточняю: служащий внутри или снаружи вагонов ходит? внутри Если внутри, то можно ли пользоваться выключателями(тогда сразу много вариантов возникает)? можно
    А если снаружи, то можно былоб без сил Кариолиса замерить радиус кривизны… хотя бред конечно, ответ видимо проще
    P.S. Зачем вообще так сцеплять вагоны, ещё и свет там хаотично оставлять? для того, чтобы Вы подумали как можно решить такую задачу 🙂 для пассажиров что ли? 🙂

  4. да явно внутри он, чо уж, и в окно выглянуть не может, иначе задача обессмысливается 🙂

  5. Nate , у него нечем писать и он не модут ничем сделать засечки. А на счет все обойти и выключить свет: а как он узнает что он обошел ВСЕ вагоны. Ведь может быть ситуация когда вагонов миллион и свет включен только в первом. Он его выключит и пойдет дальше, на каком счете он поймет, что это уже первый вагон в котором он был?
    Тем более решение с записками или засечками очевидное, я бы не поставила метку «сложные».
    Можно конечно распустить свитер и тянуть веревочки между вагонами, но тогджа метка задачи была бы «физические». Думайте, решение должно быть логическим!

  6. Служащий находится внутри вагонов и может ходить только внутри. Никаких дополнительных предметов у него нет, ни колокольчиков, ни ниток, ни маркеров, ни песка, ни чего-либо еще, есть только выключатели в вагонах, которые включают/выключают свет в этом вагоне.
    Подсказка: Решение задачи является неким алгоритмом, по которому он должен обходить вагоны и что-то делать со светом.

  7. Воот! Если он внутри, то можно, допустим, выкрутить лампочку в одном вагоне, а затем проходя остальные вагоны оставлять включенным(или включать) свет, в конце концов дойдём до вагона, в котором свет не включится.
    И ещё один метод придумал(ацке сложный):
    у нас есть вагон, в котором мы стоим — первый; и есть две стороны обхода: направо и налево (относительно нас смотрящих в окно у боковых сидений)
    В первом вагоне свет выключим,
    теперь идём направо и выключаем во втором вагоне свет, затем возвращаемся в первый вагон;
    из первого вагона идём налево и включаем в минус первом вагоне свет
    возвращаемся в первый вагон идём направо проходим второй, идём дальше и в третьем оставим свет выключенным… ходим туда-сюда, вобщем
    Что получим в итоге:
    дойдя до определённого периода мы начнём выключать свет там где до этого его включали (и наоборот). А это значит, что наступит момент, когда пойдя на лево из первого вагона мы в минус первом увидим выключенный свет! Тогда количество вагонов, которое мы насчитали идя направо и есть искомое количество вагонов!
    Вроде не перемудрил 🙂

  8. Перемудрил, конечно, в последнем:
    слева можно оставить только минус первый вагон с включенным светом (больше налево не ходить 🙂 ). Затем надо после каждого выключения справа света проверять включен или нет свет в минус первом вагоне. Кстати чтоб не ходить в потёмках лучше поменять стратегию на обраную(один вагон оставить с выключенным светом, в остальных его включать)

  9. rin,
    зачем лезть в «минус первый» вагон, по моему проще выключить свет в том, в котором стоишь первоначально

  10. Я бы действовал в обоих направлениях. Т.е. при обходе влево — выключать свет во всех вагонах слева от исходного, а при обходе вправо — включать во всех вагонах справа от исходного. И когда колличество освещённых, или неосвещённых вагонов уменьшится на 1, это будет означать, что «рассчёт закончен», останется суммировать их колличество 😎

  11. молодцы, господа! Но, есть одно маленькое «но» 🙂
    rin, Ваш метод немного затратнее, ечи я правильно посчитала, то вам нужно сделать 110 проходов, чтобы найти количество вагонов, тогда как в методе vestran’а всего 65 🙂
    Я решила эту задачу немного по-другому. Я ходила влево-вправо увеличивая вагонов на 1 и меняла положение выключателя в каждом вагоне и запоминала положение выключателя в последнем. Например:
    в исходном вагоне я меняю положение переключателя и запоминаю его.
    иду влево на 1 вагон, меняю положение переключателя и запоминаю каким оно стало.
    затем иду вправо, по пути проверяю положение переключателя в исходном вагоне, если оно не поменялось иду на один вагон правее,меняю положение переключателя и запоминаю его.
    иду влево уже на 2 вагона, сравниваю положение переключателя с тем что я запомнила, если совпадает, иду на 1 вагон левее и так далее.
    До тех пор пока запомненное положение переключателя не будет отличаться от реального.

  12. SusAnna, Вы нам чего-то не договариваете? Как это вам удалось посчитать колличество проходов в решении по алгоритму rinа и по моему алгоритму. И сколько проходов в таком случае в решении по вашему алгоритму? 8-0

  13. vestran, ой я тут просто перемудрила немного 🙂 просто я проверяла ваши алгоритмы на примере 10 вагонов 🙂
    так вот, rin, прибавляя каждый раз по одному вагону он проходит это расстояние по 2 раза, то есть получаем число проходов: СУММА_по_i(i*2), где i = 1 to 10.
    В Вашем же случае (так же как и в моем) Вы ходите туда-сюда прибавляя по одному вагону, но последний круг проходится 2 раза, то есть получаем: СУММА_по_i (i) + N, Где i = 1 to N (в нашем случае N=10)

  14. SusAnna, ну я примерно так и подумал. Только хочу заметить, что в наших с rinом алгоритмах колличество проходов зависит от того как включен свет. Если, к примеру, свет нигде не горит, то сколько бы не было вагонов в сцепке, нужно всего два прохода. 😎

  15. О-о! Ну я тоже чуть намудрил в моём алгоритме в предпоследнем проходе свет будет включен, либо выключен во всей сцепке и посчитаны вагоны, а в последнем проходе, просто убеждаемся, что кольцо замкнуто. И ещё только что подумал, что можно в обе стороны выключать свет (для экономии энергии и ресурса выключателей).

  16. Еще проще: включить свет в 2 вагонах в котором находишся и в соседнем, пойти дальше выключая везде свет(не важно в какую сторону)и как только наткнешся на 2 вагона с включенным светом, выключить в одном свет, вернуться посматреть а горит ли в тех 2 вагонах свет если не значит ты прошел круг.
    Думать надо головой.

  17. макс, если я правильно поняла, то Вы движетесь по 2 вагона за раз. Тогда, при количестве вагонов равном 10, и в худшем случае (когда свет включен везде) получается 70 проходов (формула для вычисления 2*СУММА_по_i(3+2*i), где i = 0 to N/2-1) что не лучше чем у vestran. Если же Вы продвигаетесь по одному вагону за раз, то получается и того больше. Единственное Ваш алгоритм дает меньше проходов, при нечетном N, а при четном, как показано выше — больше.
    Думать надо головой.
    Согласна с Вами, только прежде чем ставить себя выше (умнее) других, стоит убедиться в достоверности своих аргументов.

  18. включим свет в вагоне с Проводником. (если он и так включен то ни чего не будем делать) обозначим его как вагон №1
    идем в следующий вагон если там темно, то это «не учтеный» вагон, включаем свет и идем в следующий и т.д пока не встретим вагон со «включеным светом»
    в вагоне с «включеным» светом Проводник не знает горел ли здесь свет или он сам его включил (обозначим это вагон N1)
    по этому «выключаем» в этом вагоне свет и идем обратно к вагону №1 если в вагоне №1 свет горит то это не кольцо и в поезде больше чем N1 вагонов
    идем в вагон N1 включаем свет (теперь в вагонах с 1 по N1 «включен» свет)
    нам известно что в поезде больше либо равно N1 вагонов значит если в следущих N1-1 вагонах где-то не горит свет, то вагонов не меньше чем N2 где N2—номер вагона в котором был выключен свет, соответсвенно можно проверять еще N2-1 вагон и т.д..
    теперь рассмотрим случай когда прошли определили что вагонов Ni и проверяю следующие Ni-1 вагон свет везде «включен» тогда имеем 2*Ni-1 вагонов с «включеным» светом.
    в последнем 2*Ni-1 «выключаем» свет и идем обратно в вагнон №1 если в каком-то вагоне «выключен» свет тогда мы нашли «цикл» и общее количество вагонов = 2*Ni-1-K
    где К тот вагон где свет оказался «выключен»
    если же во всех вагонах свет оказался «включен» то вагонов не меньше чем 2*Ni-1 и продолжаем поиск.

  19. Ребят, наверное, постановка страдает, но. Почему бы не
    1. найти «дырку» — то есть первый неосвещенный вагон.
    2. начать считать вагоны, начиная со следующего за «дыркой» освещенного вагона, при этом оставив в нем свет.
    3. каждый попавшийся вагон считать и выключать свет если включен.
    4. убедившись что количество освещенных вагонов — 1 (единица) просто выключить в нем свет.

  20. все гораздо проще. проводник снимает ботинок с себя и обходит. в итоге натыкается на свой ботинок

  21. Пройти 2 круга. Первый — все включить/выключить. Второй — считать кол-во вагонов, проделывая обратную операцию. Т.к. поезд стоит по кругу, то всегда можно глянуть в окно и посмотреть, горит ли где еще свет (выключен ли где еще) на первом этапе. Взяв те же 10 вагонов, получаем 20 повторов. Ну плюс 3 на погрешность (проверка соседних, не попадающих в угол обзора).

  22. Пройти полкруга! =)
    Первый вагон: включил свет.
    Дальше идешь — выключаешь в остальных и считаешь вагоны.
    Когда выключаешь — смотришь в окно (в центр круга вагонов).
    Если видишь напротив себя вагон, в котором включен свет, а сзади того вагона света нигде нет — ты дошел до середины = умножай посчитанное число вагонов на два. Иначе — идешь дальше.

  23. если n не стремится к бесконечности, а примерно к 10, то можно предположить, что включив свет на пару минут мы обеспечим прогрев светильника (если это не люм), тем самым, включая и выключая свет и робуя нагрев светильника мы дойдем до вагона в котором толькошчто включался свет!!!
    тру????

  24. Ну нет Visitor. А если кол-во вагонов очень велико (там ведь оно не уточняется), то может и получиться так, что противоположный вагон находится за перделами видимости

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

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

  27. записать на листочке последовательность из 0 и 1 (выключен или включен свет) и когда он заметит, что оно начало повторятся . остановиться. и посчитать количество цыфр на листочке, до начала повторения 🙂

  28. тогда долго ему придется обход делать 🙂
    сперва обойти и все выключить. а потом обойти и все включить считая включения до первого включенного. (или наоборот)
    или тупо обойти и в каждом вагоне оставлять записку — типа «вагон номер раз», «вагон номер два» и т.д. … 🙂

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *