Лабораторная работа №5

Рекурсия

Цель работы:
Познакомиться с одним из эффективных способов решения сложных задач – рекурсией.

Общие сведения:

Очень часто, разрабатывая программу, удается свести исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, вычисление функции F(n) может потребовать вычисления F(n-1) и еще каких-то операций. Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Алгоритм называется рекурсивным, если он прямо или косвенно обращается к самому себе. Часто в основе такого алгоритма лежит рекурсивное определение какого-то понятия. Например, о факториале числа N можно сказать, что N! = N*(N – 1)!, если N > 0 и N! = 1 если N = 0. Это – рекурсивное определение.
Вот еще одно рекурсивное определение.
1. 3 коровы – это стадо коров.
2. Стадо из n коров – это стадо из n – 1 коровы и еще одна корова.
Попробуем применить это определение для проверки, является ли стадом группа из пяти коров (обозначим ее К5). Объект К5 не удовлетворяет первому пункту определения, поскольку пять коров – это не три коровы. Согласно второму пункту К5 – стадо, если там есть одна корова, а остальная часть К5, назовем ее К4, – тоже стадо коров. Решение относительно объекта К5 откладывается, пока не будет принято решение относительно К4. Объект К4 снова не подходит под первый пункт, а второй пункт гласит, что К4 – стадо, если объект К3, полученный из К4 путем отделения одной коровы, тоже стадо. Решение о К4 тоже откладывается. Наконец, объект К3 удовлетворяет первому пункту определения, и мы можем смело утверждать, что К3– стадо коров. Теперь и о К4 можно утверждать, что это стадо, а значит, и К5 является стадом коров.
Любое рекурсивное определение состоит из двух частей. Эти части принято называть базовой и рекурсивной частями. Базовая часть является нерекурсивной и задает определение для некоторой фиксированной части объектов. Рекурсивная часть определяет понятие через него же и записывается так, чтобы при цепочке повторных применений она редуцировалась бы к базе.

Примеры

1. Задача. Написать рекурсивную программу поиска минимального элемента массива.
Решение. Опишем функцию Pmin, которая определяет минимум среди первых n элементов массива а. Параметрами этой функции являются количество элементов в рассматриваемой части массива - n и значение последнего элемента этой части – а[n]. При этом если n>2, то результатом является минимальное из двух чисел – а[n] и минимального числа из первых (n-1) элементов массива. В этом заключается рекурсивный вызов. Если же n=2, то результатом является минимальное из первых двух элементов массива. Чтобы найти минимум всех элементов массива, нужно обратиться к функции Pmin, указав в качестве параметров значение размерности массива и значение последнего его элемента. Минимальное из двух чисел определяется с помощью функции Min, параметрами которой являются эти числа. 
Program Example _1;
Const n=10;
Type MyArray=Array[1..n] of Integer;
Const a : MyArray = (4,2, -1,5,2,9,4,8,5,3);
Function Min (a, b : Integer) : Integer;
Begin
  if a>b then Min := b else Min:=a;
End;
Function Pmin(n, b : Integer) : Integer;
Begin
  if n = 2 then Pmin := Min(n,a[1]) else Pmin := Min(a[n], Pmin(n-1,a[n]));
End;
BEGIN
  Writeln(‘Минимальный элемент массива  - ‘, Pmin(n,a[n]));
END.
2. Задача. Ханойские башни. Имеется три стержня А, В, С. На стержень А нанизано п дисков радиуса 1, 2,..., п таким образом, что диск радиуса i является i-м сверху. Требуется переместить все диски на стержень В, сохраняя их порядок расположения (диск с большим радиусом находится ниже). За один раз можно перемещать только один диск с любого стержня на любой другой стержень. При этом должно выполняться следующее условие: на каждом стержне ни в какой момент времени никакой диск не может находиться выше диска с меньшим радиусом.
Решение. Предположим, что мы умеем перекладывать пирамиду из (n-1) диска. Рассмотрим пирамиду из n дисков. Переместим первые (n-1) дисков на стержень С (это мы умеем). Затем перенесем последний n-й диск со стержня А на стержень В. Далее перенесем пирамиду из (n-1) диска со стержня С на стержень В. Так как n-й диск самый большой, то условие задачи не будет нарушено. Таким образом, вся пирамида будет на стержне В. Аналогичным образом можно перенести n – 2, n – 3 и т. д. дисков. Когда n=1, осуществить перенос очень просто: непосредственно с первого стержня на второй. При этом для решения задачи будет достаточно 2n - 1 перекладываний. 
Program Example_2;
Const k = 3;
Var a,b,c : Char;
Procedure Disk(n : Integer; a, b, c: Char);
Begin
  if n>0 then
     begin
       Disk(n-1,a,c,b);
       Writeln(‘Диск ‘,n, ’ c ‘, a,’->’, b);
       Disk(n-1,c,b,a);
     end;
End;
BEGIN
  a := ‘A’; b := ‘B’; c := ‘C’;
  Disk(k,a,b,c);
 ReadLn;
END.

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

1. На чем основан рекурсивный метод программирования?
2. В чем разница между «циклическим» и «рекурсивным» способами определения? Какой элемент является обязательным в рекурсивном определении?
3. Что такое «фрейм активации»?
4. К каким последствиям приводит «рекурсивное зацикливание»?
5. Какое условие должно обязательно присутствовать в любой рекурсивной процедуре?
6. Что такое явная и косвенная рекурсии?
7. Дайте рекурсивное определение целой степени числа N.

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

1. Ввести последовательность чисел (окончание ввода – 0) и вывести их в обратной последовательности. Входные данные взять из текстового файла.
2. Используя команды write(x) лишь при x=0..9, написать рекурсивную программу печати десятичной записи целого положительного числа n.
3. Напишите рекурсивную функцию, которая возвращает среднее из n элементов массива чисел.
4. Найти первые N чисел Фибоначчи двумя способами: с помощью рекурсии и с помощью итерации. Сравнить эффективность алгоритмов.
5. Написать функцию сложения двух чисел, используя только прибавление единицы.
6. Написать функцию умножения двух чисел, используя только операцию сложения.
7. Вычислить сумму элементов одномерного массива.
8. Найти НОД (наибольший общий делитель) двух натуральных чисел.
9. Вычислить несколько значений функции Аккермана для неотрицательных чисел m и n:
10. Напишите рекурсивную функцию, которая вычисляет длину строки.
11. Написать функцию C(m,n) вычисления биномиальных коэффициентов по следующей формуле:
12. Проверить, является ли фрагмент строки с i-го по j-й символ палиндромом.
13. Вычислить произведение элементов одномерного массива.
14. Написать процедуру сортировки массива методом простого выбора.
15. Подсчитать количество цифр в заданном числе.
16. Написать функцию, проверяющую правильность имени в языке Pascal.
17. Написать функцию которая методом деления отрезка пополам (методом дихотомии) находит с точностью eps корень уравнения f(x) = 0 на отрезке [a,b] (). Метод дихотомии определяется следующим образом. Если f(a) и f(b) имеют разные знаки, то между точками a и b существует корень R. Пусть – средняя точка в интервале Если f(m) = 0, то корень R=m. Если нет, то либо f(a) и f(m) имеют разные знаки , либо f(m) и f(b) имеют разные знаки. Если, то корень лежит в интервале В противном случае он лежит в интервале Теперь выполним это действие для нового интервала – половины исходного интервала. Процесс продолжается до тех пор, пока интервал не станет меньше eps.
18. В текстовом файле задана последовательность положительных чисел, за которой следует отрицательное число. Написать функцию без параметров для нахождения суммы этих положительных чисел.
19. Написать функцию без параметров, которая подсчитывает количество цифр в тексте, заданном в текстовом файле (за текстом следует точка).
20. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0). Написать программу поиска минимального пути для произвольной пары городов.
21. Вычислить определитель матрицы, пользуясь формулой разложения по первой строке:
где матрица Bk получается из A вычеркиванием первой строки и k-го столбца.
22. Написать функцию определения, является ли заданное натуральное число простым.
23. Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.
24. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0). Написать программу поиска минимального пути обхода всех городов без посещения дважды одного и того же города (задача коммивояжера).
25. Задан набор слов. Построить из них любую цепочку таким образом, чтобы символ в конце слова совпадал с символом в начале следующего.
26. Задан массив целых. Построить из них любую последовательность таким образом, чтобы последняя цифра предыдущего числа совпадала с первой цифрой следующего.
27. Для данного n напечатайте коэффициенты разложения полинома (1 + x)n.
28. Вычислить, используя рекурсию, выражение
29. Написать процедуру печати всех перестановок из n символов.
30. Написать процедуру перевода числа из десятичной системы счисления в двоичную.
Назад
На главную
    Учебник по языку Pascal          Лабораторные работы по программированию          Справочник



Нет комментариев.


Оставить комментарий:
Ваше Имя:
Email:
Антибот: *  
Ваш комментарий: