Раздел: Документация
0 ... 46 47 48 49 50 51 52 ... 177 в лей значение 0 элемента, соответствующего клетке начала движения, на 1. Исполнять роль такого «детонатора» у нас будет функция recurstvesolverftJ. i, j). где n - размер-не, гь доски 1 oi индексы к. in кн. :п которой кит. юл жен начать движение, Ее кол: rccunrivesolver (n, i, j) field ч- chcasfield (n) field <- 1 I bronfi.j,field, 1) Первое действие, которое должна выполнить функция brain, это проверить, не закончил ли кон ь обход доски на прошлом шаге. На то, ты л <> действительно так, будет указывать отсутствие нулей в описывающей поле матрице field. Наименьшим значением в ней будет 1. Выделить же минимальный элемент из матрицы можно, воспользовавшись функцией min. Если проверка покажет, что обход был успешно завершен, то текущая активация должна быть разрушена, а в точку вызова возвращена матрица field, хранящая найденный маршрут. Осуществить эти действия позволяет оператор return. brain(i, j,field,n) := return field if minefield) = 1 i Если на иоле есть еще нсносещенные клетки, нужно проверить, можно ли сделать шаг в одну из н их из клетки, в которой конь находится в данный момент. Для этого следует запустить цикл от 0 до 7, последовательно перебирая все варианты хода. Чтобы вычислить индексы клетки, в которую конь переместится, сделав некоторый ход, нужно к индексам данной клетки прибавить смещения по соответствующим направлениям (как вы помните, смещения для всех вариантов шага хранятся в векторах вложенного вектора step), Вычислив индексы, нужно проверить, корректны ли они. Индекс не может быть меньше нуля и больше или равен номеру последнего столбца (строки) матрицы поля. Если окажется, что значение индекса некорректно, необходимо сразу перейти к рассмотрению следующего варианта хода, для чего нужна задействовать оператор continue. Аналогично нужно поступить, если клетка, в которую перешел бы кон ь в резул ьтате хода, уже была посещена им ранее (об этом говорит то, что значение соответствующего элемента матрицы поля не равно 0). for кеО.Л -И+(«ерД jl-j+j continue if -i(t> <. it < rows(field) л 0 i, jl < cols (field) л field =0 i Обратите внимание, как был задан комплекс условий, выполнение которых необходимо, чтобы ход можно было осуществить. □ В Mathcad возможны двойные сравнения типа А£х£В. Это довольно необычно: В универсальных языках программирования сначала бы вычислялось условие ASX, а полученный при этом результат сравнился затем с В. По этой причине в таких языках, как С++, двойные сравнения невозможны (их необходимо разбивать на отдельные операции сравнения, связанные посредством операторов логического И и ИЛИ). В Mathcad же можно задавать не только двойные, но и более сложные сравнения, содержащие сколь угодна много операций. Например; 2<3<4<5<б=16> 4<r S<7 = 1 □Посредством двойных сравнений мы проверяем, существует ли клетка, в которую переместился бы конь в результате хода. Ее индексы не должны быть отрицательными и превышать количество строк (столбцов) в матрице. Определить размерность матрицы можно, воспользовавшись функцией rows (количество рядков) или cols (количество столбцов). □Отдельные условия объединяем в комплекс условий посредством операторов логического И «а», так как для того, чтобы конь мог сделать ход, необходимо одно* временное выполнение всех условий. Если бы было достаточно выполнения хотя бы одного условия, мы бы задействовали оператор логического ИЛИ «V*. Важной особенностью логических операторов является то, что они имеют более низкий приоритет, чем операторы сравнения (подобно тому, как операторы суммы и разности уступают по приоритету умножению и делению), Поэтому двойные сравнения не нужно брать в скобки, объединяя их посредством оператора И. На момент вычисления оператора И выражения справа и слева его уже будут вычислены в 0 или I. □Комплекс условий записан так, что он вычисляется в истину тогда, когда конь может сделать ход в клетку, Однако оператор continue должен быть задействован тогда, когда условия вычисляются в ложь. По этой причине нужно перед комплексом условий ввести оператор логического НЕ *—>*-, который преобразует ложь в истину, а истину в ложь. Если все необходимые условия выполнятся, нужно сделать Ход Это будет выражаться в том, что значение соответствующего клетке элемента матрицы field должно быть изменено с 0 на номер данного хода. Определить этот номер очень просто, так как номер предыдущего хода передается функции Ьгаш в качестве четвертого параметра. field, ., *- п + 1 Сделав ход, нужно выполнить рекурсивный вызов функции brain. Результатом этого вызова будет илн сообщение 4 Bad way*, означающее, что данный путь тупиковый, или матрица с найденным маршрутом. Если маршрут будет найден, дальнейшую работу функции продолжать нет смысла. При этом активация должна быть разрушена, а в качестве результата ее работы возвращена матрица с маршрутом. Если же данный путь оказался тупиковым, необходимо сделать шаг назад, что будет выражаться в том, что значение заполненного последним элемента матрицы field должно быть заменено нулем. res fitld +- brain(il,jl,field,i] -t- 1) return res 6eld if res field * "Bad way" field. ., *-0 il,)l Важным и тонким моментом является то, как активации функции brain обмениваются информацией. Почему для того, чтобы следующая активация «знала», какие клетки уже были посещены конем, матрица field должна быть передана ей в качестве параметра? Почему для того, чтобы «спустить» матрицу с маршрутом от последней активации К первой, она должна последовательно возвращаться активациями, по мере их разрушения, как результат их работы? На это имеется две причины. Во-первых, функция не может изменить объект данных, который не относится непосредственно к ее коду. При обращении к внешней переменной нз кода функции создается копня ее значения. И именно с копией работает код функции. Поэтому, даже если объект данных, хранимый во внешней переменной, подвергается модификациям по мере работы кода функции, после разрушения активации никаких изменений не останется, так как все операции проводились над копией. Именно поэтому матрицы field и res field нельзя вынести во внешние переменные. Во-вторых, функция, вызванная из кода другой функции, не видит ее локальных переменных, Поэтому нельзя создать матрицу field при вызове функции recursive solver, азатем лишь модифицировать ее по мере роста рекурсивной цепи. Код функции может обращаться лишь к глобальным переменным. Если все варианты шага будут просмотрены и не один из них не приведет к нахождению искомого маршрута, направление признается тупиковым. В этом случае функция brain должна возвратить строк}1 «Badway*. Функция brain готова. Ее полный код: brain(i,j,field,n):= return field if min(field) = I for KSU..7 j-iU-i+(stepk jl«-j+(*q>vjn continue ifO£iI<rows(field)AO £ jUcobKfield) Afield -6) 6еЦ1Л<-п+1 res field «- brain(il,jl,field,n + 1) return res field if res field* "Bad way" field, .. +-0 "Bad way" Как видите, функции brain соответствует довольно небольшой код. Это очень характерно для рекурсивных алгоритмов: их абстрактность и сложность для понимания компенсируется компактностью, доходящей порой до изящества Именно поэтому рекурсивные алгоритмы столь популярны в программировании, Проверим написанный код в работе. Мы увидим, что он весьма эффективен: он находит маршрут вне зависимости оттого, какая клетка выбрана начальной. Однако, увы, за приемлемое время маршрут обнаруживается лишь для досок размером 6x6 клеток или более маленьких. Для стандартной же доски 8x8 клеток поиск будет вестись столь долго, что результата будет просто невозможно дождаться. Это связано с колоссальным количеством вариантов, которые необходимо перебрать алгоритму. recursive solver(5,0,0) =
recursive soIver(6,3,3) =
Увы, но написанную программу невозможно оптимизировать так, чтобы она стала работать существенно быстрее. Не получится найти решение для доски 8x8 клеток, даже если программу перевести в нерекурсивную форму или реализовать ее посредством компилируемого языка вроде С++. Дело в том, что в основе нашей программы лежит 0 ... 46 47 48 49 50 51 52 ... 177
|
