Перейти на главную страницу
Рекурсивным называют любой объект, частично определяемый через такой же объект. Рекурсивной называется подпрограмма, которая вызывает саму себя. Такая рекурсия называется прямой. Существует ещё косвенная рекурсия, когда две или более подпрограммы вызывают друг друга. Далее мы будем рассматривать только прямую рекурсию.
Классическим примером рекурсивной подпрограммы является вычисление факториала. Факториалом натурального числа (обозначается
) называется произведение первых
натуральных чисел. Дополнительно полагается, что 0!=1.
Это же определение можно переписать рекурсивно, определив факториал через факториал от меньшего числа
Таким образом, чтобы вычислить 3!, надо вычислить 2!, чтобы вычислить 2!, надо вычислить 1!, чтобы вычислить 1!, надо вычислить 0!, а вот 0! вычисляется непосредственно.
Программа вычисления факториала может выглядеть следующим образом:
{$mode delphi}
Program Sample1;
//Рекурсивная функция
Function Fact(n : Int64) : Int64;
Begin
Then Fact:=1 //Нерекурсивная ветвь
Else Fact:=n*Fact(n-1) //Рекурсия
End;
Begin
Read(n);
End.
Таким образом, для построения рекурсивной подпрограммы надо свести решаемую задачу к самой себе, но при других значениях параметров, а также предусмотреть условие выхода из рекурсии. Покажем это на примерах.
Для однозначного сумма цифр числа равна самому
. Для остальных же
легко свести задачу к вычислению суммы цифр числа, полученного зачёркиванием у исходного последней цифры.
Всё! Более при разработке алгоритма ни о чём думать не нужно. Разбираться, как это будет работать, на первых порах не стоит. Только запутаемся. Пишем программу. Учитываем, что m может быть велико, а вот сумма его цифр не превышает .
Program SummDigit;
Function summ(m : Int64) : Byte;
Begin
If m<10 Then summ := m
End;
Begin
Read(a);
End.
Мы уже решали эту задачу с использованием циклического алгоритма (см. занятие 5). Теперь получим рекурсивное решение. Пусть . Тогда
В этом рекурсивном определении первая строка применяется для сведения нечётного показателя степени к чётному. Во второй строке сформулирована основная идея сокращения вычислений: вместо возведения в чётную степень
быстрее возвести
в степень
. Постепенно уменьшаясь при выполнении первых двух строк,
станет равным нулю. Тогда и произойдёт выход из рекурсии. Пишем программу.
Program Power;
Function QPow(x : Extended; n : Integer) : Extended;
Begin
If odd(n) Then
Else If n=0 Then
QPow:=1
Else QPow := QPow(x*x,n div 2)
Var x,y : Extended;
n : Integer;
Begin
Read(x);
Read(n);
WriteLn(x:0:5,'^',n,'=',y:0:5)
End.
Вспомните, что функция odd(n) возвращает значение true, если n — нечётное число.
Вспомним алгоритм перевода записи натурального числа в двоичную систему счисления на примере числа 510. Будем делить это число и все получаемые частные на 210, пока не получим в частном ноль. Потом все остатки запишем в обратном порядке.
5 |
2 |
|
|
1 |
2 |
2 |
|
|
0 |
1 |
2 |
|
|
1 |
0 |
Можно заметить, что для того, чтобы перевести в двоичную систему число 510, мы должны перевести в двоичную систему число 5 div 2 и приписать в конец число 5 mod 2. Это даёт возможность построить рекурсивный алгоритм. Условие выхода из рекурсии — если число меньше двух, то его запись в двоичной системе счисления будет иметь тот же вид, что и в десятичной.
{$mode delphi}
Program Notation;
Const BASE=2; //Основание системы счисления
Procedure Numeration(n : Int64);
Begin
If n >=BASE Then
Write(n mod BASE)
End;
Var n : Int64;
Write('Введите натуральное число ');
Read(n);
Numeration(n);
WriteLn //Чтобы опустить курсор на новую строку
End.
Если , то решение задачи очевидно: надо просто перенести один стержень. В противном случае переносим пирамиду из верхних
кольца со стержня A на промежуточный стержень C, нижнее кольцо переносим со стержня A на стержень B, а потом со стержня C переносим всю находящуюся там пирамиду на стержень B. Этими рассуждениями мы свели задачу переноса пирамиды из N колец к задачам переноса пирамиды из
кольца.
При написании рекурсивной подпрограммы учтём, что количество ходов может быть большим и на экране не обозримым. Поэтому выводить будем в файл. Перенос кольца со стержня A на стержень B будем обозначать .
{$mode delphi}
//Ханойские башни
Program Hanoi;
Var f : Text;
Procedure Move(N : Byte; otkuda, kuda, cherez : char);
Begin
If N=1 Then
Else Begin
Move(N-1,otkuda,cherez,kuda);
WriteLn(f,otkuda,'-->',kuda);
Move(N-1,cherez,kuda,otkuda)
End
Var n : Byte;
Begin
Assign(f,'Hanoi.in');
Read(f,n);
Close(f);
Assign(f,'Hanoi.out');
Rewrite(f);
Move(n,'A','B','C');
Close(f)
End.
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
Пример. Для входного файла, соответствующего таблице 1, ответом будет число 5 (длина жёлтого или зелёного связных кусков).
Приступим к разработке функции Count.
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Таким образом, функция Count получается рекурсивной.
Чтобы каждый элемент матрицы , равный 1, имел соседей со всех сторон, окружим исходную матрицу «забором» из нулей (см. таблицу 2). «Забор» показан серым цветом.
Наличие «забора» освобождает от необходимости проверки выхода за пределы массива при обработке матрицы .
Пишем программу.
{$mode delphi}
Program Kusok;
Const MAXSIZE=30;
Type TIndex=0..MAXSIZE+1;
TMatrix = array[TIndex,TIndex] of 0..1;
Var a : TMatrix; //Глобальная матрица
//Вычисление длины связного куска, содержащего a[row,col]
Function Count(row,col : TIndex) : Integer;
Begin
Count:=0
a[row,col]:=0; //Разрываем связный кусок
Count:=1+Count(row-1,col)+Count(row+1,col)+
Count(row,col-1)+Count(row,col+1)
//А может, здесь сделать a[row,col]:=1 ?
End
//Ввод данных
Procedure Input(out a : TMatrix; out M,N : TIndex);
Var f : Text;
i,j : TIndex;
Begin
Reset(f);
Read(f,M,N);
For i:=1 To M Do
For j:=1 To N Do
Read(f,a[i,j]);
Close(f);
//Обносим матрицу "забором" сверху и снизу
For i:=0 To N+1 Do
Begin
a[M+1,i]:=0
End;
//Теперь слева и справа
Begin
a[i,N+1]:=0
End
End;
Var max,len : Integer;
i,j : TIndex;
M,N : TIndex;
f : Text;
Begin
max:=0;
For j:=1 To N Do
Begin
len:=Count(i,j);
max:=len
Assign(f,'output.txt');
Rewrite(f);
Write(f,max);
Close(f)
End.
По этой же причине, ради экономии времени, матрица обносилась забором, а не заполнялась нулями полностью перед вводом данных. Хотя для маленьких матриц это и не существенно.
Рекурсивной называется подпрограмма, которая вызывает саму себя. Такая рекурсия называется прямой. Существует ещё косвенная рекурсия, когда две или более подпрограммы вызывают друг
06 10 2014
1 стр.
Если взять отдельное хозяйство, например, схпк «Янгорчино», то его развитие к 2020 году будет выглядеть следующим образом
16 12 2014
1 стр.
Матрица, после приведения к треугольному виду может быть записана следующим образом…
16 12 2014
1 стр.
Рынок маломерных судов может быть сегментирован по стоимости готового изделия (ценовой критерий) следующим образом
07 10 2014
6 стр.
Таким образом, электротравма представляет собой поражение организма под действием электрического тока
11 10 2014
1 стр.
Кіріспе Delphi ортасы туралы түсінік
14 12 2014
4 стр.
Семинар I. Как может выглядеть позитивистская исследовательская установка в середине ХХ века: Структурализм и семиотика на примере анализа киноискусства
11 10 2014
1 стр.
16 12 2014
1 стр.