Все наверное хоть раз играли в эту занимательную игру. Для тех, кто не играл вкратце расскажу правила:
Поле 10 на 10, в битве участвует линейные корабли N*1 прямоугольники, всего при N=1 - 4 корабля, при N=2 - три корабля, при N=3 два корабля, при N=4 - один корабль, то есть всего 10 кораблей. Производятся выстрелы - по 1 клетке за выстрел, возможные ситуации: ранил, убил, промах. Корабли расположены изолировано по полю, то есть не соприкасаются ни сторонами, ни углами. Вопросы такие:
1) За какое наименьшее число выстрелов гарантированно убивается четырехпалубник, если он один на поле?
2)За какое наименьшее число выстрелов гарантированно убивается четырехпалубник, если на поле целая эскадра?
House Fox
Гений-Говорун
 Offline
Сообщений: 2005
СПАСИБО
-вы поблагодарили: 26
-вас поблагодарили: 125
"Everybody lies"
|
 |
� Ответ #15 : Апрель 17, 2010, 11:39:15 � |
|
Ну не знаю, в чем различие, но навреное снова 29. (до этого что-то не то написал)
|
|
|
|
|
Записан
|
Не всегда то, что нелогично глупо, а то что логично верно.
|
|
|
House Fox
Гений-Говорун
Offline
Сообщений: 2005
СПАСИБО
-вы поблагодарили: 26
-вас поблагодарили: 125
"Everybody lies"
|
|
� Ответ #16 : Апрель 17, 2010, 11:41:17 � |
|
Объясняю : Ну четырехпалубник все равно один на поле будет, т.е. он может не измениться и столько же ходов потребуется для его убития.
|
|
|
|
|
Записан
|
Не всегда то, что нелогично глупо, а то что логично верно.
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #17 : Апрель 17, 2010, 11:42:58 � |
|
23 в том случае, если мы каждый раз будем попадать в корабли (не 4х палубный), а это 16 выстрелов + оставшиеся клеточки простреливаем - 23
|
|
|
|
|
Записан
|
Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #18 : Апрель 17, 2010, 11:43:45 � |
|
Объясняю : Ну четырехпалубник все равно один на поле будет, т.е. он может не измениться и столько же ходов потребуется для его убития.
А как определить какой из них 4х палубный ? |
|
|
|
|
Записан
|
Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
|
|
|
General
Умник
Offline
Сообщений: 681
СПАСИБО
-вы поблагодарили: 47
-вас поблагодарили: 164
|
|
� Ответ #19 : Апрель 17, 2010, 11:44:18 � |
|
House Fox, Дело в том, что когда на поле есть другие корабли, попадание не гарантирует, что попали именно в четырёхпалубник. Интересная задача.
|
|
|
|
|
Записан
|
|
|
|
House Fox
Гений-Говорун
Offline
Сообщений: 2005
СПАСИБО
-вы поблагодарили: 26
-вас поблагодарили: 125
"Everybody lies"
|
|
� Ответ #20 : Апрель 17, 2010, 11:44:57 � |
|
23 в том случае, если мы каждый раз будем попадать в корабли (не 4х палубный), а это 16 выстрелов + оставшиеся клеточки простреливаем - 23
Ну если мы убиваем один корабль, то вокруг него все клетки резко "закрываются", т.е. в них можно не стрелять. Ну т.е. первый мой вариант тоже подходит(т.е. 9 выстрелов) |
|
|
|
|
Записан
|
Не всегда то, что нелогично глупо, а то что логично верно.
|
|
|
House Fox
Гений-Говорун
Offline
Сообщений: 2005
СПАСИБО
-вы поблагодарили: 26
-вас поблагодарили: 125
"Everybody lies"
|
|
� Ответ #21 : Апрель 17, 2010, 11:45:41 � |
|
Ребят, я запутался  |
|
|
|
|
Записан
|
Не всегда то, что нелогично глупо, а то что логично верно.
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #22 : Апрель 17, 2010, 11:49:32 � |
|
Ребят, я запутался Главное не торопится.  |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #23 : Апрель 17, 2010, 11:50:31 � |
|
 20 с 100% удачей ) |
|
|
|
|
Записан
|
Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #24 : Апрель 17, 2010, 12:24:32 � |
|
А если удача отвернулась от нас?
Можно попробовать посчитать сколько потребуется выстрелов для убиения 4-ка, если по пути нам пришлось еще убить два трех палубника и 3 двухпалубника.
|
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
kinder
Свой человек
Offline
Сообщений: 298
СПАСИБО
-вы поблагодарили: 10
-вас поблагодарили: 35
|
|
� Ответ #25 : Апрель 18, 2010, 03:17:23 � |
|
2) 56 выстрелов, так у меня получилось в самом худшем случае. Алгоритм таков - как и в первой задаче проходим по диагоналям, при нахождении корабля обстреливаем его, для этого достаточно трёх выстрелов для однопалубного, 4х для двух, 5ти для трёх и 5ти для четырёхпалубного. Кроме двух особых точек в центре где требуется на один выстрел больше (и есть возможность там расположить два корабля). Очевидно максимальное количество выстрелов потребуется когда все корабли лежат на этих диагоналях. Клеток на диагоналях 24. Итого: 24+(3-1)*4+(4-1)*3+(5-1)*2+5+(2)=56
|
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #26 : Апрель 18, 2010, 15:18:26 � |
|
Зачем обстреливать корабли, если по условию сказано, что они не соприкасаются друг с другом: убил одно палубный автоматически клетки вокруг него отсекаются - там уже не может быть другого корабля.
|
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
kinder
Свой человек
Offline
Сообщений: 298
СПАСИБО
-вы поблагодарили: 10
-вас поблагодарили: 35
|
|
� Ответ #27 : Апрель 18, 2010, 18:33:11 � |
|
Илья, точно давно я не играл в морской бой  сейчас пересчитаю, нашел еще другой способ |
|
|
|
|
Записан
|
|
|
|
kinder
Свой человек
Offline
Сообщений: 298
СПАСИБО
-вы поблагодарили: 10
-вас поблагодарили: 35
|
|
� Ответ #28 : Апрель 18, 2010, 19:16:06 � |
|
2) мой ответ 43 выстрела
очевидно, однопалубные не должны быть на диагоналях, в остальном также, получается:
24+(3-1)*3+(4-1)*2+5+2=43
в моём случае независимо от стратегии всегда существует способ расставить корабли так, чтобы выстрелов потребовалось не менее 43.
|
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #29 : Апрель 19, 2010, 10:47:40 � |
|
А у меня поначалу получалось 46.
|
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
|
