Читать книгу Основы программирования с Java - Тимур Машнин - Страница 8

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

Как и в игре крестики-нолики, задача здесь начинается с матрицы 3х3, но в этой задаче, клетки занимают квадратные яблоки.

Давайте назовем это задачей квадратных яблок.

Люди на самом деле могут вырастить квадратные яблоки или даже квадратные арбузы.

Предположим, что в исходном состоянии этой задачи существует червь в средней ячейке.

Вопрос в том, может ли червь съесть все яблоки, выполнив следующие два правила.

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

То есть, червь может двигаться только в ячейку, где есть еще несъеденное яблоко внутри.

Рисунок показывает, что червь начинает с середины. После того, как заканчивается среднее яблоко, он может двигаться в одну из четырех клеток на стороне, но не в углу. Таким образом, червь может двигаться вправо, двигаться вниз, двигаться влево и двигаться вверх.

Я хочу, чтобы вы подумали, есть ли решение этой задачи.

То есть, может ли червь съесть все 9 яблок.

Это должно быть совершенно очевидно.

Здесь часть пространства состояний графа и это возможный путь, который может привести к решению.

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

Можно написать программу Java, которая была бы создана для решения этой задачи.

И после прочтения этой книги, вы должны быть в состоянии написать собственную программу для решения таких задач, как эта.

Это демо-программа, которая была написана для вас, чтобы проиллюстрировать решение задачи квадратного яблока.

Задача будет начинаться с червем в середине. Червь настигает яблоко, перемещаясь в другую ячейку.

Отображая условие – не посещать клетки, которые были захвачены ранее, цифры показывают последовательность шагов.

Программа также отображает последовательность шагов в другом окне.

Таким образом, вы можете видеть, что есть в общей сложности 8 решений, как обсуждалось ранее.

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

То есть, есть в общей сложности, есть 27 яблок. Чтобы помочь вам визуализировать проблему, диаграмма здесь отображает куб в три слоя.

Подобно тому, что у нас было раньше, червь прячется в середине, и мы должны следовать тем же правилам.

То есть, в начале, есть 6 возможных ходов, вместо 4, как в случае 2D, потому что в дополнение к 4 ячейкам на сторонах в среднем слое, червь также может перейти к средней ячейке на переднем плане и средней ячейке на заднем плане.

И теперь вопрос в том, может ли червь по-прежнему съесть все 27 яблок.

Помните, что червь не может вернуться к любым тем ячейкам, которые были захвачены ранее.

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

Если червь опять должен начать с середины, следуя тем же правилам, это та же задача, как и раньше, независимо от цвета яблок, и у нас есть те же 8 решений, как и в предыдущем случае 2D.

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

Подсказка в том, что надо посмотреть, как меняется цвет, когда червь переходит из одного яблока в другое.

Давайте теперь вернемся к задаче квадратных яблок 3D и будем чередовать цвета яблок, как мы сделали это в 2D случае.

Как и в предыдущем 3D случае червь прячется в середине.

Так что это все та же 3D задача, как и раньше, хотя цвета некоторых из яблок были изменены.

Теперь используйте то, что вы наблюдали в случае 2D, и попытайтесь придумать быстрое решение этой задачи.