Страниц: 1 [2] 3 4 ... 8
  Печать  
Автор Тема: Выживет ли мышь?  (Прочитано 31645 раз)
0 Пользователей и 1 Гость смотрят эту тему.

Есть N картонных коробок, стоящих вплотную друг к другу в один ряд. В одной из них сидела мышь и прогрызла себе ходы из каждой коробки в соседние. Из крайних коробок прохода наружу она не прогрызла.
Охотнику дали ружье и неограниченное количество патронов, чтобы убить мышь при следующих условиях:
1) изначально охотник не знает, в какой коробке сидит мышь.
2) если охотник выстрелил в коробку, где сидит мышь, то мышь считается убитой
3) если охотник выстрелил в коробку, где нет мыши, то после выстрела мышь обязательно переходит в любую коробку соседнюю к той, в которой она сидела в момент выстрела. И сидит там пока не грянет следующий выстрел.
Сможет ли охотник гарантированно застрелить мышь? Если да, то за какое наименьшее количество выстрелов?
?
Свой человек
***
Offline Offline

Сообщений: 288

СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41


584276839
Просмотр профиля Email
Ответ #15 : Март 25, 2010, 16:41:26 �

2n-1 получается вроде.

Эти пользователи сказали вам СПАСИБО :

Илья

За это сообщение 1 пользователь сказал спасибо!
Записан
sek140675
Гений-Говорун
*
Offline Offline

Сообщений: 1861

СПАСИБО
-вы поблагодарили: 283
-вас поблагодарили: 108



Просмотр профиля Email
Ответ #16 : Март 25, 2010, 16:42:49 �

 Крутой
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #17 : Март 25, 2010, 16:46:14 �

стрелки а размер коробки вам и нафиг не нужен??
Задачка на поиск алгоритма.

Бедная-бедная мышка. Cry
Думал, что дольше проживет, но с Ikob ом шутки плохи. Smiley
Да, мышки меня боятся!
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #18 : Март 25, 2010, 16:48:39 �

2n-1 получается вроде.
Точно, обсчитался.
?, спасибо за сыкономленный патрон. Пиво
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
?
Свой человек
***
Offline Offline

Сообщений: 288

СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41


584276839
Просмотр профиля Email
Ответ #19 : Март 25, 2010, 16:51:19 �

Сэкономленный патрон уйдет на погрешность стрелка, один из 200 патронов вполне можно промахнуться.  Пиво
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #20 : Март 25, 2010, 17:43:54 �

После каждого выстрела мышка либо убивается, либо меняет чётность норки (с четной на нечётную или наоборот).
Допустим, мы знаем чётность норки мышки в начальный момент.
Тогда за N (или N-1) ходов мы её убьём, начиная последовательно стрелять с минимального соответствующего номера.
Это и есть стратегия.
1. Предполагаем, что сначала мышка в чётной норке. Тратим N-1 ходов максимум, чтобы дойти до конца. Если мышка осталась жива, мы ошиблись чётностью.
2. В этом случае мы снова начинаем сначала, но чётность нам заведомо известна.
Вот, собственно и всё.
Осталось оценить кол-во патронов для худшего случая.
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)

Эти пользователи сказали вам СПАСИБО :

Илья

За это сообщение 1 пользователь сказал спасибо!
Записан
?
Свой человек
***
Offline Offline

Сообщений: 288

СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41


584276839
Просмотр профиля Email
Ответ #21 : Март 25, 2010, 17:55:41 �

buka, все правильно.  Крутой
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #22 : Март 25, 2010, 17:56:31 �

Да, buka, все верно. Спасибо за подробное решение. Пиво
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Redirect
Гений-Говорун
*
Offline Offline

Сообщений: 1472

СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214


Is it cocktail hour yet?

497367901
Просмотр профиля
Ответ #23 : Март 25, 2010, 18:44:55 �

А он не может подойти сбоку к коробкам и выстрелить пару раз ?)))
Записан

Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
sek140675
Гений-Говорун
*
Offline Offline

Сообщений: 1861

СПАСИБО
-вы поблагодарили: 283
-вас поблагодарили: 108



Просмотр профиля Email
Ответ #24 : Март 25, 2010, 18:52:13 �

А он не может подойти сбоку к коробкам и выстрелить пару раз ?)))

тогда мышка обкакается

Эти пользователи сказали вам СПАСИБО :

Илья

За это сообщение 1 пользователь сказал спасибо!
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #25 : Март 25, 2010, 19:29:44 �

Цитировать
тогда мышка обкакается
Да, а это уже противоречит условию задачи.
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Redirect
Гений-Говорун
*
Offline Offline

Сообщений: 1472

СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214


Is it cocktail hour yet?

497367901
Просмотр профиля
Ответ #26 : Март 25, 2010, 19:30:40 �

А у нас храбрая мышка Smiley
Записан

Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
Smith
Из мудрейших мудрейший
**
Offline 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 (для начала) Wink
Последнее редактирование: Март 25, 2010, 20:11:51 от Smith Записан
?
Свой человек
***
Offline Offline

Сообщений: 288

СПАСИБО
-вы поблагодарили: 39
-вас поблагодарили: 41


584276839
Просмотр профиля Email
Ответ #28 : Март 25, 2010, 20:48:23 �

Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3.
2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ...
N-1 (для начала) Wink
А при Н = 1 или 2 выстрелов Н потребуется
Записан
Smith
Из мудрейших мудрейший
**
Offline 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 (для начала) Wink
А при Н = 1 или 2 выстрелов Н потребуется
так это у кого какая стратегия...
Записан
Страниц: 1 [2] 3 4 ... 8
  Печать  
 
Перейти в: