Выполнение практических заданий

Лабораторная работа №6.

Тема: Применение рекурсивных функций.

Цель: Развить навыки организации процедур и функций. Уметь использовать стандартные и пользовательские процедуры и функции. Уметь использовать различные виды параметров процедур.

Оборудование и материалы: Методическое пособие, ручка, карандаш, линейка, ластик, шаблон А4.

Ход работы

Методические рекомендации.

Необходимая информация содержится в лекции № 10.

Решение задач представить в следующем порядке: постановка задачи, построение математической модели, блок-схемы процедур и функций, программный код, тестирование.

Задание для лабораторной работы выбрать согласно варианту по приведённой таблице. Вариант определяется порядковым номером в журнале группы.

Образцы решения типовых задач.

Задача №1. Вычисление факториала и возведение в степень.

Function stepen (a: real;n:word): real;

Begin

{ Если степень числа а равна 0, то результат – число 1.}

If n=0 then stepen: =1

Else

{ Иначе для возведения в степень число а надо умножить на а в степени n-1.}

Stepen: = a*stepen(a, n-1)

End;

Function factorial (n:word): real;

Begin

{Если N=0 или 1, то факториал равен 1.}

If n <=1 then factorial: =1

Else

{Иначе факториал числа N рассчитывается так N*factorial(N-1).}

Factorial: = N*factorial (N-1)

End;

Var a: real;

N: integer;

Begin

Writeln (‘Возведениечисла а в степень N ’);

Write (‘a=’);read(a);

Write (‘N=’);read(N);{Если степень числа а положительная, то просто обращаемся к функции stepen(a,n)}

If N>=0 then

writeln (stepen(a,n)) {Если степень числа отрицательная, то вычисляем а в степени n, как 1 .}

Else

writeln (1/stepen(a,abs(n)));

Writeln (‘Вычисление N! ’);

Write (‘N=’);

Read (N);

Write (N,’! =’, factorial(N)); End.

Задача №2. Перевод натурального числа из десятичной системы счисления в двоичную.

Решение. Для решения этой задачи рассмотрим сначала, как перевести число из десятичной системы счисления в двоичную. Пусть число 39, которое и надо представить в двоичной системе. Для этого разделим его на 2, получим целую часть и остаток от деления. Целую часть снова делим на 2 и получаем целую часть и остаток. Так делаем до тех пор, пока целую часть можно делить на 2 (то есть пока она не станет равной 1).

Теперь, начиная с этой единицы, выписываем в обратном порядке все остатки от деления, это и будет запись числа 39 в двоичной системе счисления:

39 = 100111 .

Таким образом можно переводить любое натуральное число из десятичной системы счисления в двоичную, а также и в другие системы (например, восьмеричную или шестеричную).

Опишем процедуру:

Procedure Rec (n: Integer);

Begin

If n>1 Then Rec (n Div 2);

Write (n Mod 2);

End.

Первая цифра (1) выводится на экран из последнего вызова, следующая цифра (0) из предпоследнего и так далее, последняя (1)- из первого. Таким образом, вывод очередной цифры происходит перед тем, как выйти из данной функции.

Выполнение практических заданий.

Вариант	№ задач	Вариант	№ задач	Вариант	№ задач
	1, 4		5, 8		3, 6
	2, 5		3, 5		2, 7
	3, 6		4, 7		4, 8
	1, 7		3, 8		7, 9
	2, 8		2, 9		1, 6
	3, 9		5, 7		2, 7
	1, 5		6, 8		4, 5
	2, 6		1, 9		4, 9
	3, 7		1, 4		2, 3
	1, 8		6, 9		3, 6

1. Написать рекурсивную функцию для нахождения биномиальных коэффициентов

Для заданного М вычислить все

2. Описать рекурсивную функцию, которая по заданным вещественному х и целому т вычисляет величину согласно формуле

3. Написать программу вычисления функции Аккермана для всех неотрицательных целых аргументов m и n

4. Описать рекурсивную функцию PowerN вещественного типа, находящую значение n-ый степени числа x по формуле

, , при n > 0,

при n < 0

(x 0- ввещественное число, n- целое). С помощью этой функции найти значения x при пяти различных значениях n.

5.Описать рекурсивную функцию SqrtK вещественного типа, находящую приближенное значение корня k-й степени из числа x по формуле

, ,

где y(n) обозначает SqrtK(x, k, n)(x-вещественный параметр, k и n-целые; x>0, k>1, n>0).

С помощью этой функции найти приближенные значения корня k-й степени из x при шести различных значениях n.

6. Описать рекурсивную функцию FibRec(N) целого типа, вычисляющую N-е число Фибоначчи F(N) по формуле

F (1)= F(2)=1, F(k)=F(k-2)+F(k-1),

где k=3,4....

С помощью этой функции найти пять чисел Фибоначчи с указанными номерами и вывести эти числа вместе с количеством рекурсивных вызовов функции FibRec, потребовавшихся для их наложения.

7. Описать рекурсивную функцию целого типа, находящую число сочетаний из n элементов по m, используя формулу

C(0, n)=C(n, n)=1, C(m, n)= C(m, n-1)+ C(m-1, n-1)

При 0<m<n(m и n-целые параметры; n>0, 0 m n). Дано число N и пять различных значений M. Вывести числа вместе с количеством рекурсивных вызовов функции, потребовавшихся для из нахождения.

8. Описать рекурсивную функцию Digits целого типа, находящую количество цифр в строке S без использования оператора цикла. С помощью этой функции найти количество цифр в данных пяти строках.

9. Найти сумму первых N членов арифметической (геометрической) прогрессии.

Контрольные вопросы.