Вход | Регистрация
    1  2
О жизни... :: Наука

OFF: Задача: тигр за дверью

OFF: Задача: тигр за дверью
Я
   Ненавижу 1С
 
23.12.21 - 19:24
Есть 32 пронумерованных комнаты в ряд. В одной из комнат сидит тигр. Каждую минуту вы открываете дверь в одну из комнат. Если там тигр - вы его "поймали". Если нет - вы закрываете дверь. После чего тигр обязательно переходит в соседнюю комнату по отношению к той, где был - в одну из сторон по своему усмотрению (кроме крайних комнат, там только в одну сторону). После чего всё повторяется.
Можно ли гарантированно "поймать" тигра и если да - то сколько минут для этого понадобится?
   Arbuz
 
101 - 24.12.21 - 13:36
тогда я тоже могу
   Ненавижу 1С
 
102 - 24.12.21 - 13:37
(101) что ты можешь?
   Ненавижу 1С
 
103 - 24.12.21 - 13:37
(100) неправда, 32
   Krendel
 
104 - 24.12.21 - 13:37
(99) он просто ждет, когда тигр к нему придет
   pechkin
 
105 - 24.12.21 - 13:37
(100) те только для 64 комнат нельзя поймать. А для меньшего можно?
   Arbuz
 
106 - 24.12.21 - 13:43
(105) Да можно для любого, я проиграл )) куда деньги слать?
   Kassern
 
107 - 24.12.21 - 13:51
(106) вот сюда http://amur-tiger.ru/ru/ у них свой фонд есть)
   gr13
 
108 - 24.12.21 - 14:07
(105) почему нельзя? можно для любого количества комнат поймать, в чем проблема, то?
   osa1C
 
109 - 24.12.21 - 14:31
(50) Короли всегда возвращаются ив Испании и во Франции и даже блин в России
   Shur1cIT
 
110 - 24.12.21 - 15:33
(0) нет нельзя, ибо тигр может гулять между двумя комнатами, а ты открывать их когда его нет
   Kassern
 
111 - 24.12.21 - 15:50
(110) возьмите 5 комнат и придуймайте алгоритм для тигра, чтобы его не поймали. охотник будет ходить так 23455432
   Kassern
 
112 - 24.12.21 - 15:50
тот же принцип работает и на N комнат
   Митяйский
 
113 - 24.12.21 - 15:58
(111) 234432 будет для пяти комнат.
Ответ в самом начале темы дали правильный, 2N-4
   ManyakRus
 
114 - 24.12.21 - 16:10
(113) 234432 - ответ неправильный, убежит тигр
23455432 - ответ почти правильный, но дверь 1 тоже надо открывать в конце т.к. задача поймать тигра а не узнать где он прячется

мой ответ: 2N-3
   Митяйский
 
115 - 24.12.21 - 16:12
(114) ну тогда 2N-2, потому что надо количество минут, а не количество открываний двери
   Kassern
 
116 - 24.12.21 - 16:13
(114) "ответ неправильный, убежит тигр " напишите последовательность, при которой он убежит)
   ManyakRus
 
117 - 24.12.21 - 16:16
(115) нет нулевой минуты бесплатной, всё равно 2N-3
   Митяйский
 
118 - 24.12.21 - 16:18
(117) Напиши, как тигр убежит. Гипотетический тигр в комнате 1 на последнем ходу ловится в первые три хода, тащемто
   ManyakRus
 
119 - 24.12.21 - 16:19
(116)
охотник: 234432
тигрррр: 212345
открывать дверь 2 раза подряд бесполезно :-)
   Митяйский
 
120 - 24.12.21 - 16:20
(119) на первом ходу это что такое?
   Kassern
 
121 - 24.12.21 - 16:22
(119) вы издеваетесь над животными?? Сразу к охотнику пихнули?)
   ManyakRus
 
122 - 24.12.21 - 16:23
(120) я неправ :-(
но в общем случае это всё равно неправильно решение если дверей было бы больше,
просто совпадение что дверей мало
   Kassern
 
123 - 24.12.21 - 16:23
(122) попробуйте на 10 дверях, так же будет наглядно
   Kassern
 
124 - 24.12.21 - 16:25
(123) просто в экселе нарисуйте по числу в каждой ячейке 2345678998765432 и напротив попробуйте алгоритм для тигра придумать
   ManyakRus
 
125 - 24.12.21 - 16:26
правильно: обойти всё начиная с чётного, потом начиная с нечётного
неправильно: обойти всё начиная с чётного два раза
234+432 = обход два раза начиная с чётного числа
   Kassern
 
126 - 24.12.21 - 16:28
(125) вы видимо не поняли смысл, зачем в одной комнате охотник ждет. Это нужно, чтобы сменить "фазу" после прохода всех комнат, кроме крайних. Это дает 100% возможность поймать тигра.
   Kassern
 
127 - 24.12.21 - 16:31
(125) первым проходом мы 100% убеждаемся, что справа нет хищника. А раз мы его не встретили, значит наши фазы хода не совпали (мы на четных, тигр на нечетных к примеру), как только мы подождали ход, мы убедились, что он не в крайней точке и сменили фазу, теперь тигру некуда деваться
   Salimbek
 
128 - 24.12.21 - 16:32
(125) Вы не правы. Суть в том, что четность двери тигра каждый раз меняется. Поэтому начинаем с 2 и допредпоследней. Таким образом, если тигр был в четной двери в начале, то он будет гарантированно пойман. Если же тигр был в нечетной двери, то второй раз проходим этот же маршрут назад, и, таким образом, не оставляем тигру шансов.
(127) "первым проходом мы 100% убеждаемся, что справа нет хищника." - ложное утверждение. Первым проходом мы убеждаемся что в начале тигр не был в четной двери.
   Kassern
 
129 - 24.12.21 - 16:33
(128) первым проходом+повтором предпоследней двери)
   Salimbek
 
130 - 24.12.21 - 16:34
(129) Первым ходом тигр был правее в 3-й двери, и идет влево, поймаете его первым проходом?
 
 
   Kassern
 
131 - 24.12.21 - 16:34
(128) можете назвать случай, когда тигр будет правее охотника при первом проходе+ повторе предпоследней двери?
   Kassern
 
132 - 24.12.21 - 16:36
(130) а я разве утверждал, что поймаю, я лишь сказал, что его не будет правее
   ManyakRus
 
133 - 24.12.21 - 16:40
(128) мой ответ точно такой же как твой,
поэтому мы оба правы, и я не могу быть неправ.
Зато я первым написал алгоритм :-)
   Kassern
 
134 - 24.12.21 - 16:42
(133) "неправильно: обойти всё начиная с чётного два раза
234+432 = обход два раза начиная с чётного числа" вы утверждаете, что это не верно, но не привели ни 1 примера, когда это не работает
   Salimbek
 
135 - 24.12.21 - 16:42
(132) В таком случае некорректно высказывание "первым проходом мы 100% убеждаемся, что справа нет хищника.", т.к. в начале тигр может быть правее и первым проходом мы его не ловим.
Корректно высказывание "первым проходом мы 100% убеждаемся, что _в конце первого прохода_ справа нет хищника."
   ManyakRus
 
136 - 24.12.21 - 16:42
(126) наверно ты прав :-)
сменить фазу надо если всего количество дверей нечётное (=5)
   ManyakRus
 
137 - 24.12.21 - 16:44
(134) это не работает если количество дверей>5 и чётное
как и задано в задаче
т.е. ответ неправильный в общем случае
ответ случайно правильный для одного случая 5 дверей
   Kassern
 
138 - 24.12.21 - 16:46
(137) приведите пример для 6 дверей и алгоритма охотника 23455432, когда хищник его обходит
   Kassern
 
139 - 24.12.21 - 16:46
(137) я привел 5 дверей, так как это наглядно
   Kassern
 
140 - 24.12.21 - 16:48
не важно, четное или нет количество дверей, важно на каких клетках (четных или нет) находится тигр. Если совпадает с охотником, то ловится на первом проходе, если нет, то стояние на одной комнате меняет фазу и снова ловится зверь
   ManyakRus
 
141 - 24.12.21 - 16:50
(138)
2345+5432 - это ответ правильный
т.к. сначала с чётного потом с нечётного
неправильно - два раза с нечётного
   ManyakRus
 
142 - 24.12.21 - 16:51
(138)
2345+5432 - это ответ правильный
т.к. сначала с чётного потом с нечётного
неправильно - два раза с чётного
   Kassern
 
143 - 24.12.21 - 16:52
(142) окей, давайте для 7 дверей, тогда 2345665432 устроит?
   Kassern
 
144 - 24.12.21 - 16:52
еще раз показывает, что вы не уловили суть первого прохода и стояния в пердпоследней комнате)
   pechkin
 
145 - 24.12.21 - 16:54
(143) 7 - 2 раза должна быть
   Kassern
 
146 - 24.12.21 - 16:55
(145) зачем? Напишите алгоритм тигра, который это обойдет
   ManyakRus
 
147 - 24.12.21 - 16:56
(140) всё правильно мыслишь, везде прав :-)
только решать надо для общего случая сколько угодно дверей, или 32 дверей
   Kassern
 
148 - 24.12.21 - 16:59
(147) на небольших примерах просто наглядней, каждый может сам попробовать полосатого спасти)
   Ненавижу 1С
 
149 - 24.12.21 - 17:20
(71) и (80) смотри
   Ведущий
 
150 - 25.12.21 - 07:52
(9) Действительно, со скобками нужно было. Короче, за 60 открываний.
   Ведущий
 
151 - 25.12.21 - 07:54
2 * N - 4 или 2 * (N - 2)
   HawkEye
 
152 - 25.12.21 - 23:24
(147) формула для общего случая дана еще в (3) правда без скобок...
  1  2

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