Лабораторная работа ’ 7 Тема- Рекурсия Цель работы- освоение приемов рекурсивного написания алгоритмов
Работа добавлена на сайт samzan.net:
Лабораторная работа № 7
Тема: Рекурсия
Цель работы: освоение приемов рекурсивного написания алгоритмов.
Образец решения задачи.
Задача. Составьте рекурсивный алгоритм вычисления произведения элементов массива.
Постановка задачи
Входные данные.
Одномерный массив – 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. Линейная рекурсия это
варианты ответов:
- рекурсия, в которой каждый рекурсивный вызов приводит не более, чем к одному дальнейшему рекурсивному вызову
- рекурсия, которая приводит к простой структуре обработки, перед тем как начинается новое выполнение рекурсивного вызова, вычисление предыдущего рекурсивного вызова прекращается
- рекурсия, в которой, по меньшей мере, на одной ветке разветвления в теле рекурсии встречаются 2 и более рекурсивных вызова
- когда в теле рекурсивного объявления в выражениях фактических параметров в свою очередь встречаются рекурсивные вызовы
- когда процедура а рекурсивно вызывает процедуры а и в, процедура в в свою очередь рекурсивно вызывает а и в
3. Повторная рекурсия это
варианты ответов:
- рекурсия, в которой каждый рекурсивный вызов приводит не более, чем к одному дальнейшему рекурсивному вызову
- рекурсия, которая приводит к простой структуре обработки, перед тем как начинается новое выполнение рекурсивного вызова, вычисление предыдущего рекурсивного вызова прекращается
- рекурсия, в которой, по меньшей мере, на одной ветке разветвления в теле рекурсии встречаются 2 и более рекурсивных вызова
- когда в теле рекурсивного объявления в выражениях фактических параметров в свою очередь встречаются рекурсивные вызовы
- когда процедура а рекурсивно вызывает процедуры а и в, процедура в в свою очередь рекурсивно вызывает а и в
4. Удаленная рекурсия это
варианты ответов:
- рекурсия, в которой каждый рекурсивный вызов приводит не более, чем к одному дальнейшему рекурсивному вызову
- рекурсия, которая приводит к простой структуре обработки, перед тем как начинается новое выполнение рекурсивного вызова, вычисление предыдущего рекурсивного вызова прекращается
- рекурсия, в которой, по меньшей мере, на одной ветке разветвления в теле рекурсии встречаются 2 и более рекурсивных вызова
- когда в теле рекурсивного объявления в выражениях фактических параметров в свою очередь встречаются рекурсивные вызовы
- когда процедура а рекурсивно вызывает процедуры а и в, процедура в в свою очередь рекурсивно вызывает а и в
5. Что требуется для реализации рекурсивных вызовов?
6. В чем заключается механизм рекурсии?
7. Куда помещаются данные при рекурсивной работе алгоритма?
8. Какие шаги необходимо выполнить, чтобы дать рекурсивное определение какому-либо понятию?
Как расходуется память при обслуживании вызовов рекурсивной функции?
Когда целесообразно использовать рекурсию при решении задач?
2. Вариант 1 За каждый правильный ответ 1 балл
3. комунікаційних технологій КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Факультет інформаційних технологій
4. Українська мова за професійним спрямуванням
5. Тема 6 УРОК ~ ОСНОВНАЯ ОРГАНИЗАЦИОННАЯ ФОРМА УЧЕБНОГО ПРОЦЕССА 1
6. Реферат- Визнання доходів за бартерними контрактами
7. Невербальные средства общения
8. Здоровый образ жизни десять основных привычек
9. Основы инвестирования
10. Тема- Кримські гори
11. Лекции по истории философии А
12. Анализ сбыта продукции предприятия
13. ТЕМА МОНІТОРИНГУ КОНТРОЛЮ І ПРОФІЛАКТИКИ ТОКСИКОІНФЕКЦІЙ САЛЬМОНЕЛЬОЗНОЇ ТА ЕШЕРИХІОЗНОЇ ЕТІОЛОГІЙ 16
14. Реферат на тему- ldquo;Статистичні ігри
15. ПРАКТИКУМ Вспомогательное учебное издание для студентов технического вуза Утверждено редак
16. Витамин К.html
17. Скрибнер. Спасибо моему агенту Лиз Дархансофф и всем работникам Дархансофф и Веррилл за оказанную помощь.
18. Тема 400 S- Основными разделами лечебнопрофилактической помощи населению являются - профилактика - д
19. ции. Методы продажи тов.
20. лекция Написание 2 эссе -или получение 4х плюсов за устную работу на занятиях -или написание 1 эссе полу