Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Задача. Странный поезд

Задача. Странный поезд
Я
   1Сергей
 
27.07.18 - 09:28
Есть поезд, состоящий из некоторого количества вагонов. Вы находитесь в одном из них. Это очень странный поезд, потому что его вагоны сцеплены в кольцо. В каждом вагоне есть лампочка, которую вы можете включать и выключать. Ваша задача заключается в том, чтобы определить количество вагонов в поезде. Опишите алгоритм решения этой задачи.

Других людей и прочих живых или неживых существ в поезде нет. Лампочки нельзя выкручивать, они не перегорают и не нагреваются, рисовать на стенах мелом нельзя, окон у вагонов нет. В общем, состояние поезда — это только лампочки. Кстати, начальное состояние поезда неизвестно, то есть изначально какие-то лампочки могут гореть, а какие-то не гореть. Единственный способ узнать, горит ли лампочка в определенном вагоне — это войти в него и посмотреть.
 
 
   Fish
 
1 - 27.07.18 - 09:30
Какой-то старый баян.
   Cyberhawk
 
2 - 27.07.18 - 09:32
Наверное, при первом кольцевом обходе нужно сделать какой-нибудь маркер (последовательность включенных - выключенных лампочек), а потом обойти еще разок по кругу от этого маркера до этого же маркера, посчитав количество лампочек (вагонов)
   Cyberhawk
 
3 - 27.07.18 - 09:32
Либо при первом обходе зажечь все лампочки, а потом их гасить
   1Сергей
 
4 - 27.07.18 - 09:32
(2) любая последовательность может повторяться
   Cyberhawk
 
5 - 27.07.18 - 09:33
Конечно
   Малыш Джон
 
6 - 27.07.18 - 09:33
(3) а как определить, все ли ты лампочки зажег?
   Fish
 
7 - 27.07.18 - 09:34
Вот решение:
1. Включим свет в том вагоне, в котором сейчас находимся, он будет у нас первым вагоном.
2. идем вперед по вагонам до следующего вагона с включенным светом, считая количество вагонов.
3. Нашли следующий вагон со включенным светом, это будет вагон с номером n, гасим в нем свет.
4. Возвращаемся на такое же количество вагонов обратно (n-1), таким образом попадаем в первый вагон.
5. если в нем свет не горит, значит на шаге 3 мы же его и погасили, а значит кольцо замкнулось и количество вагонов в поезде n.
6. если горит, то возвращаемся к пункту 2 этого плана.
   Fish
 
8 - 27.07.18 - 09:34
+(7) Но это лишь один вариант. Есть другие.
   Cyberhawk
 
9 - 27.07.18 - 09:35
(6) Думаю, надо бегать туда-сюда, расширяя область охвата
   Cyberhawk
 
10 - 27.07.18 - 09:35
Вон, в (7) уже и расписали ))
 
 Рекламное место пустует
   1Сергей
 
11 - 27.07.18 - 09:36
(7) правильно
   Кай066
 
12 - 27.07.18 - 09:36
Долго вы будете мусолить одно и то же?
Как посчитать сколько вагонов в поезде?
   1Сергей
 
13 - 27.07.18 - 09:48
Проверьте себя
http://prntscr.com/kbddgo
   2S
 
14 - 27.07.18 - 09:50
(13) говорят я Пушкин, дальше чаго делать насальника?
   Fish
 
15 - 27.07.18 - 09:52
(13) Я тоже Пушкин :))
   1Сергей
 
16 - 27.07.18 - 09:53
(14) Напиши сколько баллов набрал. Фалометрией займёмся
   Cyberhawk
 
17 - 27.07.18 - 09:53
Где ссылка-то на Пушкина?
   Fish
 
18 - 27.07.18 - 09:53
(16) Так там уже написано: 26990 :))
   Кай066
 
19 - 27.07.18 - 09:58
(16) Какие баллы, это скриншот
   1Сергей
 
20 - 27.07.18 - 10:25
   Cyberhawk
 
21 - 27.07.18 - 10:47
(20) Такой же результат (26990)
   Fish
 
22 - 27.07.18 - 10:50
   Вафель
 
23 - 27.07.18 - 11:17
Сначала пройти и погасить все лампы. потом 1 включить и пройти и посчитать
   1Сергей
 
24 - 27.07.18 - 11:19
(23) как понять, что погасил все лампы?
   sechs
 
25 - 27.07.18 - 11:19
(0) А я вот еще задачу знаю. Почему канализационные люки круглые?
   1Сергей
 
26 - 27.07.18 - 11:21
(25) ты ещё спроси почему у гориллы ноздри большие :)
   sechs
 
27 - 27.07.18 - 11:25
(26) Ну ты первый начал
   Chang Woo
 
28 - 27.07.18 - 23:24
(25) Известно почему. Мы это в аэрокосмической академии проходили. Размер и форма советского люка соответствуют ракетам которые могут базироваться в шахтах замаскированных под канализационные люки.
   Cyberhawk
 
29 - 28.07.18 - 08:56
(28) В какой из шести?


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует