программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 7. Рекурсия 7.2 Как приходят к рекурсивным подпрограммам? 7.2.1 Органически рекурсивные определения Нет готовых рецептов, как для данной произвольной проблемы получить (ре- курсивный) алгоритм ее решения. Однако некоторые рекомендации имеются. Многие рекурсивные подпрограммы являются точным «слепком» с соответ- ствующего определения. Это верно, скажем, в отношении подпрограммы вычисле- ния факториала. Для рекурсивного определения полиномов Лежандра: P n (x) = ⎧⎪⎪⎪ ⎪⎨ ⎪⎪⎪⎪ ⎩ 1, если n = 0, x, если n = 1, ((2n − 1)xP n −1 (x) − (n − 1)P n −2 (x))/n, сразу получаем рекурсивную программу. function p(n:integer;x:real):real; begin if n=0 then p:=1 else if n=1 then p:=x else p:=((2*n −1)*x*p(n−1,x)−(n−1)*p(n−2,x))/n end 7.2.2 Извлечение рекурсии из постановки задачи В большинстве случаев, однако, рассматриваемая задача не является алгорит- мически сформулированной. Поэтому пытаются прийти к (рекурсивному) алгорит- му, сводя общую задачу к «более простым» задачам того же рода. Точнее говоря, речь идет о получении достаточного числа (условных) уравнений, определяющих искомую функцию. Иногда непосредственно ясно, как это сделать, но чаще все- го требуется интуиция. Например, для решения задачи нахождения наибольшего общего делителя двух (положительных) чисел можно привлечь следующий мате- матический результат: если a — большее из двух чисел a и b, то пары a, b и a − b, b имеют одни и те же делители, а значит, один и тот же наибольший общий делитель. Отсюда непосредственно следует алгоритм gcd нахождения наибольшего общего делителя. В следующем примере рекурсивно определим сложение целых, опираясь на операции перехода к следующему и предыдущему числам. В силу законов ассоци- ативности и коммутативности имеем (a + 1) + (b − 1) = a + b. Поэтому операцию сложения можно ввести так: function plus(a,b:integer):integer; begin if b=0 then plus:=a else if b>0 then plus:=plus(succ(a),pred(b)) else plus:=plus(pred(a),succ(b)) end 7.2 Как приходят к рекурсивным подпрограммам? 129 В качестве еще одного примера покажем, как можно рекурсивно определить возведение в степень (причем алгоритм получается более эффективный, чем с ис- пользованием n-кратного умножения). Алгоритм: x 0 = 1, x 2n = (x × x) n , x 2n +1 = x ×(x × x) n Получаем естественную программу: function power(x:real; n:integer):real; {предполагаем, что n>0} begin if n=0 then power:=1 else if n mod 2 = 0 then power:= power(x*x, n div 2) else power := x * power(x*x, n div 2) end; 7.2.3 Вложение Если не удается извлечь рекурсию из самой постановки задачи, то часто оказы- вается полезным обобщить задачу (например, введя дополнительные параметры); подходящее обобщение позволяет усмотреть возможность рекурсии, а, возвраща- ясь к частному случаю, мы получаем алгоритм для первоначальной задачи. Классический пример применения такого приема вложения дал Маккарти в 1962 г. Исходная задача была: isprim (n): «Установи, является ли заданное положительное натуральное число n простым». При этом предполагается, что известно определение простого числа: «Нату- ральное число n называется простым, если оно больше 1 и не делится ни на одно число, большее или равное 2 и меньшее n». Удачным обобщением будет такая задача (в которой вводится один дополни- тельный параметр): ispr (n, m): «Установи, верно ли, что заданное натуральное число n не делится ни на одно число, большее или равное m и меньшее n». (Не уменьшая общности, можно считать, что 2 ⩽ m ⩽ n.) Но для этой новой задачи ясно, что ispr (n, m) истинно, во-первых, если m=n, и, во-вторых, если истинно ispr(n, m + 1) и n не делится на m, и мы приходим к подпрограмме: function ispr(n,m:integer):boolean; {2 <= m <= n} begin if m=n then ispr:=true else ispr:=(n mod m <>0) and ispr(n,m+1) end В качестве частного случая получаем нужную нам подпрограмму: function isprim(n:integer):boolean; {n>=1} begin if n=1 then isprim:=false else isprim:=ispr(n,2) end 130 Глава 7. Рекурсия 7.2.4 Использование характеристических свойств Иногда бывает целесообразно переформулировать характеристическое свой- ство задачи так, чтобы из него можно было извлечь какой-либо (другой) алгоритм. Так в задаче: для заданного натурального числа n ⩾ 1 определить (единственное) натуральное число ld (n), такое что 2 ld (n)−1 ⩽ n ⩽ 2 ld (n) необходимо выполнение предиката P (ld (n), n), где P (a, n) = 2 a −1 ⩽ n ⩽ 2 a Но для этого характеристического предиката P (a, n) имеет место очевидная рекурсия P (a, n) = ⎧⎪⎪ ⎨⎪⎪ ⎩ a = 1, при n = 1, P (a − 1, n div 2), при n > 1, а значит, и ld(n) допускает рекурсивное определение ld (n) = ⎧⎪⎪ ⎨⎪⎪ ⎩ 1, при n = 1, ld (n div 2), при n > 1, из которого получаем алгоритм: function ld(n:integer):integer; {n>=1} begin if n=1 then ld:=1 else ld:=ld(n div 2)+1 end 7.2.5 Разделяй и властвуй Для решения той или иной задачи ее часто разбивают на части, находят их решения и затем из них получают решение всей задачи. Этот прием, особенно если его применять рекурсивно, часто приводит к эквивалентному решению задачи, подзадачи которой представляют собой ее меньшие версии. Проиллюстрируем эту технику на следующем примере. Рассмотрим задачу о нахождении наибольшего и наименьшего элементов мно- жества S, содержащего n элементов. Представим множество в виде массива x:array[1..n] of integer Очевидный путь поиска наибольшего и наименьшего элементов состоит в том, чтобы искать их по отдельности. Более оптимальный алгоритм по числу сравнений получается при одновременном нахождении наибольшего и наименьшего элементов. Применяя прием «разделяй и властвуй», мы разбиваем множество S на два подмножества S 1 и S 2 по n/2 элементов в каждом. После этого рекурсивно нахо- дим наибольший и наименьшие элементы в каждой из двух половин. Наибольший и наименьший элементы множества S можно определить, произведя еще два срав- нения — наибольших элементов в S 1 и S 2 и наименьших элементов в них. Обозначим через max и min очевидные подпрограммы для нахождения наи- большего и наименьшего элементов из двух чисел: 7.3 Рекурсия и итерация. Метод накапливающего параметра 131 function max(а,b:integer):integer; function min(а,b:integer):integer; Части множества S, получающиеся в результате разбиения, в нашем представ- лении можно задавать парой индексов (i, j) — указывающих нижнюю и верхнюю границы подмассива. В этих обозначениях легко написать следующую рекурсивную процедуру. procedure maxmin(i,j:integer;var maxel,minel:integer); var max1,min1,max2,min2:integer; k:integer; begin if abs(i −j)<=1 then begin maxel:=max(x[i],x[j]); minel:=min(x[i],x[j]) end else begin k:=(i+j) div 2; maxmin(i,k,max1,min1); maxmin(k,j,max2,min2); maxel:=max(max1,max2); minel:=min(min1,min2) end end Для нахождения наибольшего M1 и наименьшего M 2 элементов множества S достаточно в главной программе обратиться к процедуре: maxmin(1,n,M1,M2). В нашем примере задача разбивалась на подзадачи равных размеров (точнее, почти равных размеров; идеальный был бы случай, когда n было бы степенью двойки). Это не было случайностью. Поддержание равновесия (балансировка) — основной руководящий принцип при разработке хорошего алгоритма. Разбиение задачи на подзадачи неравных размеров менее эффективно. 7.3 Рекурсия и итерация. Метод накапливающего параметра Известно, что любую рекурсивную программу можно преобразовать в эквива- лентную программу, не имеющую рекурсивных вызовов. И наоборот, для каждой программы, содержащей циклические вычисления (итерацию), существует эквива- лентная рекурсивная программа, не имеющая циклов. Таким образом, рекурсия и итерация являются взаимозаменяемы- ми методами программирования. 132 Глава 7. Рекурсия Отметим, что имеются языки программирования, в которых отсутствует итера- ция — ее заменяет рекурсия. К таким языкам относятся «чистые» функциональные языки (например, Haskell) и Пролог. Как и в итеративном случае, для решения конкретной задачи возможны раз- личные рекурсивные программы, некоторые из них могут быть неэффективны. Рассмотрим числа Фибоначчи. Пусть f (n) — n-ое число Фибоначчи, определя- емое с помощью рекуррентного соотношения f (n + 1) = f (n) + f (n − 1), для n > 0 и f (1) = 1, f (0) = 0. При непосредственном, «лобовом подходе» мы получаем программу: function f(n:integer):integer; begin if n=0 then f:=0 else if n=1 then f:=1 else f:=f(n −1)+f(n−2) end Эта программа неэффективна, так как каждое обращение к функции f при n > 1 приводит к двум дальнейшим обращениям, т. е. общее число обращений растет экспоненциально. Однако очевидно, что числа Фибоначчи можно вычислять по итеративной схе- ме, при которой использование вспомогательных переменных x = f (i) и y = f (i − 1) позволяет избежать повторного вычисления одних и тех же значений: {вычисление x=f(n) при n>0} i:=1;x:=1;y:=0; while i Но мы можем определить эффективную рекурсивную функцию для вычисле- ния чисел Фибоначчи, используя метод накапливающего параметра. Для ясности изложения запрограммируем сначала с помощью этого метода вычисление факто- риала: function fac(n:integer):integer; function facr(n,y:integer):integer; begin if n=0 then facr:=y else facr:=facr(n −1,y*n) end; begin fac:=facr(n,1) end Параметр y в данном случае называется накапливающим. Для вычисления чисел Фибоначчи нам понадобится два накапливающих параметра. function fib(n:integer):integer; function fiba(n,f1,f2:integer):integer; begin if n<2 then fiba:=f2 else fiba:=fiba(n-1,f2,f1+f2) 7.4 Рекурсия в своем блеске и великолепии 133 end; begin fib:=fiba(n,0,1) end; 7.4 Рекурсия в своем блеске и великолепии 7.4.1 Ханойские башни После примеров предыдущих разделов может сложиться мнение, что исполь- зование рекурсии излишне и предыдущие задачи можно было бы легко решить без рекурсии с помощью циклов. Для тривиальных задач это действительно так. В этом разделе рекурсия продемонстрирует всю свою мощь, красоту и необходимость. В конце 19 столетия в Европе появилась игра под названием «Ханойские баш- ни». Популярности игры содействовали рассказы о том, что этой игрой заняты служители храма брахманов и что завершение игры будет означать конец света. Предметы, которыми пользовались монахи, будто бы состояли из медной плат- формы с укрепленными на ней тремя алмазными иглами с насажанными 64-мя золотыми дисками. Цель игры — перенести башню с левой иглы на правую, при- чем за один раз можно переносить только одно кольцо, кроме того, запрещается помещать большее кольцо над меньшим (рис. 7.2). Рис. 7.2 – «Ханойские башни» Предположим, что иглы пронумерованы числами 1, 2 и 3 и что монахам надо перенести 64 диска с иглы 1 на иглу 3. Обозначим поставленную задачу таким образом: перенести башню(64,1,3) Наша цель будет заключаться в разработке алгоритма, который подскажет мона- хам последовательность корректных перемещений, в результате чего задача будет решена. К простому решению приводит догадка о том, что основное внимание нужно обратить на нижний диск иглы 1, а не на верхний. Задача «перенести баш- ню(64,1,3)» после этого оказывается эквивалентной следующей последовательно- сти подзадач: перенести башню(63,1,2); перенести диск с иглы 1 на иглу 3; перенести башню(63,2,3) 134 Глава 7. Рекурсия Это маленький, но значительный шаг к решению. Маленький, поскольку нам все еще надо дважды переносить по 63 диска. Значительный, потому что мы можем повторить подобный анализ столько раз, сколько будет необходимо. Например, задача перенести башню(63,1,2) может быть выражена как перенести башню(62,1,3); перенести диск с иглы 1 на иглу 2; перенести башню(62,3,2) Для построения общего алгоритма нам надо указывать, какой иглой можно пользоваться как временным хранилищем. Это можно сделать, расширив нашу запись так, чтобы перенести башню(n, a, b, c) значило бы перенести n дисков с иглы a на иглу b, используя иглу c для временной башни. Мы можем утверждать, что задача перенести башню(n, a, b, c) может быть решена за три шага: перенести башню(n − 1, a, c, b); перенести диск с a на b; перенести башню (n − 1,c,b,a). Этот алгоритм не имеет смысла для случая n < 1, поэтому добавляем правило: ничего не делать, если n < 1 Процедуру для действия «перенести диск» запишем в следующем виде: procedure transferDisk(from{откуда},where{куда}:integer); begin writeln(from, '--->',where) end Рекурсивную процедуру для действия «перенести башню» получаем в виде: procedure transferTower(n,from,where,work:integer); begin if n>0 then begin transferTower(n-1,from,work,where); transferDisk(from,where); transferTower(n-1,work,where,from) end end Пусть главная программа содержит операторы: read(disk); transferTower(disk,1,3,2) Тогда будем иметь Ввод : 3 Вывод : 1--->3 1--->2 7.4 Рекурсия в своем блеске и великолепии 135 3--->2 1--->3 2--->1 2--->3 1--->3 Математический анализ алгоритма показывает, что время, нужное програм- ме для переноса башни, состоящей из n дисков, пропорционально 2 в степени n. Современные вычислительные машины, решая задачу «Ханойские башни», могут вычислить (но не напечатать) одно перемещение за одну миллионную долю се- кунды. Даже при такой скорости для расчета переноса башни из 64-х дисков им потребуется около миллиона лет. 7.4.2 Поиск маршрута — алгоритм с возвратом Особенно интересный раздел программирования — это задачи из области «ис- кусственного интеллекта». Здесь нужно строить алгоритмы, которые находят реше- ния определенной задачи не по фиксированным правилам вычисления, а методом проб и ошибок. Обычно процесс проб и ошибок разделяется на отдельные подза- дачи. Часто эти подзадачи наиболее естественно описываются с помощью рекур- сии. Процесс проб и ошибок можно рассматривать в общем виде как поисковый процесс, который постепенно строит и просматривает (а также обрезает) дерево подзадач. Задача. Имеется n населенных пунктов перенумерованных от 1 до n. Некото- рые пары пунктов соединены дорогами. Определить, можно ли попасть по этим дорогам из 1-го пункта в n-ый, и напечатать маршрут. Информация о дорогах задается в виде матрицы A размером n ×n. Пункты i и j — соединены дорогой, если A[i,j]=1 (и A[j,i]=1), иначе — A[i,j]=0. Считаем также, что A[i,i]=0. type path=array[1..n] of 0..n; {представление маршрута; ненулевые элементы массива — пройденные населенные пункты в маршруте} procedure add(var p:path;k:integer); {добавление пункта в путь} var i:integer; begin i:=1; while (i p[i]:=k; end; function good(i:integer;p:path):boolean; {функция проверяет, принадлежит ли пункт i маршруту p} var j:integer; begin good:=true; for j:=1 to n do if p[j]=i then good:=false end; 136 Глава 7. Рекурсия procedure print (p:path); {печать маршрута p} var i: integer; begin for i:=1 to n do if p[i]<>0 then write(p[i], ' ') end; procedure search(p:path;x:integer); {x — населенный пункт, p — пройденный путь} var i:integer; begin if x=n then begin add(p,x);print(p) end else for i:=1 to n do if (A[x,i] =1) and good(i,p) then begin add(p,x);search(p,i) end end; var A:array[1..n,1..n] of 0..1; p:path; i:integer; begin {ввод матрицы A} for i:=1 to n do p[i]:=0; search(p,1) end. 7.4.3 Быстрая сортировка Рекурсия дает лучший из известных до сего времени метод сортировки мас- сивов. Он обладает столь блестящими характеристиками, что его изобретатель К. Хоар окрестил его быстрой сортировкой. Пусть дан массив целых чисел: var a:array[1..n] of integer; Попробуем рассмотреть следующий алгоритм: выберем случайным какой-то элемент массива (назовем его x), просмотрим массив, двигаясь слева направо, пока не найдем элемент a[i]>x, а затем просмотрим его справа налево, пока не найдем элемент a[j] procedure partition; var w,x:integer; begin i:=1;j:=n; выбор случайного элемента x; repeat while a[i] 7.4 Рекурсия в своем блеске и великолепии 137 if i<=j then begin w:=a[i];a[i]:=a[j];a[j]:=w; i:=i+1;j:=j-1 end until i>j end Заметим, что отношения > и < заменены на ⩾ и ⩽, отрицания которых в операто- ре цикла с предусловием — это < и >. При такой замене x действует как барьер для обоих просмотров. Если, например, в качестве x выбрать средний элемент, равный 42, из массива 44 55 12 42 94 6 18 67, то для того, чтобы разделить массив, потребуется два обмена элементов: 18 на 44 и 6 на 55: 18 6 12 42 94 55 44 67, конечные значения индексов равны i=5 и j=3. Элементы a[1],. . ., a[i − 1] меньше или равны x=42, элементы a[j+1],. . ., a[n] больше или равны x. Следовательно, мы получили два подмассива a[k] ⩽ x для k=1,. . ., i − 1 a[k] ⩾ x для k=j+1,. . ., n и, следовательно, a[k]=x для k=j+1,. . ., i − 1. Теперь нам пора вспомнить, что наша цель — не только разделить массив на большие и меньшие, но также рассортировать его. Однако от разделения до сорти- ровки всего небольшой шаг: разделив массив, нужно сделать то же самое с обеими полученными частями, затем с частями этих частей и т. д., пока каждая часть не будет содержать только один элемент. Этот метод представим программой: procedure quiksort; {быстрая сортировка массива a[i] целых чисел} type index:1..n; procedure sort(l,r:index); var i,j:index; w,x:integer; begin i:=l;j:=r; x:=a[(l+r) div 2]; repeat while a[i] if i<=j then begin w:=a[i];a[i]:=a[j];a[j]:=w; i:=i+1;j:=j −1 end until i>j; if l begin sort(1,n) end;{quiksort} |