Вычислительное мышление: Метод решения сложных задач | страница 102

информация будет такой: 0 в строке A (потому что там 0 + 0 + 0 + 0, хотя вам скажут только про 0 в сумме), 1 в строке B (потому что там 0 + 1 + 0 + 0) и 0 в строке С. Это начало. Теперь вы знаете, что корабль находится в строке B, но не знаете, где именно. Теперь спросите, какая сумма получается в каждом столбце. В столбце 1 выходит 0, в столбце 2 — 1, в столбце 3 — 0 и в столбце 4 — 0. Теперь вы знаете, что корабль находится в столбце 2. Это показано на рис. 70, где подсказки расположены в кружочках по краям игрового поля. Обобщив эту информацию, вы поймете, что корабль находится в клетке В2, и — БАБАХ! — он потоплен!

Теперь представьте, что где-то в сетке располагаются два эсминца. На этот раз мы не скажем, где они. Ваш друг снова сообщает вам сумму значений в каждой строке и столбце. На этот раз вы узнаете, что у вас есть 2 в строке А, 0 в строке В и 0 в строке C; 1 в столбце 1, 0 в столбце 2, 1 в столбце 3 и 0 в столбце 4, как на рис. 71a. Где же корабли?

Вот общий подход к поиску кораблей. Во-первых, нам сказали, что в строке А сумма равна 2. Значит, там что-то есть! Мы можем распространить информацию о присутствии чего-то на всю строку А до самого конца. Хотя мы распределили данные по всей строке, мы все еще не знаем, где находится «что-то», а просто уверены, что оно где-то там есть. Давайте продолжать. Теперь распределим данные по строкам В и С. Здесь нет дополнительной информации, потому что в каждой строке стоит по нолю. В результате получается сетка как на рис. 71.

Мы знаем, что в строке А что-то есть, это здесь и показано. Но пока мы не знаем, что же это такое. Теперь мы смотрим на столбцы и создаем новую сетку. Если так же распределить информацию по столбцам, где в столбце 1 будет 1, в столбце 2 — 0, в столбце 3 — 1 и в столбце 4 — 0, то получится сетка как на рис. 72.

Мы знаем, что в столбцах 1 и 3 что-то есть, но не знаем, где именно. Чтобы окончательно решить эту задачу и восстановить расположение кораблей, мы просто складываем эти сетки с распределенной информацией вместе и получаем сетку как на рис. 72.

В объединенной сетке, например, A1 = 2 + 1 = 3, A2 = 2 + 0 = 2, A3 = 2 + 1 = 3 и так далее. Если теперь посмотреть на эту объединенную сетку с двумя наборами распределенных данных, то мы увидим на ней два пиковых значения 3 на позициях A1 и A3. Эти пиковые значения и отмечают, где находятся корабли. Итак, у нас есть автоматический детектор кораблей, но, что еще важнее, есть и способ открыть истинное расположение кораблей на сетке. Мы можем восстановить, как выглядит наш пруд, по одним подсказкам — см. рис. 73. Чтобы этого добиться, нужно использовать результаты, которые получаются при сложении всех данных в строке и в столбце. Теперь пришло время сняться с якоря и вернуться к рентгеновским лучам. Как вы, вероятно, догадались, все это время мы занимались задачей, связанной именно с ними.