Question

Мистер Фокс играет в морской бой на доске 13 на 13 с Мистером Фордом. Мистер Форд поставил на свою доску только один 7-палубный корабль. За какое наименьшее количество выстрелов Мистер Фокс сможет гарантированно ранить этот 7-палубный корабль Мистера Форда?

Answer 1

Ответ:

24

Пошаговое объяснение:

Для того что бы оптимально проверить все возможные расположения коробля, нужно оптимальным образом протестировать корабль по вертикали и горизонтали. Для 7ми палубного корабля это горизонталь и вертикаль кратная 7ми от начала поля. Но так как наше поле 13х13, то 7мая клетка от начала делит поле пополам, поэтому достаточно по горизонтали можно прострелить 13 клеток и по вертикали. Однако средняя точка с индексом (7;7) общая для вертикальной линии и горизонтальной и её не имеет смысла простреливать так как данная горизонталь и вертикаль и так простреливается полностью, поэтому количество оптимальных точек:

13+13-2=24

Answer 2

Для нахождения наименьшего количества выстрелов, гарантирующих попадание в 7-палубный корабль Мистера Форда, мы должны определить оптимальную стратегию атаки. В этой задаче мы можем использовать стратегию деления доски на секторы.

Доска 13 на 13 может быть разделена на 4 сектора, по 2 сектора по горизонтали и вертикали. Для гарантированного ранения 7-палубного корабля нам необходимо попасть в каждый из этих секторов хотя бы один раз.

Используем стратегию:

1. Выстрел в середину первого сектора (6x6).
2. Выстрел в середину второго сектора (6x7).
3. Выстрел в середину третьего сектора (7x6).
4. Выстрел в середину четвёртого сектора (7x7).

Следуя этой стратегии, Мистер Фокс сможет гарантированно ранить 7-палубный корабль Мистера Форда своими выстрелами в наименьшем количестве ходов.