Форум умных людей

Все наверное  хоть раз играли в эту занимательную игру. Для тех, кто не играл вкратце расскажу правила:
Поле 10 на 10, в битве участвует линейные корабли N*1 прямоугольники, всего при N=1 - 4 корабля, при N=2 - три корабля, при N=3 два корабля, при N=4 - один корабль, то есть всего 10 кораблей. Производятся выстрелы - по 1 клетке за выстрел, возможные ситуации: ранил, убил, промах. Корабли расположены изолировано по полю, то есть не соприкасаются ни сторонами, ни углами. Вопросы такие:
1) За какое наименьшее число выстрелов гарантированно убивается четырехпалубник, если он один на поле?
2)За какое наименьшее число выстрелов   гарантированно убивается четырехпалубник, если на поле целая эскадра?

Ответ и на первый и на второй вопрос : за 100 выстрелов. :)

Правильно.
Да, забыл добавить самую малость: за какое наименьшее количество выстрелов. :)

 :)Ну я так и понял, но решил не упускать момент и ответить. ;)

На Хабре, кстати, была хорошая статья про морской бой (http://habrahabr.ru/blogs/games/82221/)

37

Нет.

29

Вот я сейчас считаю :
29

Вот это верно.  :good2:
А как быть со вторым вопросом?

2)23 !!!!

Ну 9 хватит по-моему.

Даже 21

Господа, надо остановится на одном варианте. Рассматриваем самый "худший" для нас случай.
По секрету: Показать скрытый текст

Ну не знаю, в чем различие, но навреное снова 29. (до этого что-то не то написал)

Объясняю : Ну четырехпалубник все равно один на поле будет, т.е. он может не измениться и столько же ходов потребуется для его убития.

23 в том случае, если мы каждый раз будем попадать в корабли (не 4х палубный), а это 16 выстрелов + оставшиеся клеточки простреливаем - 23

А как определить какой из них 4х палубный ?

House Fox, Дело в том, что когда на поле есть другие корабли, попадание не гарантирует, что попали именно в четырёхпалубник. Интересная задача.

Ну если мы убиваем один корабль, то вокруг него все клетки резко "закрываются", т.е. в них можно не стрелять. Ну т.е. первый мой вариант тоже подходит(т.е. 9 выстрелов)

Ребят, я запутался :laugh:

Главное не торопится. :beer:

(http://s52.radikal.ru/i138/1004/a0/ed180000295b.png)

20 с 100% удачей )

А если удача отвернулась от нас?
Можно попробовать посчитать сколько потребуется выстрелов для убиения 4-ка, если по пути нам пришлось еще убить два трех палубника и 3 двухпалубника.

2) 56 выстрелов, так у меня получилось в самом худшем случае. Алгоритм таков - как и в первой задаче проходим по диагоналям, при нахождении корабля обстреливаем его, для этого достаточно трёх выстрелов для однопалубного, 4х для двух, 5ти для трёх и 5ти для четырёхпалубного. Кроме двух особых точек в центре где требуется на один выстрел больше (и есть возможность там расположить два корабля). Очевидно максимальное количество выстрелов потребуется когда все корабли лежат на этих диагоналях. Клеток на диагоналях 24. Итого: 24+(3-1)*4+(4-1)*3+(5-1)*2+5+(2)=56

Зачем обстреливать корабли, если по условию сказано, что они не соприкасаются друг с другом: убил одно палубный автоматически клетки вокруг него отсекаются - там уже не может быть другого корабля.

Илья, точно
давно я не играл в морской бой :)
сейчас пересчитаю, нашел еще другой способ

2) мой ответ 43 выстрела
очевидно, однопалубные не должны быть на диагоналях, в остальном также, получается:
24+(3-1)*3+(4-1)*2+5+2=43
в моём случае независимо от стратегии всегда существует способ расставить корабли так, чтобы выстрелов потребовалось не менее 43.

А у меня поначалу получалось 46.

ответы на оба вопроса = 24. выстрела

чтобы 100% поразить четурехпалубник при минуме выстрелов, необходимо каждую строку и акждый столбец простреливать по принципу "3 пустых.. выстрел..3 пустых.. выстрел"

т.к. 4 палубник, то 4 позиции с которых можем начинать их отстрел.

на картинке сверху - один из вариантов прострела всего поля

на картинкеснизу - 4 варианта в рез-те которых получается в сумме 24,25,25,26 выстрелов.
лучший 24.

если стоят ВСЕ корабли, то это не меняет ответа, т.к. наихудший вариант - мы не попадем ни в какой корабль кроме 4 палубника.

(http://s61.radikal.ru/i174/1004/00/aa70bd9b941e.jpg)

Наихудший вариант, если мы попадем во все трехпалубные и во все двухпалубные и нам придется их проверять на наличие 4-ой палубы.

Илья предоставьте вариант эскадры, для которой требуется более 43 выстрелов

Кстати, я хоть и подтвердил, что 29 - это правильный ответ на первый вопрос, щас проверил и меньше чем за 30 выстрелов не получаеся. Так что надо еще разобраться с первым вопросом, то есть предоставить решение в 29 выстрелов, при котором 4-х палубник гарантированно убивается, а потом уже двигаться дальше.

и правда 29 на 1 вопрос.
(http://s45.radikal.ru/i109/1004/63/d7eabef745c1.jpg)

второй вопрос и правда поперебористее

касяк. корабль у кромки стоит.. если в другмо месте - то 30 надо =/

:beer:

ааа, неет, косяка нету. последний выстрел СПЕЦИАЛЬНО должен производиться у стенки - иначе мы бы корабль уже зацепили ДО этого и в цифру 29 уложились (т.к. в запасе как минимум 1 выстрел был бы)!! все нормуль ))

а уже дошел до того, что требуется всего 28 выстрелов!!

алгоритм базировался на прошлых картинках+мысль загнать корабль в угол (который отбросит парочку вариантов автоматом) затем прострелять все у кромки.  результат на картинке.

(http://i080.radikal.ru/1004/33/eb21648353fb.jpg)

нумерация стрельбы приобрела стратегическое значение ))

на счет второго вопроса - получил с допущениями число 45.. которое на практике всегда меньше , но высчитать его точно - вообще нереально
альтернатива - написать программку которая переберет все сочетании на основании предыдущих картинок
24*22*20*18*16*14 == 42,5 млн вариантов для перебора всех возможных значений. ээм бумажки с ручкой точно не хватит

ну что, будут варианты эскадр для более чем 43 выстрелов ? :)
число точное