<<
>>

Рекурсивные алгоритмы

Упражнение № 1. Знакомство с рекурсивными алгоритмами Пример 65. Написать программу построения изображения, представленного на следующем рисунке:

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

Всего изображено четыре уровня окружностей. Для того, чтобы составить программу построения этого изображения, можно: • описать процедуру изображения одной окружности с четырьмя окружностями поменьше; • для изображения каждой окружности следующего уровня использовать эту же процедуру, только с другими значениями параметров — координат центров, величин радиусов и т. д. Опишем алгоритм рисования окружности радиуса г с центром в точке (х,у) с четырьмя окружностями вокруг. При этом необходимо знать расстояния (г1) от точки (х,у) до центров окружностей окружения (радиусы орбиты), которые, очевидно, равны.
Пусть — = к\, где г — радиус окружности окружения, — = к2. г г Procedure Picturel(x,y,r, rl:Integer); Begin {изобразить окружность с центром (х,у) и радиусом г} ; {вычислить rl}; • For i:=l То 4 Do Begin {вычислить координаты центра (xl,yl) i-й окружности}; Picturel(xl, у1, Сновое значение r>, rl) ; End; End. Таким образом, в описанной процедуре мы осуществляем вызов ее же самой в качестве вспомогательной. Как вычислить значения xl, у\1 Они зависят от х и у следующим образом: х\ = х + dx, у\ = у + dy. Необходимо выразить значения приращений координат dx, dy. Воспользуемся определениями тригонометрических функций sin и cos: dx = rl • cos(a) dy = rl • sin(a), где a = к/2, к, Зк/2, 2n. Если осуществить вызов этой же процедуры из основной программы с начальными параметрами, то рекурсивные вызовы никогда не закончатся и программа будет работать бесконечно.
Для того, чтобы этого не случилось, можно ввести в качестве аргумента процедуры некоторую величину п, которая при каждом новом вызове процедуры будет уменьшаться на 1, а в тело процедуры включить условие, что его операторы должны выполняться только при п > 0, то есть это условие будет играть роль своеобразной «заглушки», ограничивающей число вызовов процедуры. Ниже приведена программа, полностью решающая поставленную задачу. В основной программе запрашиваются радиус г самой большой окружности и число уровней п, а также задаются значения коэффициентов kl и kl. Центр самой большой окружности располагается в центре экрана. Program Example_65; • Uses Graph; Var x,y,n,г, rl, cd,gm:Integer; kl,k2:Real; • Procedure Picture2(x,у,r,rl,n:Integer); Var xl, yl:Integer; i:Integer; Begin If n>0 Then {"заглушка"} Begin circle (x,у,r); {рисование окружности} rl:=trunc(r*k2); {вычисление радиуса орбиты} For i:=l To 4 Do Begin xl:=trunc(x+rl*cos(pi/2*i)); yl:=trunc(y+rl*sin(pi/2*i)) ; {координаты центра i-й окружности} • picture2(xl,yl,truno(r*kl),rl,n-1); {вызов процедуры с новыми параметрами} End; End; End; Begin {задание начальных значений} Write-In ( 'Введите число уровней п. ' ) ; Readln(n); х:=600 Div 2; у:=400 Div 2; Writeln('Введите радиус первой окружности г'); Readln(r); kl:=0.3; k2:=2; cd:=detect; gm:=l; {инициализация графики} initgraph(cd, gm, 'c:\tp7_0\bin'); picture2(x,y,r,rl,n); Readln; {задержка на экране} closegraph; End. Примечания: 1. Для того чтобы проследить последовательность рисования окружностей при рекурсивных вызовах, можно дополнительно включить в тело процедуры простой цикл, обеспечивающий некоторую паузу перед выводом на экран очередной окружности. 2. Изменяя в процессе демонстрации работы программы значения kl9 к2, п, можно получать множество привлекательных рисунков. Пример 66. Снежинка. Разработать программу, которая обеспечивает рисование снежинки, число звеньев и число ветвей которой задаются пользователем. На рисунке ниже изображена снежинка, состоящая из трех звеньев и восьми ветвей.
Сделаем расчет дайны каждого звена по известному значению п — количеству звеньев и величине экрана. Будем считать, что снежинка строится в квадрате 400 х 400 точек. Центр снежинки совпадает с центром квадрата, а длина отрезка каждого

очередного звена в четыре раза меньше предыдущего. Если через / обозначить длину первого звена, то справедливо следующее равенство: или

то есть Пусть снежинка состоит из одного звена и р ветвей, тогда соответствующая программа проста. Основная ее часть имеет вид For i:=l То р Do Begin xl:=trunc(x+l*cos(2*pi*(i-1)/p)); yl:=trunc(y+l*sin(2*pi*(i-1)/p)); {координаты конца очередного звена} line(х,у,xl,yl); {рисование звена} End; Здесь х, у — координаты точки центра снежинки. Наша снежинка рисуется как бы много раз, при этом длины звеньев изменяются, поэтому их надо просчитать один раз и запомнить в массиве L из п элементов. Длина каждого звена уменьшается в четыре раза по отношению к предыдущему. Длина первого звена определяется из того, что в квадрате из 400 х 400 точек необходимо построить снежинку из п звеньев. Если мы дошли до этапа рисования самого маленького звена (самой маленькой снежинки), то наша программа должна работать как приведенный набросок. Итак, логика решения задачи.

Начинаем рисовать из центра, точки А, нарисовали первый отрезок АВ (а), если это не последнее звено, то будем рисовать отрезок следующего звена ВС, звено не последнее, поэтому продолжим.

Предположим, что нарисовали СЕ, это первая ветвь самой маленькой снежинки, наша программа должна работать как набросок, то есть рисовать все ветви этой снежинки. После этого мы должны вер- нуться в точку В. Так как это не последняя ветвь этой снежинки, то мы снова должны нарисовать следующую ветвь — отрезок BD (б), а затем снова полностью самую маленькую снежинку. Что необходимо для реализации этой логики? Пусть значение переменной к будет равно текущему номеру звена снежинки, в начальный момент оно равно п. Тогда при переходе от точек С, D к точке В мы должны «вспомнить» координаты точки В и номер ветви снежинки, рисуемой из точки В. При переходе от точки В к точке А мы должны «вспомнить» координаты точки А и номер ветви снежинки, рисуемой из точки А. Эта логика легко реализуется с помощью рекурсии. Примечание. Для вычисления значения показательной функции ап используется тождество ап= епЫа. Program Example__66; Uses Graph; Const р=8; n=4; Var x, у, i,cd, gm: Integer; *•••■■ L: Array[l..n] Of Integer; Procedure Picture3 (x, y, k: Integer); Var xl, yl: Integer; i: Integer; . Begin If k>0 Then {«заглушка»} Begin • For i:=l To p Do Begin {координаты конца очередного звена} xl:=trunc(x+L[k]*cos(2*pi*(i-1)/p)); yl:=trunc(y+L[k]*sin(2*pi*(i-1)/p)); • line(x,y,xl,yl); {рисование звена} picture3(xl,yl,k-1) ; End; End; End; Begin L[n] := trunc(200*3*exp ( (n-1)*ln(4))/(exp(n*ln(4))-l)); {***} r For i:=2 To n Do L[n-i+1]:=trunc(L[n]/exp((i-1)*ln(4))); г x:=300; y:=200; {координаты центра снежинки} cd:=detect; gm:=l; {инициализация графики} - Initgraph (cd, gm, ' с :\tp7_^0\bin ' ) ; . Picture3(x,y,n); Readln; {задержка на экране} Closegraph; End. Задания 1. Модифицировать программу так, чтобы пересекающиеся части отрезков (АВ, ВТ) рисовались один раз. 2. Если строку программы, помеченную {***}, изменить на L [1] :=trunc(200*3*ехр((п-1)*1п(4))/(exp(п*1п(4))-1) ) ; то какие дальнейшие изменения необходимо внести в программу? Упражнение № 2.
Простые задачи Пример 67. Написать рекурсивную программу поиска минимального элемента массива. Решение. Опишем функцию p min, которая определяет минимум среди первых п элементов массива а. Параметрами этой функции являются число элементов в рассматриваемой части массива п и значение последнего элемента этой части а[п]. При этом если п > 2, то результатом является минимальное из двух чисел — а[п] и минимального числа из первых (п — 1) элементов таблицы. В этом заключается рекурсивный вызов. Если же п = 2, то результатом является минимальное из первых двух элементов массива. Чтобы найти минимум всех элементов массива, надо обратиться к функции p min, указав в качестве параметров значение размерности массива и значение последнего его элемента. Минимальное из двух чисел определяется с помощью функции min, параметрами которой являются эти числа. Program Example_67; Const n=10; Type MyArray=Array[1..n] Of Integer; Const a:MyArray=(4,2,-1,5,2, 9,4,8,5,3); . Function min (a,b:Integer):Integer; Begin If a>b Then min:=b Else min:=a; • End; Function p_min(n,b:Integer):Integer; Begin If n=2 Then p_min:=min(n,a[1]) Else p_min:=min(a[n],p_min(n-1,a[n])); End; Begin WriteIn('Минимальный элемент массива -',p_min(n,a In])); End. Пример 68. Ханойские башни. Имеются три стержня А, В, С. На стержень А нанизано п дисков радиуса 1, 2, ..., п таким образом, что диск радиуса i является i-м сверху. Требуется переместить все диски на стержень В, сохраняя их порядок расположения (диск с большим радиусом находится ниже). За один раз можно перемещать только один диск с любого стержня на любой другой стержень. При этом должно выполняться следующее условие: на каждом стержне ни в какой момент времени никакой диск не может находиться выше диска с меньшим радиусом. Решение. Когда кольцо одно, никаких проблем нет, все действия очевидны. Предположим, что мы умеем перекладывать пирамиду из (п— 1) кольца. Рассмотрим пирамиду из п колец. Переместим первые (п— 1) колец на стержень С (это мы умеем). Затем перенесем последнее я-е кольцо со стержня А на стержень В.
Далее перенесем пирамиду из (п— 1) кольца со стержня С на стержень В. Так как я-е кольцо самое большое, то условие задачи не будет нарушено. Таким образом, вся пирамида будет на стержне В. Действуя так, можно переложить любое число колец. При этом для решения задачи будет достаточно 2п— 1 перекладываний. Program Example_68; . Const k=3; Var a,b,c: Char; Procedure Ring(n: Integer; a, b, c: Char); Begin If n>0 Then Begin Ring(n-1,a,c,b); Writeln('кольцо' , n,' c ' , a,'—>',b, ' ' ) ; Ring(n-1,c,b,a); End; End; Begin a: = ’A’; b^’B’; c:=’C'; Ring(k,a,b,c); Readln End. Упражнение № 3. Фрактальные кривые Пример 69. Написать программу получения следующего изображения:

В треугольнике проводятся все три средние линии. В результате он разбивается на 4 новых треугольника. К трем из них, примыкающим к вершинам первоначального треугольника, применяется та же процедура. Program Example_69; Uses Graph; . ^ Var хс,ха,xb,уа,yb,ус:Integer; {координаты вершин треугольника} n,cd,gm:Integer; Procedure Triangle(xa, ya, xb, yb, *xc, yc, n:Integer); {координаты середин сторон треугольника} Var хр, xq, xr, yp, yq, yr: Integer; Begin If n>0 Then {«заглушка»} Begin {вычисление координат середин сторон треугольника} xp:=(xb+xc) Div 2; yp:=(yb+yc) Div 2/ xq:=(xa+xc) Div 2; yq:=(ya+yc) Div 2; xr:=(xb+xa) Div 2; yr:=(yb+ya) Div 2; line(xp ,yp ,xq,yq) ; {изображение средних линий треугольника} line(xq,yq,xr,yr); line(xp,yp,xr,yr); Triangle(xa,ya,xr,yr,xq,yq,n-1); Ttriangle(xb,yb,xp,yp,xr,yr,n-1)/ Triangle(xc,yc,xq,yq,xp,yp,n-1); End; End; Begin {задание начальных значений} {координаты вершин самого большого треугольника} хс:=300; ус:=0; xb:=600; yb:=400; ха:=0; уа:=400; cd:=detect; gm:=l; initgraph(cd,gm,'c:\tp7_0\Bin'); {изображение первого самого большого треугольника} line(ха,ya,xb,yb); line(xb,yb,хс,ус); line(ха,уа,хс,ус); Triangle(ха,ya,xb,yb,хс,ус,6); Readln; {задержка на экране} Closegraph; . End. Задания для самостоятельного выполнения 1. Написать рекурсивную программу вычисления п-то члена геометрической прогрессии, суммы ее п первых членов и суммы ее членов, начиная с /-го по к-й. 2. Описать рекурсивную функцию вычисления максимального числа Фибона- чи, ближайшего к заданному п по недостатку. 3. Описать рекурсивную функцию поиска индекса минимального элемента массива. 4. Составить рекурсивную программу, проверяющую, является ли палиндромом фрагмент строки с /-го по у-й символ. 5. Составить программы для построения на экране следующих изображений:

6. Изменить программу рисования кривых Гильберта так, чтобы обеспечить рисование кривых С[ 1], С[2], С[3], С[4], С[5] (см. базовый учебник «Информатика»). 7. Изменить программу рисования кривых Гильберта так, чтобы обеспечить рисование кривых А[3], В[3], С[3], D[3]. 8. На рисунке изображены кривые Серпинского 1 и 2-го порядков. Составить программу построения кривых 1, 2, 3, 4 и 5-го порядков, так чтобы центры этих кривых совпадали.

9. На рисунке изображены кривые Коха 1 и 2-го порядка. Составить программу построения кривой 7У-го порядка.

10. На рисунке изображены прокладки Серпинского 1 и 2-го уровня. Разработать программу построения прокладки Серпинского 7У-го порядка.

11. На рисунке изображен ковер Серпинского 1 и 2-го уровня. Разработать программу построения ковра Серпинского 7У-го порядка.

Упражнение № 4. Перебор с возвратом Многие комбинаторные задачи можно представить как поиск элементов конечного множества, удовлетворяющих определенным условиям. Очевидно, что всегда есть «лобовое» решение, состоящее в переборе всех элементов этого множества с проверкой соответствующих условий. Однако даже для простых задач такой перебор потребует огромных временных затрат. Общая схема Любая комбинаторная задача, к которой применим алгоритм перебора с возвратом, может быть описана в общем случае следующим образом: даны п линейно упорядоченных множеств Uu U2,..., Un и требуется построить вектор А = (аь аъ..., ап), где ахе £7], а2е иъ..., апе Un, удовлетворяющий заданному множеству условий и ограничений. В алгоритме перебора с возвратом вектор А строится покомпонентно слева направо: Предположим, что уже найдены значения первых к— 1 компонент, А =х, а2, ..., ак-1, ?,..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты ^некоторым множеством Skс Uk. Если ^оказалось непустым, мы вправе выбрать в качестве ак наименьший элемент Sk и перейти к рассмотрению Sk+, и так далее. Однако, если условия таковы, что Sk оказалось пустым, мы возвращаемся к предыдущему этапу, выбрасываем (к — 1)-й элемент ак-х и выбираем в качестве нового ак— 1 тот элемент Sk-X, который непосредственно следует за только что отброшенным. Может оказаться, что для нового ак-х условия задачи допускают непустое и тогда мы попытаемся снова выбрать элемент ак. Если невозможно выбрать ак-и то возвращаемся еще на шаг назад и выбираем новый элемент ак-2 и так далее. Алгоритм Шаг 1. [Начало] Положить к = 1 и Sx = Ux. Шаг 2. [Следующий элемент 5J Если Sk пусто, то перейти к шагу 5, иначе — положить ак равным наименьшему из элементов Sk. Шаг 3. [Закончено ли решение?] Если к 1, то уменьшить А; на 1, положить S* = S*\{fl*} и вернуться к шагу 2. Пример 70. Задача о шахматном коне. Существуют способы обойти шахматным конем шахматную доску, побывав на каждом поле по одному разу. Составить программу нахождения всех возможных способов обхода доски. Решение Структуры данных. Для хранения «истории» прохождения конем доски необходимо знать, был на конкретном поле[/,у] конь или нет. Из поля [/, у] конь может попасть (в максимальном варианте) на восемь полей. В массивах di[ 1..8], dj[ 1..8] будем хранить приращения к значениям координат, в сумме с которыми /, j дают возможные координаты нового хода коня. Примечание. На рисунке символом ** обозначено положение коня, а цифрами 1, 2,..., 8 — номера ходов, которые можно сделать из поля [3, 5]. Выполнив очередной ход, можно: • попасть за пределы доски; • попасть в поле, которое уже занято; • попасть в поле, которое пока еще свободно. Учитывая это, для доски из т горизонталей и п вертикалей вводится массив

где

Основная логика работы достаточно проста: Begin If Or Then exit Else Begin ; ; End; End; Поиск варианта обхода начинается с левой верхней клетки доски, то есть с r[ 1, 1]. Выполнить ход можно только в том случае, если клетка свободна или если не осуществляется выход за пределы доски (г[/, у] = 0). Сделать ход конем означает изменить значение соответствующего элемента массива г на очередное значение t — Если очередная клетка занята или если ход делается за пределы доски, надо попытаться сделать из той же позиции другой ход— взять следующие значения из массивов ri и rj. Если все 8 вариантов ходов из текущего положения будут проверены и ни одно из них не приведет к выполнению хода, то есть это ситуация, когда конь не может продолжать обход доски. В этом случае мы должны вернуть один ход или серию ходов и попытаться найти новый вариант обхода. Для этого надо взять следующие значения приращений координат из массивов ri и rj, попытаться сделать новый ход и так далее. Но для того, чтобы осуществить «возврат», необходимо знать «историю» обхода. Завершается поиск обхода, если все клетки пройдены, то есть значение t равно т* п (тогда надо вывести массив на экран), или если конь не может выполнить очередной ход (на экран надо вывести сообщение о невозможности выполнения обхода). Реализовать такую логику поиска обхода выгоднее всего с помощью рекурсии. Program Example_70; Const n=4; m=5; {размеры доски} q: Boolean=faise; {возможно ли сделать обход} di: Array[1..8] Of Integer=(-2,-1,1,2,2,1,-1,-2); dj: Array[1..8] Of Integer=(1,2,2,1,-1,-2,-2,-1); Var a: Array[-1..n+2,-1..m+2] Of Integer; i, j, 1: Integer; Procedure Print; {вывод двумерного массива на экран} Begin For i:=l To n Do Begin For j:=l To m Do Write (a [i,j] :3); . Writeln . . ' End; End; Procedure rec (i,j,t:Integer); {процедура поиска обхода} Var k:Integer; Begin If (a[i,j]0) Then exit {выход за пределы доски или клетка занята} . ■ ■ , = Else \ Begin a[i,j]:=t; {сделать ход} If t=n*m Then {выполнен полный обход} Begin print; q:=true End Else For k:=l To 8 Do rec (i+di[k],j+dj[k],t+1) ; {выбор нового хода} a[i,j]:=0; {возврат на один шаг назад} End; End; Begin {заполнение массива} For i:=—1 То n+2 Do For j : ==— 1 To m+2 Do If (in) Or (jm) Then a[i,j]:=-l; For i:=l To n Do For j:=l To m Do rec(i,j,l); {выбор местоположения первого коня} + If not q Then Writeln('Невозможно выполнить обход'); + Readln; End. Пример 71. Задача о ферзях. Существуют способы расстановки 8 ферзей на шахматной доске 8х 8 так, чтобы они не били друг друга. Составить программу нахождения всех возможных способов. Решение. Структуры данных. Из шахмат известно, что ферзь, установленный на поле [/,у ], бьет все фигуры, находящиеся на той же самой вертикали у, горизонтали / и диагоналях, для которых сумма (/ + у) и разность (/ — у) индексов постоянны. На рисунке показаны значения сумм и разностей индексов для восходящих от 2 до 16 и нисходящих от —7 до 7 диагоналей. Рассмотрим нашу задачу для доски 4x4. Начинаем просмотр горизонтали 1 и пытаемся найти поле [/,у] для постановки ферзя. Если мы установили ферзя на поле [1,1], то поля, отмеченные на рисунке «*», считаются занятыми («под боем»). Переходим на вторую горизонталь. Ферзя можно установить на поле [2,3], тогда

поля, отмеченные «#», также выбывают из рассмотрения. Переходим на третью горизонталь, на ней все поля «под боем», поэтому необходимо вернуться на вторую горизонталь и попытаться установить на ней ферзя по-другому, рис. б. Следующее поле [2,4]. Возвращаемся на третью горизонталь, поле [3,2] свободно. Устанавливаем ферзя и переходим на четвертую горизонталь. Установить на ней ферзя нельзя. Возвращаемся на третью горизонталь — больше допустимых полей нет, на вторую — на ней также нет и, наконец, на первую. Устанавливаем ферзя на следующее поле [1,2]. Поля, отмеченные «*», — «под боем», рис. в, второго ферзя — на поле [2,4], поля «#» — «под боем», третьего ферзя на поле [3,1], поля «@» — «под боем». И наконец, четвертого ферзя можно поставить на поле [4,3]. Итак, логика основной части программы, текст которой приведен ниже, имеет следующий вид: Program Example__71; Const n=8; k:lnteger=0; {счетчик проверок безопасности полей} . Var x:Array [l..n] Of Integer; {решение} arArray [l..n] Of Boolean; {вертикаль} ' brArray [2..2*n] Of Boolean; {восходящая диагональ(/)} c:Array [-n+l..n-l] Of Boolean; {нисходящая диагональ(\)} Procedure Init; {начальные значения} - Var i:Integer; Begin FillChar(a,SizeOf(a),True); FillChar(b,SizeOf(b),True); FillChar(c,SizeOf(c),True); End; Procedure Move(i,j:Integer); {процедура «фиксируй ход»} Begin x[i]:=j; a[j]:=False; b[i+j]:=False; c [ i-j] :=False; End; Procedure Back_Move(i,j:Integer); {процедура «отмена хода»} Begin a[j]:=true; b[i+j]:=true; c[i-j]:=true; End; Function D_Hod(i,j:Integer):Boolean; {функция ¿возможен ли ход»} Begin D__Hod:=a[j] And b[i + j] And c[i-j] End; Procedure Print; {вывод решения} 4 Var i,j ¡Integer; Begin For i:=l to n Do Begin For j:=1 To N Do . If j=x[i] Then Write(’i’:2) Else Write('*f:2) ; Writeln(x[i] :3) ; End; WriteLn(k); ' End; Procedure Solve(i:Integer); {нахождение решения} , Var j:Integer; Begin If i=n+l Then Begin Inc(k); Print End Else For j:=1 To n do If D_Hod(i,j) Then Begin Move(i,j); Solve(i+1); Back_Move(i,j) ; End; End; Begin {основная программа} Init; Solve(1); ReadLn End. Пример 72. Задача о лабиринте. Прямоугольное клеточное поле ограничено препятствиями. Кроме того, на поле задается произвольная система препятствий, начальная клетка, на которой находится Черепашка, и конечная клетка. Найти маршрут выхода из лабиринта, если он существует, и пронумеровать клетки маршрута в том порядке, в котором проходит их Черепашка. Черепашка может делать шаг на одну клетку в любом из четырех направлений: влево, вправо, вверх, вниз. Решение. Структуры данных. Клеточное поле размером Nx М опишем двумерным массивом А размерности N + 2, М + 2. При этом будем считать, что A[i,j] = 0, если клетка [i,j] свободна и не посещалась Черепашкой; A[i,j] - —1, если клетка [i,j] является клеткой, на которой находится препятствие, или находится за пределами лабиринта.

Координаты входа — /1, у 1, координаты выхода — /2,/2. Они задаются пользователем. Блок задания исходных данных в программе и вывод массива Z достаточно просты, поэтому остановимся на разборе основной логики. Черепашка, перемещаясь по свободным клеткам (A[i,j] = 0), должна найти клетку выхода (A[ÜJ2] = 0), запоминая при этом свой путь, и после нахождения отметить свой путь числами, то есть в каждую клетку пути записать номер шага, на котором она проходит эту клетку. Предположим, что Черепашка находится в клетке a[i9j]. Из этой клетки она может сделать либо шаг на север, либо шаг на восток, либо шаг на запад, либо шаг на юг, если соответствующее направление не закрыто препятствием. Пусть Черепашка осуществляет поиск свободного поля для выполнения хода в следующем порядке: Т — соответствует уменьшению координаты / (Dec(/)); ): а [3, 4] := 4. Это тупик — с трех сторон клетка с координатами 4, 5 окружена препятствиями. Следовательно, надо вернуться на один шаг назад и попытаться по-другому сделать четвертый шаг. Из предыдущей клетки можно шагнуть еще и в четвертом направлении, то есть а[4, 3]:=4. Затем вновь делается шаг в четвертом направлении, единственно возможном (я[5, 3]:=5). И так далее до тех пор, пока Черепашка не доберется до конечной клетки. Таким образом, при анализе вариантов очередного хода Черепашке необходимо проверить, свободна ли рассматриваемая клетка. В этом случае a[ij] = 0. Ход делать нельзя в клетку, для которой a[i?j] = —1 (выход за границы лабиринта, в клетке препятствие), или а[ /, j] > 0 (ход назад). При выполнении 1-го хода в клетку с координатами /, j надо a[i, j] присвоить значение 1. Если Черепашка зашла в тупик (в трех направлениях препятствия или границы лабиринта), то она должна попытаться сделать новый вариант прохода. Для этого ей надо вернуться на один шаг назад и проверить оставшиеся варианты из предыдущей позиции. При этом необходимо «занулить» значение a[i, j]. Выбор варианта хода осуществляется из четырех возможных вариантов. В массивах Ъ и с, содержащих по 4 элемента, будем хранить приращения к значениям текущих координат, в сумме с которыми они дают возможные координаты нового хода Черепашки: b:Array[1..4] Of Integer=(-1,0,0,1); с:Array[1..4] Of Integer=(0,-1,1,0); Тогда выбор хода и проверку его возможности можно организовать с помощью цикла For к:=1 То 4 Do ^ If a[i+b[к],j+с[к]]=0 Then... Опишем этот процесс в виде рекурсивной процедуры Move(i,j, ¡. Integer), входными параметрами которой являются значения текущих координат Черепашки ij и 1 — номер ее очередного шага. Если текущие значения координат совпадут с заданными конечными значениями /2, fl, то необходимо вывести лабиринт с отмеченным проходом Черепашки и закончить работу. Вывод осуществляется процедурой Print(a:my array). Если прохода из заданной начальной клетки в заданную конечную клетку не существует, то необходимо вывести информацию об этом на экран. В этом случае, после того как Черепашка проверит все возможные способы прохода, и необходимый результат не будет получен, значение a[i2, fl] по-прежнему будет равно 0. Program Example_72; Uses Crt; Const n=5; m=6; {размеры поля} b:Array[1..4] Of Integer=(-1,0,0,1); c:Array[1..4] Of Integer=(0,-1,1,0); Type myarray=Array [0..n+1,0..m+1] Of Integer; Var a: myarray; {исходный лабиринт} . i,j,il,i2,j1,j2: Integer; Procedure Init; {формирование массива а из файла} Var i, j, t: Integer; f: text; Begin Assign(f,'с:\1.dat1); Reset(f); For i:=0 To n+1 Do For j:=0 To m+1 Do a[i,j]:=-l; For i:=l To n Do For j:=1 To m Do Read(f,a[i,j]); Close (f); End; Procedure Print(a: myarray); {печать лабиринта} Var i, j: Integer; Begin For i:=l To n Do Begin For j:=1 To m Do Case a [ i,j] Of -1: Write(1 * 1) ; 0: Write( ' ' ) ; Else Write(a[i,j]:3); End; Writeln; End; End; Procedure Move(i, j, 1: Integer); Var к¡Integer; Begin If (i=i2) And (j =j2) Then {достигнута конечная клетка} Begin print (a); exit End Else Begin For k:=l To 4 Do {выбор направления хода} If a[i+b[k],j+c[k]]=0 Then {шаг сделать можно} Begin a [i+b[k],j+c[k]] :=1; {сделать шаг} hod(i+b[k],j+c[k] ,1 + 1) ; a[i+b[k],j+c[k]]:=0; {возврат на 1 шаг назад} End; End; End; Begin Clrscr; Writeln('ДАННЫЙ ЛАБИРИНТ:'); Writeln ( '_____________ '); Init; Print(a); Writeln (.'ВВЕДИТЕ КООРДИНАТЫ ВХОДА'); Readln(il,j1); Writeln('ВВЕДИТЕ КООРДИНАТЫ ВЫХОДА'); Readln(i2,j2); a [il,j1] :=1; {первый шаг в начальную клетку с координатами il, jl} Move (i 1, j 1,2) ; If a[i2,j2]=0 Then Writeln('ПРОХОД НЕВОЗМОЖЕН'); Readln; End. Задания для самостоятельной работы 1. Какое наименьшее число ферзей можно расставить на доске так, чтобы держали под боем все ее свободные поля? Модификация задачи. Найти расстановку ферзей, которая одновременно решает задачу для досок 9x9, 10 х 10 и 11x11. 2. Расставить на доске ТУхТУ (М< 12) N ферзей так, чтобы наибольшее число ее полей оказалось вне боя ферзей. 3. Расставить на доске как можно больше ферзей так, чтобы при снятии любого из них появлялось ровно одно не атакованное поле. 4. За какое наименьшее число ходов ферзь может обойти все поля доски 8x8? 5. Расставить на доске 8x8 максимальное число ферзей так, чтобы каждый из них нападал ровно на р (р< 2) ферзей. (Ответ. При р = 1 десять, а при р = 2 четырнадцать.) 6. Задача о коне Аттилы («Трава не растет там, где ступил мой конь!»). На шахматной доске стоят белый конь и черный король. Некоторые поля доски считаются «горящими». Конь должен дойти до неприятельского короля, повергнуть его и вернуться на исходное место. При этом ему запрещено становиться как на горящие поля, так и на поля, которые уже пройдены. 7. Магараджа — это фигура, которая объединяет в себе ходы коня и ферзя. Для доски 10 х 10 найти способ расстановки 10 мирных магараджей. 8. (Задача с международной олимпиады школьников по программированию 1991 г.). Пронумеровать позиции в матрице (таблице) размером 5x5 таким образом, чтобы номер / (1 ) = (х, у ± 3); • и, я) = (х ± 2, у ± 2). Требуется: а) написать программу, которая последовательно нумерует позиции матрицы 5x5 при заданных координатах позиции, в которой поставлен номер 1 (результаты должны быть представлены в виде заполненной матрицы); б) вычислить число всех возможных расстановок номеров для всех начальных позиций, расположенных в правом верхнем треугольнике матрицы, включая ее главную диагональ.

<< | >>
Источник: Могилев А. В.. Практикум по информатике. 2005

Еще по теме Рекурсивные алгоритмы:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. ЗАДАЧА: РЕШЕНИЕ
  13. Переживание
  14. Переживание
  15. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  16. Замечания по структуре материала
  17. Прием структуризации психологического портрета.
  18. Работа с собой