Рекурсивные процедуры и функции

 

При вычислениях возможны случаи, когда подпрограмма обращается к себе самой. Такую ситуацию называют рекурсией.

Примером рекурсии служит подпрограмма вычисления факториала натурального числа:

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. Вычислить произведение двух целых положительных чисел с помощью рекурсивной функции, не используя цикл.

Program Prog5_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. Находим связь между предыдущим и следующим членами последовательности (рекуррентное соотношение). Член связан с соотношением: . Множитель, с помощью которого связаны два соседних члена последовательности, равен .

Program Prog5_11;

var n:integer; x:real;

function s(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< ε.

Program Prog5_12;

const e=0.001;

var x,f:real;

function s(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.

Program Prog5_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+ b²)-(a-b)³.

6. По заданному значению величины x определить, имеет ли функция

значение, и найти его.

7. Вычислить значения функции y=ax²+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 вычислить xⁿ согласно формуле:

10. Найти произведение для заданных a и n.

11. Даны неотрицательные целые числа n, m; вычислить A(n,m) – функцию Аккермана, где

12. Вычислить ln x, пользуясь формулами:

e – заданная точность.

13. Для заданного M ³ m ³ n >0 вычислить все биномиальные коэффициенты C_mⁿ по формулам:

14. Вычислить определитель заданной матрицы, пользуясь формулой разложения по первой строке (матрица B получается вычеркиванием из A первой строки и k -го столбца):

15. Вычислить по формуле:

, где ,

 

Задание 3. Составьте программу с использованием процедуры для решения следующей задачи:

Варианты заданий:

1. Найти наименьшие элементы двух различных матриц произвольной размерности.

2. «Сожмите» одномерные массивы размерности m и n, удалив из них нулевые элементы.

3. Найти сумму диагональных элементов матриц A и В.

4. В двух целочисленных последовательностях различной длины замените все элементы, следующие за элементом с максимальным значением, на значение минимального элемента.

5. Вычислить , где – корни уравнения 2x²+x – 4=0, – корни уравнения 3y²+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 больше длины строки. В нулевом байте хранится реальная длина строки. Доступ к элементам строки – символам – осуществляется так же, как к элементам массива, с помощью индекса, который записывается в квадратных скобках за идентификатором строковой переменной.

Примеры описания строк:

const slovo = ‘massiv’;

frasa = ‘Я пишу программу’;

type subekt = string [30];

var B,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; {ошибка}