Есть N картонных коробок, стоящих вплотную друг к другу в один ряд. В одной из них сидела мышь и прогрызла себе ходы из каждой коробки в соседние. Из крайних коробок прохода наружу она не прогрызла.
Охотнику дали ружье и неограниченное количество патронов, чтобы убить мышь при следующих условиях:
1) изначально охотник не знает, в какой коробке сидит мышь.
2) если охотник выстрелил в коробку, где сидит мышь, то мышь считается убитой
3) если охотник выстрелил в коробку, где нет мыши, то после выстрела мышь обязательно переходит в любую коробку соседнюю к той, в которой она сидела в момент выстрела. И сидит там пока не грянет следующий выстрел.
Сможет ли охотник гарантированно застрелить мышь? Если да, то за какое наименьшее количество выстрелов?
?
Свой человек
Offline
Сообщений: 288
СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41
|
|
� Ответ #15 : Март 25, 2010, 16:41:26 � |
|
2n-1 получается вроде.
|
|
|
|
sek140675
Гений-Говорун
Offline
Сообщений: 1861
СПАСИБО
-вы поблагодарили: 283
-вас поблагодарили: 108
|
|
� Ответ #16 : Март 25, 2010, 16:42:49 � |
|
|
|
|
Записан
|
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #17 : Март 25, 2010, 16:46:14 � |
|
стрелки а размер коробки вам и нафиг не нужен??
Задачка на поиск алгоритма. Бедная-бедная мышка. Думал, что дольше проживет, но с Ikob ом шутки плохи. Да, мышки меня боятся!
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #18 : Март 25, 2010, 16:48:39 � |
|
2n-1 получается вроде.
Точно, обсчитался. ?, спасибо за сыкономленный патрон.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
?
Свой человек
Offline
Сообщений: 288
СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41
|
|
� Ответ #19 : Март 25, 2010, 16:51:19 � |
|
Сэкономленный патрон уйдет на погрешность стрелка, один из 200 патронов вполне можно промахнуться.
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #20 : Март 25, 2010, 17:43:54 � |
|
После каждого выстрела мышка либо убивается, либо меняет чётность норки (с четной на нечётную или наоборот). Допустим, мы знаем чётность норки мышки в начальный момент. Тогда за N (или N-1) ходов мы её убьём, начиная последовательно стрелять с минимального соответствующего номера. Это и есть стратегия. 1. Предполагаем, что сначала мышка в чётной норке. Тратим N-1 ходов максимум, чтобы дойти до конца. Если мышка осталась жива, мы ошиблись чётностью. 2. В этом случае мы снова начинаем сначала, но чётность нам заведомо известна. Вот, собственно и всё. Осталось оценить кол-во патронов для худшего случая. Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
|
|
|
|
?
Свой человек
Offline
Сообщений: 288
СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41
|
|
� Ответ #21 : Март 25, 2010, 17:55:41 � |
|
buka, все правильно.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #22 : Март 25, 2010, 17:56:31 � |
|
Да, buka, все верно. Спасибо за подробное решение.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #23 : Март 25, 2010, 18:44:55 � |
|
А он не может подойти сбоку к коробкам и выстрелить пару раз ?)))
|
|
|
Записан
|
Когда деревья были большими, Папа - самый сильный, мама - самая красивая, Я верил этим книгам, фильмам, И думал никогда курить не буду, даже с фильтром. Не буду пить, чтоб не расстраивать мать Буду учиться на пять, чтобы всё узнать.
|
|
|
sek140675
Гений-Говорун
Offline
Сообщений: 1861
СПАСИБО
-вы поблагодарили: 283
-вас поблагодарили: 108
|
|
� Ответ #24 : Март 25, 2010, 18:52:13 � |
|
А он не может подойти сбоку к коробкам и выстрелить пару раз ?)))
тогда мышка обкакается
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #25 : Март 25, 2010, 19:29:44 � |
|
тогда мышка обкакается Да, а это уже противоречит условию задачи.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #26 : Март 25, 2010, 19:30:40 � |
|
А у нас храбрая мышка
|
|
|
Записан
|
Когда деревья были большими, Папа - самый сильный, мама - самая красивая, Я верил этим книгам, фильмам, И думал никогда курить не буду, даже с фильтром. Не буду пить, чтоб не расстраивать мать Буду учиться на пять, чтобы всё узнать.
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305
PeAcE
|
|
� Ответ #27 : Март 25, 2010, 20:07:27 � |
|
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3. 2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ... N-1 (для начала)
|
|
� Последнее редактирование: Март 25, 2010, 20:11:51 от Smith �
|
Записан
|
|
|
|
?
Свой человек
Offline
Сообщений: 288
СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41
|
|
� Ответ #28 : Март 25, 2010, 20:48:23 � |
|
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3. 2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ... N-1 (для начала) А при Н = 1 или 2 выстрелов Н потребуется
|
|
|
Записан
|
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305
PeAcE
|
|
� Ответ #29 : Март 25, 2010, 21:27:05 � |
|
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3. 2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ... N-1 (для начала) А при Н = 1 или 2 выстрелов Н потребуется так это у кого какая стратегия...
|
|
|
Записан
|
|
|
|
|