Страница 6 из 17
Для исторической справки. Термин отладки (debugging) используется, потому что первая известная компьютерная ошибка была найдена в 1947 году, когда мотылек (насекомое – bug) был пойман в ловушку в реле компьютера.
Насекомое было записано на пленку в журнале учета Грейс Хоппер и в настоящее время хранится в Смитсоновском музее.
Для сложных проблем, важно протестировать программу в рамках различных сценариев, так как программа, которая работала в одном случае, не означает, что она будет работать для всех случаев.
И полезно придумать план тестирования, чтобы охватить набор общих случаев, которые можно было бы ожидать при работе программы.
Тесты могут привести к двум распространенным типам ошибок, а именно синтаксической ошибки или семантической ошибки.
Также важно документировать и поддерживать программу, особенно для программ, жизнь которых, как ожидается, продлится в течение длительного времени, и для повторного использования, и программ, которые могут быть пересмотрены или изменены другими пользователями.
Игра
Прежде чем погрузиться в программирование, давайте более внимательно посмотрим на важность постановки задачи и представление процесса путем изучения обычно используемого подхода к решению задачи под названием представление пространства состояний.
В представлении пространства состояний, задача представляется в виде множества состояний.
И я буду использовать примеры для иллюстрации того, что я имею в виду под состояниями.
Пространство состояний, это множество всех возможных состояний, в которых задача может находиться.
В частности, есть множество начальных состояний, то есть там, где начинается задача, и набор конечных состояний, в том числе всех возможных решений задачи.
Два состояния связаны, если существует действительная операция, которая может превратить одно состояние в другое.
Давайте рассмотрим несколько примеров, чтобы получить более полное понимание представления пространства состояний.
Это простой пример, и задача заключается в том, чтобы включить смартфон.
Здесь есть два состояния "сон" и "работа" и они соединены операцией нажатия на кнопку питания.
Первоначально, смартфон находится в «спящем» состоянии.
Для перехода к состоянию "работать", пользователь нажимает на кнопку питания.
И смартфон переключается из состояния "сна" в состояние "работать".
Пользователь может переключиться на «спящее» состояние смартфона снова, нажав на кнопку питания.
В этом примере, вероятно, нельзя сказать много о полезности представления пространства состояний.
Давайте теперь рассмотрим более интересный пример – игру крестики-нолики.
В этой игре, два игрока ставят "крестик" или "кружок" в таблице 3x3.
И тот, кто получает 3 крестика или нолика в ряд первым либо горизонтально, либо вертикально, либо по диагонали будет победителем.
Здесь показывается, как два компьютера играют в крестики-нолики друг с другом.
Поскольку компьютеры не делают ошибок, мы можем написать программу, чтобы гарантировать, что они не проиграют в этой игре.
Это своего рода задача, изучаемая в области искусственного интеллекта.
На этой диаграмме видно, что игра начинается с пустой сетки 3x3, мы назовем это начальным состоянием.
Пусть игрок, который ставит крестик, начнет первым.
Есть 9 возможных мест, где 1-й игрок может разместить крестик, но из-за симметрии, график показывает только три варианта, в том числе средний из которых является уникальным, а два других представляет 4 случая.
2-й шаг мог бы быть сделан игроком, который ставит кружок.
Здесь все возможные ходы для 2-го игрока после удаления симметричных случаев.
Если мы будем продолжать, чтобы пройти все возможные ходы, в результате график даст нам пространство состояний.
Угадайте, сколько возможных состояний есть? Если вы достаточно терпеливы, чтобы проследить все возможности, вы увидите, что есть более чем 250000 возможных последовательностей. Вместо того чтобы идти через все случаи, давайте дальше расширять только один конкретный случай.
Здесь все возможные размещения 2-го крестика после этого конкретного выбранного состояния, и все возможные места размещения 2-го кружка.
3-я шаг со стороны игрока с крестиком приведет к первому возможному состоянию выигрыша.
Кроме того, 3-й шаг для кружка приведет ко второму возможному состоянию выигрыша.
Также есть состояние ничьей.
Эти результаты состояния победы вместе с состоянием ничьей образуют множество конечных состояний.
Есть много больше конечных состояний, которые не показаны здесь.
И после прочтения этой книги, вы должны уметь писать программы для такого рода игр или даже более сложных задач.
Пример задачи
Давайте рассмотрим другой пример, чтобы проиллюстрировать, как выбор соответствующего представления может упростить поиск решений более сложной задачи.
Как и в игре крестики-нолики, задача здесь начинается с матрицы 3х3, но в этой задаче, клетки занимают квадратные яблоки.
Давайте назовем это задачей квадратных яблок.
Люди на самом деле могут вырастить квадратные яблоки или даже квадратные арбузы.
Предположим, что в исходном состоянии этой задачи существует червь в средней ячейке.
Вопрос в том, может ли червь съесть все яблоки, выполнив следующие два правила.
Во-первых, после того, как червь закончил целое яблоко в текущей ячейке, он может двигаться только в другую ячейку, которую разделяет общая сторона, так что эти стрелки показывают 4 возможных хода и 2-е правило состоит в том, что вы не можете переместиться в ту ячейку, которую посещали прежде.
То есть, червь может двигаться только в ячейку, где есть еще несъеденное яблоко внутри.
Рисунок показывает, что червь начинает с середины. После того, как заканчивается среднее яблоко, он может двигаться в одну из четырех клеток на стороне, но не в углу. Таким образом, червь может двигаться вправо, двигаться вниз, двигаться влево и двигаться вверх.
Я хочу, чтобы вы подумали, есть ли решение этой задачи.
То есть, может ли червь съесть все 9 яблок.
Это должно быть совершенно очевидно.
Здесь часть пространства состояний графа и это возможный путь, который может привести к решению.
На самом деле, вы обнаружите, что есть 7 других пути для решения, пробуя другие ходы.
Можно написать программу Java, которая была бы создана для решения этой задачи.
И после прочтения этой книги, вы должны быть в состоянии написать собственную программу для решения таких задач, как эта.
Это демо-программа, которая была написана для вас, чтобы проиллюстрировать решение задачи квадратного яблока.