theJam.ru
|
Разделы:
Lifehack12
Данетки95
Игры139
Игры на бумаге17
Книги14
Конкурсы8
Логические задачи346
Люди3
Новости6
Познавательно33
Почемучки14
Притчи4
Работа сайта10
Разное10
Сделай сам10
С праздником16
Страшно жить10
Творчество41
Тесты14
Фото4
Хобби2
Юмор105
 Логические задачи → Посчитать вагоны
23 сентября 2008 | Добавил: SusAnna
Имеется N вагонов сцепленных покругу. В каждом вагоне в случайном порядке включен или выключен свет. Придумайте способ, как служащему посчитать количество вагонов в сцепке.
Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
Метки → сложные
|
Случайное:
Обсуждения:
Ogra → Инспектор Варнике
Carcass → Тест советского восьмиклассника
Руслан → Слова, оканчивающиеся на “зо”.
ололошин → Незадачливый рыбак
lisicanasta → Инквизиция в наши дни
Ogra → И все же, они вертятся?
SM → Последовательность
Nastya → Бесконечная игра
SpAwN# → Самая трудная игра в мире
Полезное:
Карта сайта:
|
23 сентября 2008 в 23:41
записать на листочке последовательность из 0 и 1 (выключен или включен свет) и когда он заметит, что оно начало повторятся . остановиться. и посчитать количество цыфр на листочке, до начала повторения :)
23 сентября 2008 в 23:52
а как он заметит, что оно начало повторяться?) если последовательность что-то вроде 101101101101101101101101 и при этом вагонов около мильёна ;)
23 сентября 2008 в 23:54
ыыы, обсудил щас задачу с другом, он написал:
"Надо запустить поезд и, учтя силу Кориолиса, заметить центростремительное ускорение. Найти радиус кривизны и через него -- длину окружности сцепки. А дальше поделить на длину одного вагона."
24 сентября 2008 в 00:09
Поезд запустить :) клёво конечно, но как?
Не любитель данеток, просто уточняю: служащий внутри или снаружи вагонов ходит? внутри Если внутри, то можно ли пользоваться выключателями(тогда сразу много вариантов возникает)? можно
А если снаружи, то можно былоб без сил Кариолиса замерить радиус кривизны... хотя бред конечно, ответ видимо проще
P.S. Зачем вообще так сцеплять вагоны, ещё и свет там хаотично оставлять? для того, чтобы Вы подумали как можно решить такую задачу :) для пассажиров что ли? :)
24 сентября 2008 в 00:45
если он не в нутри вагонов, то можно в центре встать и на земле, или снегу рисовать метки. типа засечки. с какого вагона начал. ну и чтоб не сбиться можно на каждый вагон засечку рисовать :)
но тогда свет не причем :)
24 сентября 2008 в 00:51
да явно внутри он, чо уж, и в окно выглянуть не может, иначе задача обессмысливается :)
24 сентября 2008 в 02:05
тогда долго ему придется обход делать :)
сперва обойти и все выключить. а потом обойти и все включить считая включения до первого включенного. (или наоборот)
или тупо обойти и в каждом вагоне оставлять записку - типа "вагон номер раз", "вагон номер два" и т.д. ... :)
24 сентября 2008 в 12:44
Nate , у него нечем писать и он не модут ничем сделать засечки. А на счет все обойти и выключить свет: а как он узнает что он обошел ВСЕ вагоны. Ведь может быть ситуация когда вагонов миллион и свет включен только в первом. Он его выключит и пойдет дальше, на каком счете он поймет, что это уже первый вагон в котором он был?
Тем более решение с записками или засечками очевидное, я бы не поставила метку "сложные".
Можно конечно распустить свитер и тянуть веревочки между вагонами, но тогджа метка задачи была бы "физические". Думайте, решение должно быть логическим!
24 сентября 2008 в 14:49
он может их привести в движение?
и например на любой вагон (будем считать его первым) привяжет длиную пластинку возвышающуюся над крышей. а на мосту, под которым проезжают вагоны повесить колокольчик.
запустить вагоны и считать их, когда колокольчик зазвенит - прекратить счет. это снова первый вагон.
24 сентября 2008 в 15:13
Служащий находится внутри вагонов и может ходить только внутри. Никаких дополнительных предметов у него нет, ни колокольчиков, ни ниток, ни маркеров, ни песка, ни чего-либо еще, есть только выключатели в вагонах, которые включают/выключают свет в этом вагоне.
Подсказка: Решение задачи является неким алгоритмом, по которому он должен обходить вагоны и что-то делать со светом.
24 сентября 2008 в 15:18
как представлю сколько ему бедному идти придеться... так жалко его становтся )
24 сентября 2008 в 21:07
Воот! Если он внутри, то можно, допустим, выкрутить лампочку в одном вагоне, а затем проходя остальные вагоны оставлять включенным(или включать) свет, в конце концов дойдём до вагона, в котором свет не включится.
И ещё один метод придумал(ацке сложный):
у нас есть вагон, в котором мы стоим - первый; и есть две стороны обхода: направо и налево (относительно нас смотрящих в окно у боковых сидений)
В первом вагоне свет выключим,
теперь идём направо и выключаем во втором вагоне свет, затем возвращаемся в первый вагон;
из первого вагона идём налево и включаем в минус первом вагоне свет
возвращаемся в первый вагон идём направо проходим второй, идём дальше и в третьем оставим свет выключенным... ходим туда-сюда, вобщем
Что получим в итоге:
дойдя до определённого периода мы начнём выключать свет там где до этого его включали (и наоборот). А это значит, что наступит момент, когда пойдя на лево из первого вагона мы в минус первом увидим выключенный свет! Тогда количество вагонов, которое мы насчитали идя направо и есть искомое количество вагонов!
Вроде не перемудрил :)
24 сентября 2008 в 23:16
Перемудрил, конечно, в последнем:
слева можно оставить только минус первый вагон с включенным светом (больше налево не ходить :) ). Затем надо после каждого выключения справа света проверять включен или нет свет в минус первом вагоне. Кстати чтоб не ходить в потёмках лучше поменять стратегию на обраную(один вагон оставить с выключенным светом, в остальных его включать)
25 сентября 2008 в 09:20
вот это, наверное, и есть правильный ответ...
но сколько же это пройти надо .... )
25 сентября 2008 в 10:05
rin,
зачем лезть в "минус первый" вагон, по моему проще выключить свет в том, в котором стоишь первоначально
25 сентября 2008 в 11:06
Я бы действовал в обоих направлениях. Т.е. при обходе влево - выключать свет во всех вагонах слева от исходного, а при обходе вправо - включать во всех вагонах справа от исходного. И когда колличество освещённых, или неосвещённых вагонов уменьшится на 1, это будет означать, что "рассчёт закончен", останется суммировать их колличество 8-)
25 сентября 2008 в 13:04
молодцы, господа! Но, есть одно маленькое "но" :)
rin, Ваш метод немного затратнее, ечи я правильно посчитала, то вам нужно сделать 110 проходов, чтобы найти количество вагонов, тогда как в методе vestran'а всего 65 :)
Я решила эту задачу немного по-другому. Я ходила влево-вправо увеличивая вагонов на 1 и меняла положение выключателя в каждом вагоне и запоминала положение выключателя в последнем. Например:
в исходном вагоне я меняю положение переключателя и запоминаю его.
иду влево на 1 вагон, меняю положение переключателя и запоминаю каким оно стало.
затем иду вправо, по пути проверяю положение переключателя в исходном вагоне, если оно не поменялось иду на один вагон правее,меняю положение переключателя и запоминаю его.
иду влево уже на 2 вагона, сравниваю положение переключателя с тем что я запомнила, если совпадает, иду на 1 вагон левее и так далее.
До тех пор пока запомненное положение переключателя не будет отличаться от реального.
25 сентября 2008 в 15:14
SusAnna, Вы нам чего-то не договариваете? Как это вам удалось посчитать колличество проходов в решении по алгоритму rinа и по моему алгоритму. И сколько проходов в таком случае в решении по вашему алгоритму? 8-0
25 сентября 2008 в 16:00
vestran, ой я тут просто перемудрила немного :) просто я проверяла ваши алгоритмы на примере 10 вагонов :)
так вот, rin, прибавляя каждый раз по одному вагону он проходит это расстояние по 2 раза, то есть получаем число проходов: СУММА_по_i(i*2), где i = 1 to 10.
В Вашем же случае (так же как и в моем) Вы ходите туда-сюда прибавляя по одному вагону, но последний круг проходится 2 раза, то есть получаем: СУММА_по_i (i) + N, Где i = 1 to N (в нашем случае N=10)
25 сентября 2008 в 17:49
SusAnna, ну я примерно так и подумал. Только хочу заметить, что в наших с rinом алгоритмах колличество проходов зависит от того как включен свет. Если, к примеру, свет нигде не горит, то сколько бы не было вагонов в сцепке, нужно всего два прохода. 8-)
25 сентября 2008 в 20:11
О-о! Ну я тоже чуть намудрил в моём алгоритме в предпоследнем проходе свет будет включен, либо выключен во всей сцепке и посчитаны вагоны, а в последнем проходе, просто убеждаемся, что кольцо замкнуто. И ещё только что подумал, что можно в обе стороны выключать свет (для экономии энергии и ресурса выключателей).
3 октября 2008 в 04:22
Еще проще: включить свет в 2 вагонах в котором находишся и в соседнем, пойти дальше выключая везде свет(не важно в какую сторону)и как только наткнешся на 2 вагона с включенным светом, выключить в одном свет, вернуться посматреть а горит ли в тех 2 вагонах свет если не значит ты прошел круг.
Думать надо головой.
3 октября 2008 в 13:18
макс, если я правильно поняла, то Вы движетесь по 2 вагона за раз. Тогда, при количестве вагонов равном 10, и в худшем случае (когда свет включен везде) получается 70 проходов (формула для вычисления 2*СУММА_по_i(3+2*i), где i = 0 to N/2-1) что не лучше чем у vestran. Если же Вы продвигаетесь по одному вагону за раз, то получается и того больше. Единственное Ваш алгоритм дает меньше проходов, при нечетном N, а при четном, как показано выше - больше.
Согласна с Вами, только прежде чем ставить себя выше (умнее) других, стоит убедиться в достоверности своих аргументов.
26 ноября 2008 в 13:31
включим свет в вагоне с Проводником. (если он и так включен то ни чего не будем делать) обозначим его как вагон №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 и продолжаем поиск.
21 марта 2009 в 06:10
Ребят, наверное, постановка страдает, но. Почему бы не
1. найти "дырку" - то есть первый неосвещенный вагон.
2. начать считать вагоны, начиная со следующего за "дыркой" освещенного вагона, при этом оставив в нем свет.
3. каждый попавшийся вагон считать и выключать свет если включен.
4. убедившись что количество освещенных вагонов - 1 (единица) просто выключить в нем свет.
10 июля 2009 в 22:07
все гораздо проще. проводник снимает ботинок с себя и обходит. в итоге натыкается на свой ботинок
12 июля 2009 в 21:03
Пройти 2 круга. Первый - все включить/выключить. Второй - считать кол-во вагонов, проделывая обратную операцию. Т.к. поезд стоит по кругу, то всегда можно глянуть в окно и посмотреть, горит ли где еще свет (выключен ли где еще) на первом этапе. Взяв те же 10 вагонов, получаем 20 повторов. Ну плюс 3 на погрешность (проверка соседних, не попадающих в угол обзора).
4 августа 2009 в 04:59
Пройти полкруга! =)
Первый вагон: включил свет.
Дальше идешь - выключаешь в остальных и считаешь вагоны.
Когда выключаешь - смотришь в окно (в центр круга вагонов).
Если видишь напротив себя вагон, в котором включен свет, а сзади того вагона света нигде нет - ты дошел до середины = умножай посчитанное число вагонов на два. Иначе - идешь дальше.
12 октября 2009 в 03:04
если n не стремится к бесконечности, а примерно к 10, то можно предположить, что включив свет на пару минут мы обеспечим прогрев светильника (если это не люм), тем самым, включая и выключая свет и робуя нагрев светильника мы дойдем до вагона в котором толькошчто включался свет!!!
тру????
3 февраля 2010 в 19:56
Ну нет Visitor. А если кол-во вагонов очень велико (там ведь оно не уточняется), то может и получиться так, что противоположный вагон находится за перделами видимости