Программирование с использованием рекурсии
Лабораторная работа
Программирование
с использованием рекурсии
Задание к лабораторной работе
Цель работы: освоить способы программирования алгоритмов с использованием
рекурсии.
Общие
сведения рекурсия - способ организации вычислительного процесса, при котором
подпрограмма в ходе выполнения составляющих ее операторов обращается сама к
себе.
Перед выполнением работы необходимо изучить способы описания и
использования рекурсивных процедур и функций.
Пример. Написать программу, содержащую подпрограммы, вычисляющий
с
использованием и без использования рекурсии.
Решение
SUMIR;n: Integer; SUM:Real;
{------- Рекурсивная процедура-функция -------------}
Function S_REC(n:word):Real;n=1 then S_REC:=4S_REC:=S_REC(n-1)+(n+1)*(n+1)/n;
{------- Процедура-функция без рекурсии ------------}
Function S(n:word):Real;i: byte; Sum: Real;:=4;i:=2 to n do
Sum:=Sum+(i+1)*(i+1)/i;:=Sum;
{----------- Рекурсивная процедура ----------------}
Procedure REC(n:word; Var S:Real);n=1 then
S:=4Begin(n-1,S);:=S+(n+1)*(n+1)/n;
{------------ Процедура без рекурсии ------------}
Procedure SS(n:word; Var S:Real);i: byte;:=4;i:=2 to n do
S:=S+(i+1)*(i+1)/i;;
{----------- Основная программа ----------------}
Begin
Write('n='); Readln(n);('Сумма равна');('1. Функция с рекурсией: ',S_REC(n):0:5);
REC(n,SUM);('3. Процедура c
рекурсией: ',SUM:0:5);
SS(n,SUM);('4. Процедура без рекурсии: ',SUM:0:5);
End.
рекурсия
алгоритм вычислительный
Контрольные
вопросы
. Что такое «рекурсия»?
. В чем преимущества и недостатки использования рекурсии?
Задачи
Решить поставленные задачи различными способами: с применением рекурсии и
без нее.
. Для заданного целого десятичного числа N получить его представление в p-ичной системе счисления (p<10).
. В упорядоченном массиве целых чисел ai, i=1...n найти номер элемента c используя метод двоичного поиска.
Предполагается, что элемент c
находится в массиве.
. Найти наибольший общий делитель чисел M и N.
Используйте теорему Эйлера: Если M
делится на N, то НОД (N, M)=N, иначе НОД (N, M)=
=НОД (M mod N, N).
. Вычислить число Фибоначчи Fb(n). Числа Фибоначчи определяются
следующим образом: Fb(0)=1; Fb(1)=1; Fb(n)=Fb(n-1)+Fb(n-2).
. Найти значение функции Аккермана A(m, n), которая определяется для всех
неотрицательных целых аргументов m и n следующим образом:
A(o, n)=n+1;(m, o)=A(m-1, 1); (m>o);(m, n)=A(m-1, A(m,
n-1)); (m>o; n>o).
6. Вычислить m-ю производную
полинома степени n
.
Вычислить значение , используя рекуррентную формулу
в
качестве начального приближения использовать значение x0=0.5(1+a).
.
Найти максимальный элемент в массиве a1...an, используя
очевидное соотношение max (a1...an)=max (max (a1...an-1), an).
.
Вычислить .
.
Вычислить
12.
Вычислить произведение n³2 (n-четное) сомножителей
.
Вычислить по следующему алгоритму: , если N четное; , если N
нечетное.
.
Вычислить n!.
15. Выполнить сортировку массива целых чисел ai, i=1, n с помощью разделения (QuickSort). См. Вирт Н., Алгоритмы и структура
данных.