| Назад | Содержание | Вперед |
При создании программы для решения сложной задачи программист обычно разбивает ее на подзадачи, чтобы для каждой такой подзадачи написать подпрограмму, а затем объединить все написанные подпрограммы в программу. Если подзадача достаточно сложная, то для решения может оказаться полезным разбить ее еще на более мелкие подзадачи и программировать каждую из них отдельно и т. д. Часто бывает, что в процессе такого разбиения задача сводится к самой себе. Если при этом исходные данные становятся проще, то этот процесс можно продолжать до тех пор, пока исходные данные не окажутся настолько простыми, что решение задачи для них станет тривиальным. Приведем примеры, демонстрирующие такой принцип решения.
Перевод десятичного натурального числа в двоичное
Напишем сценарий, который для любого натурального числа строит его двоичное представление.
Опишем функцию recbin , которая получает в качестве параметра целое положительное число n, и формирует строку, являющуюся двоичным представлением n. Эту задачу можно свести к самой себе. Если в двоичном представлении п содержится k>o двоичных цифр, то первые k-i цифр представляют число, являющееся частным от деления п на 2, а последнюю цифру легко узнать, проверив четность числа п. Если к=1, то n=1, то и двоичное представление п равно 1, и этот случай рассмотрим отдельно. В теле функции recbin есть обращение к ней самой, но с другими, более простыми параметрами. При каждом вызове функции значение параметра уменьшается, поэтому наступит момент, когда параметр станет равным 1 и решение задачи будет тривиальным.
HTML-код приведен в листинге 16.1.
Листинг 16.1. Рекурсивные методы. Двоичное представление числа
<HTML>
<HEAD>
<TITLE>Рекурсивные методы. Двоичное представление числа</TITLE>
<script language="JavaScript">
<!-—
function recbin(n)
{ var s
if (n==l) s="l"
else
{ s=recbin((n-n%2)/2)
s+=n%2
}
return s
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Рекурсивные методы. Двоичное представление числа</Н4>
<FORM name="form1">
<pre>
Введите натуральное число: <input type="text" size=12 name="num">
Двоичное представление: <input type="text" size=12 name="res">
</pre>
<input type="button" value=Bыпoлнить
onClick = "this. form. res. value = recbin (Number (this. form. num. value ))">
<input type="reset" value=0тменить>
</FORM>
</BODY>
</HTML>
Вычисление факториала рекурсивным методом
Напишем программу, которая по любому натуральному п вычисляет п! так, как показано на рис. 16.1.
|
|
| Рис 16.1. Факториал натурального числа |
Мы уже решали подобную задачу при демонстрации итеративных методов. Опишем рекурсивную функцию вычисления факториала. В функции один параметр — натуральное число п. Тривиальный случай — это вычисление значения 1!. Заметим, что верно следующее соотношение п! = п х (п — 1)!, поэтому можно свести задачу вычисления п\ к решению той же задачи, но с другим, более "простым" параметром.
HTML-код представлен в листинге 16.2.
Листинг 16.2. Рекурсивные методы. Вычисление факториала
<HTML>
<HEAD>
<TITLE>Рекурсивные методы. Вычисление факториала</TITLE>
<script language="JavaScript">
<!-— //
function fact(n)
{ var f=1
if (n=l) f=l
else f=n*fact(n-1)
return f
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Рекурсивные методы. Вычисление факториала</Н4>
<FORM name="form1">
<pre>
Введите натуральное число: <input type="text" size=20 name="num"><hr>
Значение факториала равно: <input type="text" size=20 name="res"><hr>
</pre>
<input type="button" value=Bьmoлнить
onClick="this.form.res.value=fact(this.form.num.value)">
<input type="reset" value=Отменить>
</FORM>
</BODY>
</HTML>
Пусть
n=3
. Как будет выполняться вызов
fact(n)
? На рис. 16.2 представлена схема выполнения вызова функции. Стрелки указывают порядок вычисления. Сначала происходит движение по стрелкам вниз, указывающее на то, что происходит временное прерывание выполнения текущего вызова, и переход к выполнению вызова более низкого уровня, пока не будет получен тривиальный случай. Затем происходит подъем вверх, что означает возобновление прерванных вызовов. Первым возобновится выполнение такого вызова, который был прерван последним.
|
| Рис 16.2. Схема выполнения вызова рекурсивной функции |
Определение чисел Фибоначчи рекурсивным методом
Напишем рекурсивную функцию, определяющую число Фибоначчи с номером n. По определению последовательности чисел Фибоначчи:
f 0 = f 1 = 1;
f i = f i - 1 + f i - 2 при i >= 2 .
Можно написать функцию, основываясь на только что приведенном определении:
function fib(p,s,n)
( var r
if (n<=0)
{r=s}
else
(r=fib(n-l) + fib(n-2)}
return r
}
В теле рекурсивной функции fib есть два обращения к ней самой с параметром п-1 и п-2. При вычислении fib(n-1) будет вычисляться fib(n-2), a затем значение это будет "забыто" и вычисляться заново при следующем рекурсивном вызове.
Для того чтобы избежать многих повторных вызовов используют прием, который получил название "накапливаемые" параметры. В рекурсивной функции reef ib три параметра: два последних определенных числа Фибоначчи и номер того числа, которое нас интересует. В теле функции вызов recfib (s, s+p,n-i) означает переход к следующей паре полученных чисел Фибоначчи (параметры s и s+p), и тот факт, что номер искомого числа относительно найденных уменьшился на 1.
function reefib(p,s,n)
{ var r
if (n <=0) {r=s}
else
{ r=recfib(s,s+p,n-l) }
return r
}
Для того чтобы найти число Фибоначчи п с помощью функции recfib, надо выполнить вызов recfibd, i,n-l). Приведем полностью программу решения задачи (листинг 16.3).
Листинг 16.3. Рекурсивные методы. Числа Фибоначчи
<HTML>
<HEAD>
<TITLE>Рекурсивные методы. Числа Фибоначчи</TITLE>
<script language="JavaScript">
<!-—
function recfib(p,s,n)
{ var r
if (n <=0) {r=s}
else
{ r=recfib(s,s+p,n-l) }
return r
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Рекурсивные методы. Числа Фибоначчи</Н4>
<FORM name="forml">
<pre>
Введите номер числа: <input type="text" size=8 name="num">
Число в последовательности Фибоначчи: <input type="text" size=8 name="res">
</pre>
<hr>
<input type="button" value=Bьшoлнить
onClick="this.form.res.value=recfib(1,1,
Number(this.form.num.value-1))">
<input type="reset" value=0тменить>
</FORM>
</BODY>
</HTML>
Вычисление наибольшего общего делителя
Напишем программу, которая для двух заданных натуральных чисел определяет их наибольший общий делитель.
Рекурсивная функция nod имеет два параметра — числа n и m. Будем считать, что n>m. Если это не так, то параметры можно поменять местами. Если m = 0, то задача решена, наибольший общий делитель совпадает со значением n. Сведение задачи к подзадаче основано на следующем соотношении:
nod(n,m)=nod(m,n%m)
Первый и второй параметры уменьшаются при каждом рекурсивном вызове, поэтому наступит момент, когда значение второго параметра станет равным о. Полностью текст программы приведен в листинге 16.4.
Листинг 16.4. Рекурсивные методы. Вычисление наибольшего общего делителя
<HTML>
<HEAD>
<TITLE>Рекурсивные методы.
Вычисление наибольшего общего делителя</TITLE>
<script language="JavaScript">
<!-— //
function nod(n, m)
{ var r
if (m==0) r=n
else r = nod(m, n%m)
return r
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Рекурсивные методы. Вычисление наибольшего общего делителя</Н4>
<FORM name="forml">
<pre>
Число1: <input type="text" size=10 name="numl"><hr>
Число2: <input type="text" size=10 name="num2"><hr>
Наибольший общий делитель: <input type="text" size=10 name="res">
</pre><hr>
<input type="button" value=Выполнить
onClick="this.form.res.value=nod(this.form.numl.value,
this.form.num2.value)">
<input type="reset" value=Отменить>
</FORM>
</BODY>
</HTML>
Вычисление корня уравнения методом половинного деления с помощью рекурсии
Напишем рекурсивную процедуру поиска корня уравнения вида f(x) = 0 на промежутке [а, b] методом деления отрезка пополам.
Предположим, что функция на отрезке [а, b] непрерывна и монотонна и принимает на концах отрезка значения разных знаков.
Рекурсивная функция fbin зависит от трех параметров а, b и eps. Тривиальный случай состоит в том, что длина исследуемого отрезка меньше заданного значения eps. В этом случае любую точку отрезка можно принимать за приближенное значение корня. Если длина исследуемого участка более eps, то находится середина отрезка с и вычисляется значение функции f(с). В зависимости от значения f(c) продолжать поиск корня следует либо в промежутке [а, с] , либо в [с, b] . Если на концах промежутка [а, с] значения функции противоположных знаков, то поиск корня осуществляется на этом промежутке с помощью рекурсивного вызова fbin (а, с, eps) , в противном случае нахождение корня обеспечит вызов fbin (а, с, eps) .
В листинге 16.5 описана функция ftest, которая осуществляет дополнительную проверку, вычисляя значения функции в найденной точке.
Листинг 16.5. Рекурсивные методы. Метод деления отрезка пополам
<HTML>
<HEAD>
<TITLE>Рекурсивные методы. Метод деления отрезка пополам</TITLE>
<script language="JavaScript">
<!-—//
function fbin (a,b,eps)
{ var fs=forml.func.value
var x=a
var fa=eval(fs)
x=b
var fb=eval(fs)
var fc
var с
var r
if (Math.abs(b-a) < eps)
{ r= (a+b)/2 }
else
{ c=(a+b)/2;
x=c; fc=eval(fs)
if (fa*fc < 0)
{ r=fbin(a,c,eps) }
else
{ r=fbin(c,b,eps) }
}
return r
}
function ftest(obj)
( var fs=forml.func.value
var x=obj.res.value
var tes=eval(fs)
obj.test.value=tes
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Нахождение корня уравнения вида <i>f</i>(<i>x</i>)=0
методом деления отрезка пополам</Н4>
<FORM name="form1">
<pre>
Введите функцию: <input type="text" size=30
name="func"><hr>
Введите левую границу отрезка: <input type="text" size=10 name="l"><hr>
Введите правую границу отрезка: <input type="text" size=10 name="r"><hr>
Задайте требуемую точность: <input type="text" size=10 name="eps"><hr>
<input type="button" value=Вычислить
onclick="form1.res.value=fbin(1*form1.l.value,1*form1.r.value,
l*form1.eps.value)">
<hr>
Корень уравнения равен: <input type="text" size=30 name="res"><hr>
<input type="button" value=" Тест " onClick="ftest(forml)"><hr>
Тест: <input type="text" size=30 name="test"><hr>
<input type="reset" value=Отменить>
</pre>
</FORM>
</BODY>
</HTML>
Для уравнения
х
4
+ 2x
3
- 2 =
0 все условия, при которых можно применять метод деления отрезка пополам, выполнены для интервала [0, 1]. Результат работы программы приведен на рис. 16.3.
|
| Рис 16.3. Рекурсивная функция нахождения корня уравнения |
Рассмотренные примеры показывают, что в ряде случаев можно получить короткую и выразительную программу, если строить рекурсивный алгоритм для решения задачи. Для продемонстрированных примеров, однако, существуют не очень сложные алгоритмы решения без применения рекурсии. Рассмотрим задачу, для которой легко предложить рекурсивный алгоритм решения, в то время как нерекурсивный алгоритм был бы сложным и искусственным.
Рассмотрим решение задачи, которая получила название "Задача о Ханойских башнях". Существует древнеиндийская легенда, согласно которой в городе Бенаресе под куполом главного храма, в том месте, где находится центр Земли, на бронзовой площадке стоят три алмазных стержня. В день сотворения мира на один из этих стержней было надето 64 кольца. Бог поручил жрецам перенести кольца с одного стержня на другой, используя третий в качестве вспомогательного. Жрецы обязаны соблюдать условия:
1. Переносить за один раз только одно кольцо;
2. Кольцо можно переносить с одного стержня (х) на другой (у), только если оно имеет меньший диаметр, чем верхнее кольцо, находящееся на стрежне у, или стержень у свободен.
Согласно легенде, когда, соблюдая все условия, жрецы перенесут все 64 кольца, наступит конец света.
На рис. 16.4 изображена ситуация, когда требуется перенести 7 колец.
|
| Рис 16.4. Ситуация при переносе семи колец |
Кольцо со стержня А можно перенести на стержень В или С, кольцо со стержня В можно перенести на стержень С, однако, нельзя перенести его на стержень А.
Задача состоит в том, чтобы определить последовательность минимальной длины переноса колец. Решением задачи будем считать последовательность допустимых переносов, каждый из которых имеет вид х - у, где х и у одно из обозначений: А, В или С. Если кольцо всего одно, то задача решается за один перенос А - В. Для перемещения двух колец требуется выполнить три действия: А - С, А - В, С - В. Решение задачи для трех колец содержит семь действий, для четырех — 15.
Напишем рекурсивную функцию, которая находит решение для произвольного числа колец. Функция имеет четыре параметра, первый параметр — число переносимых колец, второй параметр — стрежень, на который первоначально нанизаны кольца. Третий параметр функции — стержень, на который требуется перенести кольца, и, наконец, четвертый параметр — стержень, который разрешено использовать в качестве вспомогательного. Последовательность переноса « колец изображена на рис. 16.5.
|
| Рис 16.5. Схема решения задачи о Ханойских башнях |
Чтобы перенести п колец со стержня х на стержень у, используя стрежень z в качестве вспомогательного (рис. 16.5, г), можно поступить следующим образом:
При переносе n - 1 кольца можно воспользоваться тем же алгоритмом, т. к. на нижнее кольцо с самым большим диаметром можно просто не обращать внимания. Перенос одного кольца в программе выражается в том, что выводится соответствующий ход.
HTML-код, содержащий описанный сценарий, приведен в листинге 16.6.
Листинг 16.6. Задача о Ханойских башнях
<HTML>
<HEAD>
<TITLE>Задача о Ханойских башнях</TITLE>
<script language="JavaScript">
<!-—
function hb(n,x,y,z)
{ if (n>0)
{ hb (n-1,x,z,y);
document.writeln ("<P>", x, " -> ",y);
hb (n-l,z,y,x);
}
}
//-—>
</script>
</HEAD>
<BODY>
<Н4>Решение задачи о Ханойских башнях</Н4>
<FORM name="form1">
<pre>
Введите число колец: <input type="text" size=5 name="stl"><hr>
Введите начальный стержень: <input type="text" size=5 name="st2"><hr>
Введите конечный стержень: <input type="text" size=5 name="st3"><hr>
Введите вспомогательный стержень: <input type="text" size=5 name="st4"><hr>
</pre>
<input type="button" value=Выполнить
onClick="hb(form1.st1.value,form1.st2.value,
form1.st3.value,form1.st4.value)">
<input type="reset" value=Отменить>
</FORM>
</BODY>
</HTML>
Оценим, сколько переносов будет сделано и сколько шагов выведено при работе программы. Обозначим Т п - число ходов, необходимых для переноса п колец. Очевидно, что Т 0 = 0, Т п = 2 х Т п-1 + 1 при n>0 , отсюда получаем:
Т п = 2 n - 1
Т 64 = 2 64 - 1 = 2 x 10 19
Если считать, что на перенос одного кольца потребуется одна секунда, то на перенос всех колец потребуется более 5 млрд веков.
1. Напишите рекурсивную функцию summ(s,i, j) , проверяющую, является ли симметричной часть строки s, начинающаяся i-м и заканчивающаяся i-м ее элементами.
2. Напишите рекурсивную функцию, "переворачивающую" заданное натуральное число.
3. Напишите рекурсивную функцию, которая по последовательности литер, представляющих двоичное число, определяет соответствующее десятичное число.
4. Напишите рекурсивную функцию, вычисляющую n!!.
5. Напишите рекурсивную функцию, определяющую количество единиц в двоичном представлении натурального числа.
6. Напишите рекурсивную функцию, которая по заданным натуральным числам m и п выводит все различные представления числа « в виде суммы m натуральных слагаемых. Представления, различающиеся лишь порядком слагаемых, считаются одинаковыми.
7. Напишите рекурсивную функцию, которая формирует в обратном порядке текст, задаваемый пользователем в текстовом поле формы.
8. Напишите рекурсивную функцию для вычисления биномиального коэффициента C.
9. Напишите рекурсивную функцию, проверяющую, является ли последовательность символов идентификатором. Напомним, что идентификатором будем считать последовательность букв и/или цифр, начинающуюся с буквы.
10. В последовательности символов могут встречаться только цифры и знаки + (плюс), при этом последовательность представляет собой формулу сложения однозначных чисел. Напишите рекурсивную функцию, определяющую значение формулы.
11. В последовательности символов могут встречаться только цифры и знаки + (плюс) или - (минус), при этом последовательность представляет собой формулу арифметической суммы однозначных чисел. Напишите рекурсивную функцию, определяющую значение формулы.
| Назад | Содержание | Вперед |