Над решением работали:
- Гребенникова Дарья
- Манеев Дмитрий
- Тарасов Михаил
Условие задачи "Морской баттл"
Какое минимальное число выстрелов необходимо, чтобы на шахматной доске 8х8 обнаружить корабль 2х3?
Решение:
Рассмотрим полоску 2*8:
Рассмотрим полоску 3*8
Рассмотрим полоску 4*8. Заметим, что для нее кол-во выстрелов не поменяется
Для полоски 5*8 появится еще 2 выстрела аналогично 2 строчке
Для полоски 6*8:
Заметим, что выстраивется следующий рисунок. Необходимо. чтобы между выстрелами был зигзаг:
То есть для полоски 3*8 имеем следующий рисунок:
Тогда для поля 8*8 получим следующее:
Такой рисунок выстрелов будет работать и для поля n*m:
Способ решения 2: выстрелы по углам
Для определения корабля на поле 4*4 необзодимо 2 выстрела. Разобьем поле 8*8 на 4 таких поля:
Остался центр, в котором мы не можем обнаружить корабль. Предлагаем следующее решение обнаружения корабля в центре. Оно тоже представляет из себя поле 4*4:
