Программирование с использованием рекурсии
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Лабораторная работа
Программирование с использованием рекурсии
Задание к лабораторной работе
Цель работы: освоить способы программирования алгоритмов с использованием рекурсии.
Общие сведения рекурсия - способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Перед выполнением работы необходимо изучить способы описания и использования рекурсивных процедур и функций.
Пример. Написать программу, содержащую подпрограммы, вычисляющий
с использованием и без использования рекурсии.
Решение
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);
Writeln(2. Функция без рекурсии: ,S(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).
. Найти максимальный элемент в массиве a1...an, используя соотношение (метод деления пополам) max (a1...an)=max (max (a1...an/2), max (an/2+1, an)).
. Вычислить .
. Вычислить
12. Вычислить произведение n2 (n-четное) сомножителей
. Вычислить по следующему алгоритму: , если N четное; , если N нечетное.
. Вычислить n!.
15. Выполнить сортировку массива целых чисел ai, i=1, n с помощью разделения (QuickSort). См. Вирт Н., Алгоритмы и структура данных.