theJam.ru

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

23 сентября 2008 | Добавил: aleg940

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

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
Метки

Комментариев: 30

  1. Nate пишет:

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

  2. tib пишет:

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

  3. tib пишет:

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

  4. rin пишет:

    Поезд запустить :) клёво конечно, но как?

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

  5. Nate пишет:

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

  6. tib пишет:

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

  7. Nate пишет:

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

  8. SusAnna пишет:

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

  9. Nate пишет:

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

  10. SusAnna пишет:

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

  11. Nate пишет:

    как представлю сколько ему бедному идти придеться... так жалко его становтся )

  12. rin пишет:

    Воот! Если он внутри, то можно, допустим, выкрутить лампочку в одном вагоне, а затем проходя остальные вагоны оставлять включенным(или включать) свет, в конце концов дойдём до вагона, в котором свет не включится.

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

  13. rin пишет:

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

  14. Nate пишет:

    вот это, наверное, и есть правильный ответ...
    но сколько же это пройти надо .... )

  15. WeKo пишет:

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

  16. vestran пишет:

    Я бы действовал в обоих направлениях. Т.е. при обходе влево - выключать свет во всех вагонах слева от исходного, а при обходе вправо - включать во всех вагонах справа от исходного. И когда колличество освещённых, или неосвещённых вагонов уменьшится на 1, это будет означать, что "рассчёт закончен", останется суммировать их колличество 8-)

  17. SusAnna пишет:

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

  18. vestran пишет:

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

  19. SusAnna пишет:

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

  20. vestran пишет:

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

  21. vestran пишет:

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

  22. макс пишет:

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

    Думать надо головой.

  23. SusAnna пишет:

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

    Думать надо головой.

    Согласна с Вами, только прежде чем ставить себя выше (умнее) других, стоит убедиться в достоверности своих аргументов.

  24. lka пишет:

    включим свет в вагоне с Проводником. (если он и так включен то ни чего не будем делать) обозначим его как вагон №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 и продолжаем поиск.

  25. Dmitry пишет:

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

  26. mydryj пишет:

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

  27. Visitor пишет:

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

  28. SM пишет:

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

  29. zavkaf пишет:

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

  30. ZEVAKA пишет:

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

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать