Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Лабораторная работа № 14
|
|
Тема: Рекурсия
Цель работы: освоение приемов написания рекурсивных алгоритмов.
Образец решения задачи.
Задача.Составьте рекурсивный алгоритм вычисления произведения элементов массива.
Входные данные.
Одномерный массив – m (тип – массив дробных чисел).
Выходные данные.
Произведение элементов массива – pr (тип - дробное).
Алгоритм.
1. Ввод элементов массива.
2. Нахождения произведения элементов массива.
3. Вывод результата на печать.
Текст программы.
Модуль 1.
unit op;
Interface
Const
n=100;
Type
tMas= array [1..n] of real;
Implementation
End.
Модуль 2.
unit recursi;
Interface
uses op;
function fun(var M: tMas; k: byte): real;
procedure vvod ( varM: tMas );
Implementation
function fun(var M: tMas; k: byte): real;
Begin
if k=0 then
fun: =1
Else
fun: =M[k]*fun(M, k-1);
end;
procedure vvod ( varM: tMas );
Var
i: byte;
Begin
for i: =1 to n do
ReadLn(M[i]);
End;
End.
Основная программа.
Uses
op, recursi;
Var
pr: real;
M: tMas;
Begin
vvod(M);
pr: =fun(M);
WriteLn(’Произведение элементов массива =’, 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 divis(a, b: byte): byte;
Begin
if a< b then
divis: =0
Else
divis: = divis (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 divis(a, b: byte): byte;
Begin
if a< b then
divis: =0
Else
divis: = divis(a-b, b)+1;
end;
2. Составьте алгоритм рекурсивного поиска наибольшего элемента массива.
3. Найти первое из чисел Фиббоначи, больших m.
Вариант 8.
1. Каков будет результат функции при a=8? b=4?
function divis(a, b: byte): byte;
Begin
if a< b then
divis: =0
Else
divis: = divis (a-b, b)+1;
end;
2. Составьте рекурсивный алгоритм вычисления суммы отрицательных элементов массива.
3. Написать алгоритм и программу для поиска взаимно простых чисел в натуральном ряду чисел.
Вариант 9.
1. Каков будет результат функции при a=5? b=3?
function divis(a, b: byte): byte;
Begin
if a< b then
divis: =0
Else
divis: =divis(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. Рекурсивным называется объект
варианты ответов:
1) если он содержит сам себя или определен с помощью самого себя;
2) позволяющий строить элегантные и выразительные алгоритмы;
3) который явно обращается к самому себе;
4) содержащий прямое обращение к самому себе.
2. Линейная рекурсия ¾ это
варианты ответов:
1) рекурсия, в которой каждый рекурсивный вызов приводит не более, чем к одному дальнейшему рекурсивному вызову
2) рекурсия, которая приводит к простой структуре обработки, перед тем как начинается новое выполнение рекурсивного вызова, вычисление предыдущего рекурсивного вызова прекращается
3) рекурсия, в которой, по меньшей мере, на одной ветке разветвления в теле рекурсии встречаются 2 и более рекурсивных вызова
4) когда в теле рекурсивного объявления в выражениях фактических параметров в свою очередь встречаются рекурсивные вызовы
5) когда процедура а рекурсивно вызывает процедуры а и в, процедура в в свою очередь рекурсивно вызывает а и в
3. Повторная рекурсия ¾ это
варианты ответов:
1) рекурсия, в которой каждый рекурсивный вызов приводит не более, чем к одному дальнейшему рекурсивному вызову
2) рекурсия, которая приводит к простой структуре обработки, перед тем как начинается новое выполнение рекурсивного вызова, вычисление предыдущего рекурсивного вызова прекращается
3) рекурсия, в которой, по меньшей мере, на одной ветке разветвления в теле рекурсии встречаются 2 и более рекурсивных вызова
4) когда в теле рекурсивного объявления в выражениях фактических параметров в свою очередь встречаются рекурсивные вызовы
5) когда процедура а рекурсивно вызывает процедуры а и в, процедура в в свою очередь рекурсивно вызывает а и в
4. Удаленная рекурсия ¾ это
варианты ответов:
1) рекурсия, в которой каждый рекурсивный вызов приводит не более, чем к одному дальнейшему рекурсивному вызову
2) рекурсия, которая приводит к простой структуре обработки, перед тем как начинается новое выполнение рекурсивного вызова, вычисление предыдущего рекурсивного вызова прекращается
3) рекурсия, в которой, по меньшей мере, на одной ветке разветвления в теле рекурсии встречаются 2 и более рекурсивных вызова
4) когда в теле рекурсивного объявления в выражениях фактических параметров в свою очередь встречаются рекурсивные вызовы
5) когда процедура а рекурсивно вызывает процедуры а и в, процедура в в свою очередь рекурсивно вызывает а и в
5. Что требуется для реализации рекурсивных вызовов?
6. В чем заключается механизм рекурсии?
7. Куда помещаются данные при рекурсивной работе алгоритма?
8. Какие шаги необходимо выполнить, чтобы дать рекурсивное определение какому-либо понятию?
8. Как расходуется память при обслуживании вызовов рекурсивной функции?
9. Когда целесообразно использовать рекурсию при решении задач?