Морской бой.
Какое минимальное кол-во выстрелов нужно сделать по классическому полю 10 на 10 клеток, чтобы сто процентов попасть в 4-х клеточный корабль (не убить, а только ранить) (при возможности изобразить)?
↓↓ 0 ↑↑
Enclave (3 / 140) 2008-03-31 18:01 »»
Уточню. Он единственный на поле, других кораблей нет.
Неужели у этой задачи есть красивое решение?..
не знаю, как насчёт красивого решения, я методом логики и проверки получил 24 выстрела.
нашёл способ 22 выстрела.
Решение -- это не просто найти ответ, но и доказать, что этот ответ -- правильный. В данном случае, доказать, что это количество является наименьшим.
Я об этом думал. Довольно сложно но возможно. К сожалению за пределами моих знаний:). Догадываюсь примерно как это сделать, но не могу сообразить...
Ответ 24
Доказательство. Введем координаты клеток числами от 1 до 10 и по вертикали и по горизонтали и отметим все клетки с суммой координат с остатком 1 при делении на 4. Тогда будут отмечены 4 клетки с суммой 5, 8 клеток с суммой 9, 8 клеток с суммой 13, 4 клетки с суммой 17. Итого 24. Очевидно, при любом положении кораблика он одну из этих клеток занимает.
С другой стороны, можно поставить 24 непересекающихся кораблика. Для их поражения необходимы 24 выстрела. Ставить так - два прямоугольника 4*10 (по 10 кораблей) и прямоугольник 2*8 (еще 4)
Интересно, какой же способ нашёл Enclave для 22 выстрелов? :-)
Можно, конечно, попридираться...
сказать, что в условии четко не оговорена форма корабля. Т. е., в принципе, он может быть и квадратным. Тогда 24 выстрела - мало, надо 25.
но и так 24, по-моему, маловато...
самый раз 25
http://battle-ships.narod.ru
24-ёх точно хватает. Насчёт 22 надо уточнить, может я считать не умею просто после 20.
Zero
Из-за того, что кто-то на сайте расположил дргую версию, это не значит, что она правильная. Я вообще например видел обстрел из 36 выстрелов где автор утверждал, что это самая самая быстрая обстрелка.
|
