Рекурсивные процедуры и функции
При вычислениях возможны случаи, когда подпрограмма обращается к себе самой. Такую ситуацию называют рекурсией.
Примером рекурсии служит подпрограмма вычисления факториала натурального числа:
function f(n:integer ):integer;
Begin
if n=0 then f:=1 else f:=f(n-1)*n;
end;
Обращение к данной функции, например, с фактическим параметром 3, влечет следующие действия.
f:=3*f(2) (первый шаг)
f:=2*f(1) (второй шаг)
f:=1*f(0) (третий шаг)
На первом и втором шагах вычисление откладывается, на третьем шаге f получает значение, равное 1, и происходит вычисление факториала в обратном порядке.
Любое рекурсивное описание должно содержать явное определение результата для некоторого значения аргумента (аргументов), которое будет обеспечивать завершение рекурсивных вызовов подпрограммы. В рассмотренном примере окончание вычислений обеспечивается оператором if n=0 then f:=1.
Примеры рекурсивных функций
Пример 10. Вычислить произведение двух целых положительных чисел с помощью рекурсивной функции, не используя цикл.
ProgramProg5_10;;
var a,b,pr:integer;
function p(a,b:integer ):integer;
Begin{Произведение чисел a и b представим как сумму из b чисел a, т. е. a*b= a*(b-1)+ a}
if b=1 then p:=a else p:=p(a,b-1)+a;
End;
Begin
writeln(‘введите два числа’);
readln(a,b);
pr:=p(a,b);
writeln(pr);
End.
Пример 11. Вычислить 
, используя рекурсивную функцию.
Решение этой задачи аналогично примеру 8 темы 3. Находим связь между предыдущим и следующим членами последовательности (рекуррентное соотношение). Член 
связан с 
соотношением: 
. Множитель, с помощью которого связаны два соседних члена последовательности, равен 
.
ProgramProg5_11;
var n:integer; x:real;
functions(x:real; n:integer; v:real;
k:integer):real; {n – количество слагаемых, v – множитель}
{k – номер очередного слагаемого}
Begin
if n=0 then s:=0 else begin
s:=s(x,n-1,v*x/k,k+1)+v; end; {к сумме предыдущего шага прибавляем очередное слагаемое. Значение очередного члена и его номер вычисляется рекурсивно через обращение к функции}
end;
Begin
writeln(‘введите x и n’);
readln(x,n);
writeln(s(x,n,1,1):11:5);
End.
При обращении к функции задаем в качестве начальных значений v = 1 и k = 1.
Пример 12. Вычислить 
, с точностью ε.
Отличие этой программы от предыдущей в том, что вместо количества слагаемых задаем точность вычислений. Поэтому выход из рекурсии выполняется по условию v< ε.
ProgramProg5_12;
conste=0.001;
var x,f:real;
functions(x,e:real; v:real; k:integer):real;
Begin
if v<e then s:=0 else s:=s(x,e,v*x/k,k+1)+v;
end;
Begin
writeln(‘введите x’);
readln(x);
f:=s(x,e,1,1);
writeln(f:11:5);
End.
Пример 13. С помощью рекурсивной функции вычислить цепную дробь:
Рекуррентное соотношение состоит в следующем: если вычислена цепная дробь из n-1 элемента, то чтобы вычислить дробь, содержащую на один элемент больше, нужно 1 разделить на полученную дробь и прибавить к k.
ProgramProg5_13;
var k,n:integer; c:real;
function t(k,n:integer):real;{n – количество элементов дроби}
Begin
if n=1 then t:=k else t:=k+1/t(k,n-1);
end;
Begin
readln(k,n);
c:=t(k,n);
writeln(c:11:5);
End.
Контрольные вопросы:
1. В каких случаях используются подпрограммы?
2. В чем отличие между процедурой и функцией, для каких задач каждая из них предназначена?
3. Какая существует связь между формальными и фактическими параметрами?
4. В чем особенности механизма передачи параметров – значений и параметров переменных?
5. Какие типы можно использовать для описания значения функции?
6. Что представляет собой рекурсивный алгоритм?
7. В чем особенности описания рекурсивной функции? Как обеспечивается конечность рекурсивного алгоритма?
8. Как реализовать циклический алгоритм с помощью рекурсивной функции без оператора цикла? Что такое рекурсия с накапливающимся параметром?
Лабораторная работа № 5
Задание 1. Составьте программу с использованием процедуры – функции. Выполните ее тестирование и отладку.
Варианты заданий:
1. Для заданного вектора 
вычислить величину:
2. Определить количество дней в месяце по его порядковому номеру. Учесть високосные года.
3. Вычислить сумму значений функции:
z = f(|x|,y)+f(a,b)+f(|x|+1,-у)+f(|x|-|y|,x)+f(x+у,а+b),
где 
4. Найти наименьшую сторону треугольника, заданного координатами своих вершин.
5. Даны действительные числа s и t. Получить:
z=h(s,t)+max(s-t,st)+h(t,t),
где h(a,b)=a/(1+ b2)-(a-b)3.
6. По заданному значению величины x определить, имеет ли функция
значение, и найти его.
7. Вычислить значения функции y=ax2+bx+d, где
используя функцию 
.
8. Пусть элементами круга являются радиус (1-й элемент), диаметр (2-й элемент), длина окружности (3-й элемент). По номеру одного из перечисленных элементов и его значению вычислить площадь круга.
9. Вычислить корни x и у системы уравнений:
.
10. Вычислить площади треугольника по координатам его вершин.
11. Вычислить величину:
,
используя функцию 
.
12. Даны действительные числа s и t, получить:
где 
13. Составить процедуру-функцию для вычисления определителя третьего порядка. Описать матрицу коэффициентов как двумерный массив.
14. Проверить, верна ли гипотеза Гольдбаха о том, что каждое четное n > 2, представляется в виде суммы двух простых чисел.
15. В произвольном массиве найти наиболее часто повторяющееся число. Оформить функцию вычисления количества повторений одного числа. Дополнительных массивов не использовать.
Задание 2. Составьте программу с использованием рекурсивной подпрограммы для решения следующей задачи:
Варианты заданий:
1. Найти сумму ряда с заданной точностью e, общий член которого имеет вид:
2. Вычислить n-ый член последовательности, общий член которой имеет вид:
3. Последовательность чисел задана соотношениями:
.
Вычислить n-ый член последовательности.
4. Вычислить tg x с заданной точностью e по формулам:
.
5. Вычислить для заданных x и n:
6. Найти n-ый член последовательности, заданной соотношениями:
.
7. Вычислить значение суммы членов бесконечного ряда
с точностью до члена ряда, меньшего по модулю e.
8. Вычислить приближенное значение кубического корня из а, используя соотношение:
.
9. Для вещественного х (х<>0) и целого n вычислить xn согласно формуле:
10. Найти произведение 
для заданных a и n.
11. Даны неотрицательные целые числа n, m; вычислить A(n,m) – функцию Аккермана, где
12. Вычислить ln x, пользуясь формулами:
e – заданная точность.
13. Для заданного M ³ m ³ n >0 вычислить все биномиальные коэффициенты Cmn по формулам:
14. Вычислить определитель заданной матрицы, пользуясь формулой разложения по первой строке (матрица B получается вычеркиванием из A первой строки и k-го столбца):
15. Вычислить по формуле:
, где 
, 
Задание 3. Составьте программу с использованием процедуры для решения следующей задачи:
Варианты заданий:
1. Найти наименьшие элементы двух различных матриц произвольной размерности.
2. «Сожмите» одномерные массивы размерности m и n, удалив из них нулевые элементы.
3. Найти сумму диагональных элементов матриц A и В.
4. В двух целочисленных последовательностях различной длины замените все элементы, следующие за элементом с максимальным значением, на значение минимального элемента.
5. Вычислить 
, где 
– корни уравнения 2x2+x – 4=0, 
– корни уравнения 3y2+2y – 1=0.
6. Напишите процедуру для объединения двух упорядоченных линейных массивов в один упорядоченный. Объедините три массива размерности m, n, k.
7. Определить, в каком из двух заданных массивов натуральных чисел больше палиндромов (чисел, которые читаются одинаково как с начала, так и с конца, например, 313, 66).
8. Вычислить:
,
где 
и 
заданы массивами. Все суммы поочередно вычислять одной процедурой.
9. Вычислить В*А*С. Произведение двух матриц находить в процедуре.
10. Вычислить 
, где 
– максимальный элемент массива X(n); 
– минимальный элемент массива Y(m). Элементы и вычислять одной процедурой.
11. Два двумерных массива различной размерности преобразуйте в линейные.
12. Заданы координаты вершин n треугольников. Выяснить, сколько из них прямоугольных, равносторонних и равнобедренных. Определение вида треугольника оформить в виде процедуры.
13. Найти сумму минимумов дополнительных миноров диагональных элементов матрицы.
14. В двух двумерных массивах найти наиболее часто повторяющиеся элементы.
15. Симметричная двумерная матрица представлена своим верхним треугольником в виде линейного массива. Преобразуйте два линейных массива произвольной размерности в симметричные матрицы.
6. СТРОКИ
Цель: выработка навыков использования строковых переменных для обработки текстовой информации.
Структура строки в Паскале
Строка есть последовательность символов языка Паскаль. В выражениях константу-строку заключают в апострофы.
Формат описания строки:
var<идентификатор1>, …:string[<длина строки>];
<длина строки> – количество символов в строковой переменной. Число символов не может превышать 255. Фактическая длина строки может быть короче указанной в описании. Длину строки можно не указывать. В этом случае ее длина будет предельной – 255 символов. Для хранения строки в памяти отводится количество байтов на 1 больше длины строки. В нулевом байте хранится реальная длина строки. Доступ к элементам строки – символам – осуществляется так же, как к элементам массива, с помощью индекса, который записывается в квадратных скобках за идентификатором строковой переменной.
Примеры описания строк:
constslovo = ‘massiv’;
frasa = ‘Я пишу программу’;
typesubekt = string[30];
varB,A : subekt;
fio : string[30];
text: string;
Над строками определена операция соединения (конкатенации) «+». Она соединяет две строки в одну результирующую строку.
Пример 1.
Выражение Результат
'Дом '+'номер'+' 5/43' 'Дом номер 5/43'
Строки можно сравнивать. При сравнении двух срок символы сравниваются слева направо по значению их ASCII-кода. Строки равны, если их длины и содержание одинаковы.
Пример 2.
Выражение Результат
'akkord'>'AKKORD' true
'Принтер '<'Принтер' false
'XXX'>'XX' true
Если значение переменной после выполнения оператора присваивания больше заданной длины строки, то все лишние символы справа отбрасываются.
Пример 3.
var Str1,Str2: string[20];
Str1 := 'Группа учащихся';
Str2 := Str1 + ' первого курса';
Значение Str2 окажется равным 'Группа учащихся перв'.
Допускается использование в одном выражении операндов строкового и символьного типа.
Пример 4.
var s1,s2:string[20]; ch:char;
………………………………………………………………………………
s1:= ‘учусь’; ch:= ‘Я’; s2:=ch+s1; {возможные действия}
ch:=s1; {ошибка}