Имя: Пароль:
LIFE
 
OFF: Как посчитать сколько вагонов в поезде?
🠗 (Волшебник 09.01.2018 09:19)
0 fleur
 
09.01.18
00:20
Есть поезд, у которого последний вагон пристегнут к первому (замкнутый поезд). В каждом вагоне есть тумблер для вкл/выкл лампочки. В вагонах случайным образом горят лампочки в вагонах. Как посчитать, сколько вагонов в поезде(алгоритм). Перемещаться можно из любого соседнего вагона в следующий. Жизнь считается бесконечной. И вас сажают в один из вагонов этого поезда. Ваши действия. И да, еще паровоза нет.
1 patya
 
09.01.18
00:27
Машинист выбирает "нулевой" вагон. Зажигает в нём свет (или оставляет зажжённым).
Далее он идёт в определённом направлении от этого вагона (скажем, по часовой стрелке) и считает количество пройденных вагонов до тех пор, пока не встретит первый "зажжённый" вагон. Тогда он гасит в нём свет и идёт обратно, отсчитывая запомненное число, чтобы остановиться точно в нулевом вагоне. Если в нём свет горит -- операция повторяется. Если нет -- то запомненное число и есть искомое количество вагонов.
2 zak555
 
09.01.18
00:30
идёшь и выключаешь все лампочки
когда обнаружишь, что давно не было включённой лампы, включи и считай вагоны )
3 zak555
 
09.01.18
00:33
или
разбить/выкрутить лампу в вагоне и идти считать до первого вагона, где нет лампы
4 patya
 
09.01.18
00:36
В поезде еще должно быть три черепахи с круглыми люками, одна из которых всегда говорит правду иначе их казнят.
5 fleur
 
09.01.18
00:50
(1) и это правильный ответ! 7 минут понадобилось мистянам для решения задачки!
6 fleur
 
09.01.18
00:52
(1) как догадались?
7 zak555
 
09.01.18
00:55
8 h-sp
 
09.01.18
01:13
(6) вот что яндекс животворящий делает.
9 Злопчинский
 
09.01.18
01:23
(6) задача поставлена неверно - отсутствуют ограничивающие условия оптимальности решения. В постановке дстаточно идти по кругу и ставить отметку
10 Капюшон
 
09.01.18
02:51
задавать дату и время в двоичной системе при помощи лампочек в каждом вагоне. тогда вы пройдете круг и будете знать, что прошли его.


(9)вопрос в том, какую отметку ставить. ведь мы не имеем права делать ничего кроме, как переключать тумблеры.
11 H A D G E H O G s
 
09.01.18
03:00
Давайте начнем решать задачу с генерации GUID-а
12 H A D G E H O G s
 
09.01.18
03:01
Запишем его в двоичной форме с начала нашего пути и потом будем считывать пройденные вагоны. Как только встретим наш GUID - будем считать круг пройденным.
13 H A D G E H O G s
 
09.01.18
03:03
Вероятность случайной генерации случайно сгенерированного GUID КРАЙНЕ МАЛА. Амолед импрувед.
14 Zamestas
 
09.01.18
03:28
(1) Прикатит, когда кол-во вагонов известно заранее.
15 Zamestas
 
09.01.18
03:31
+(14) Точнее постоянное - а если их кол-во может изменятся?
16 Капюшон
 
09.01.18
03:56
(13)но вероятность есть. а вот если в лампочках закодировать дату и время, но добавить еще один символ, то вероятность увеличится в разы. Например, первый будет X000001, а последующий будет X0000002  - нужно будет только уловить эту последовательность. хотя это всё равно не тот путь. есть другой алгоритм решения. который 100% дает решение.

И он кроется в создании последовательности из чисел, имеющих зависимость от индекса пройденных.
17 Капюшон
 
09.01.18
03:58
но реального решения нет. Ведь если смоделировать очень большую выборку и заложить в нее повторяющиеся комбинации чисел, то они будут всегда рано или поздно повторяться.

Например, мы пометили три вагона цифрами "1, 2, 3", а через 100 вагонов есть уже такая последовательность, то будет шляпа...
18 Лодырь
 
09.01.18
04:45
(11) Какие GUIDы? Будьте ближе к народу, поставьте мелом крестик или напишите "Hadgehog был тут".
19 dmpl
 
09.01.18
07:33
(1)(2) Баги будут. Где гарантия, что кто-то еще не включит свет?
20 perester
 
09.01.18
08:04
(2) это если количество вагонов примерно ясно, а если их 1000, а считаешь что их 100, то данные будут неверные
(19) задачка чисто теоретическая, если несколько ребят будут одновременно включать-выключать лампы, то без еще одного измерения не обойтись, давайте отмечать вагончики гуидами
21 dmpl
 
09.01.18
08:09
(20) Нигде не сказано, что доступ монопольный. Поэтому нельзя полагаться на это допущение. Но! У каждого вагона есть год выпуска и серийный номер.
22 MaxS
 
09.01.18
08:25
Остановить поезд и попросить проводников всех вагонов выйти на собрание. Подразумевается, что все проводники исключительно дисциплинированные.
23 h-sp
 
09.01.18
08:31
лучше посмотреть в окно, и начинать отсчет от здания вокзала.
24 MaxS
 
09.01.18
08:53
(23) Нет никаких гарантий, что напротив 100500 вагона не стоит такое же здание вокзала.
25 dmpl
 
09.01.18
09:07
(24) А может вообще состав стоит в депо на вращающейся платформе :)
26 patya
 
09.01.18
09:16
(25) Скорость вращения платформы подстраивается под скорость поезда?
27 ProgAL
 
09.01.18
09:27
Эту задачу дают программисту 1с на собеседовании в нижегородском франче эксперт аналитика.
28 hhhh
 
09.01.18
10:10
надо сначала провести тестирование. Выяснить есть ли повторяющиеся участки и какой они длины и с какой периодичностью повторяются. Всё записывать, составить таблицу.

Дальше уже приступать к манипуляциям. То есть например, если период повтора - 10 вагонов, то пройти и выключить лампочку в каждом 10м вагоне.
29 MaxS
 
09.01.18
17:28
(28) В условиях задачи нет описания вида из окна вагонов. Может быть это жд мост в океане, глазом зацепится не за что.
Требовать и эффективности, и гибкости от одной и той же программы — все равно, что искать очаровательную и скромную жену... по-видимому, нам следует остановиться на чем-то одном из двух. Фредерик Брукс-младший