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