Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Рекурсия
Цель работы: освоение приемов рекурсивного написания алгоритмов.
Образец решения задачи.
Задача. Составьте рекурсивный алгоритм вычисления произведения элементов массива.
Постановка задачи
Входные данные.
Одномерный массив – m (тип – массив вещественных элементов).
Выходные данные.
Произведение элементов массива – pr (тип - вещественный).
Алгоритм.
Текст программы.
Модуль 1.
unit op;
interface
const nn=100;
type mas = array[1..nn]of real;
implementation
end.
Модуль 2.
unit recursi;
interface
uses op;
function fun(var mass: mas; k : byte) : real;
procedure vvod(var mass : mas; k: byte);
implementation
function fun : real;
begin
if k=0 then fun:=1
else fun:=mass[k]*fun(mass, k-1);
end;
procedure vvod;
var i : byte;
begin
for i:=1 to k do
readln(mass[i]);
end;
end.
Основная программа.
uses
op, recursi;
var
n : byte;
pr : real;
m : mas;
begin
writeln(‘Введите количество элементов массива’);
readln(n);
vvod(m, n);
pr:=fun(m, n);
writeln('pr=', pr : 4 : 0)
end.
Задания для самостоятельного решения.
Вариант 1.
1. Каков будет результат функции при a=12? b=3?
function NOD(a, b: byte): byte;
begin
if b=a then NOD:=a
else if a>b then NOD:=NOD(b, a-b)
else NOD:= NOD(a, b-a);
end;
2. Написать рекурсивную функцию digits, которая подсчитывает количество цифр в заданном тексте.
3. В написанном выражении ((((1 ? 2) ? 3) ? 4) ? 5) ? 6. Вместо каждого знака "?" вставить знак одного из четырех арифметических действий: +, -, *, / так, чтобы результат вычислений равнялся 35 (при делении дробная часть в частном отбрасывается).
Вариант 2.
1. Каков будет результат функции при a=24? b=8?
function NOD(a, b: byte): byte;
begin
if b=a then NOD:=a
else if a>b then NOD:=NOD(b, a-b)
else NOD:= NOD(a, b-a);
end;
2. Составьте рекурсивный алгоритм вычисления суммы элементов массива.
3. Из заданных N предметов выбрать такие, чтобы их суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать номера и суммарную стоимость выбранных предметов. Вес и стоимость предметов заданы массивами A[1:N] и B[1:N].
Вариант 3.
1. Каков будет результат функции при a=5? b=5?
function div(a, b: byte): byte;
begin
if a<b then div:=0
else div:=div(a-b, b)+1;
end.
2. Составьте алгоритм рекурсивного поиска наименьшего элемента массива.
3. В выражении 12894 * 4193 * 9510 * 8653 * 4381 * 2546 * 1158 * 8645 * 2587 заменить звездочки знаками "+" или "-" так, чтобы получившееся арифметическое выражение равнялось 1989.
Вариант 4.
1. Задан массив {fi}=2, 2, 1, 3, 1. Что будет результатом функции?
function fun(k:byte):real;
begin
if k=0 then fun:=1
else fun:=f[k]*fun(k-1);
end;
2. Составьте рекурсивный алгоритм вычисления количества четных элементов массива.
3. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения.
Вариант 5.
1. Каков будет результат функции при a=11? b=6?
function NOD(a, b: byte): byte;
begin
if b=a then NOD:=a
else if a>b then NOD:=NOD(b, a-b)
else NOD:= NOD(a, b-a);
end;
2. Составьте рекурсивный алгоритм вычисления количества элементов массива кратных 3-м.
3. Напишите рекурсивный алгоритм сортировки вставками.
Вариант 6.
1. Задан массив {fi}=0, 2, 1, 6, 1, 1. Что будет результатом функции?
function fun(k:byte):real;
begin
if k=0 then fun:=1
else fun:=f[k]*fun(k-1);
end;
2. Составьте рекурсивный алгоритм вычисления суммы положительных элементов массива.
3. В выражении 12894 * 4193 * 9510 * 8653 * 4381 * 2546 * 1158 * 8645 * 2587 заменить звездочки знаками "+" или "-" так, чтобы получившееся арифметическое выражение равнялось 1989.
Вариант 7.
1. Каков будет результат функции при a=12? b=3?
function div(a, b: byte): byte;
begin
if a<b then div:=0
else div:=div(a-b, b)+1;
end.
2. Составьте алгоритм рекурсивного поиска наибольшего элемента массива.
3. Найти первое из чисел Фиббоначи, больших m.
Вариант 8.
1. Каков будет результат функции при a=8? b=4?
function div(a, b: byte): byte;
begin
if a<b then div:=0
else div:=div(a-b, b)+1;
end.
2. Составьте рекурсивный алгоритм вычисления суммы отрицательных элементов массива.
3. Написать алгоритм и программу для поиска взаимно простых чисел в натуральном ряду чисел.
Вариант 9.
1. Каков будет результат функции при a=5? b=3?
function div(a, b: byte): byte;
begin
if a<b then div:=0
else div:=div(a-b, b)+1;
end.
2. Составьте рекурсивный алгоритм вычисления суммы нечетных элементов массива.
3. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения.
Вариант 10.
1. Каков будет результат функции при a=10? b=4?
function NOD(a, b: byte): byte;
begin
if b=a then NOD:=a
else if a>b then NOD:=NOD(b, a-b)
else NOD:= NOD(a, b-a);
end;
2. Составьте рекурсивный алгоритм вычисления количества элементов массива находящихся в диапазоне [x..y].
3. Напишите рекурсивный алгоритм сортировки выбором.
Контрольные вопросы:
1. Рекурсивным называется объект
варианты ответов:
2. Линейная рекурсия это
варианты ответов:
3. Повторная рекурсия это
варианты ответов:
4. Удаленная рекурсия это
варианты ответов:
5. Что требуется для реализации рекурсивных вызовов?
6. В чем заключается механизм рекурсии?
7. Куда помещаются данные при рекурсивной работе алгоритма?
8. Какие шаги необходимо выполнить, чтобы дать рекурсивное определение какому-либо понятию?
Как расходуется память при обслуживании вызовов рекурсивной функции?
Когда целесообразно использовать рекурсию при решении задач?