ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) - В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар.

Задачи для самостоятельного решения

Рекурсивные процедуры и функции

Разрабатывая программу решения сложной задачи, обычно разбивают ее на меньшие, более простые подзадачи. Ясно, что из отдельных независимых решений подзадач намного легче построить решение исходной задачи. Этот общий прием называется методом «разделяй и властвуй» (divide and conquer).

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

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

Procedure Rec (t:integer);

Begin

действия на входе в рекурсию;

If условие Then Rec(t-1);

действия на выходе из рекурсии;

End;

Проиллюстрируем это на примере вычисления факториала числа n (n<=20):

Function Factorial(n:byte):qword;

Begin

If n=1 Then factorial=1

Else factorial:=n*factorial(n-1);

End;

Рассмотрим как будет работать эта функция для а=5!:

Тема рекурсии достаточно сложна и у многих вызывает сложности в процессе реализации рекурсивных программ. Рекурсивные алгоритмы сложнее отлаживать, но порой они позволяют очень гибко и красиво решить задачу. Известно, что любой рекурсивный алгоритм можно заменить нерекурсивным, но это скорее всего будет стоить больше времени на реализацию. Рекурсия часто применяется при решении задач с динамическим программированием, а так же в переборных задачах. Впервые столкнувшись с понятием рекурсии возникает вопрос: а не будет ли функция вызывать себя бесконечно? Здесь нужно понять, что в любой рекурсии обязательно должна быть нерекурсивная ветвь, в нашем случае – это If n=1 Then factorial=1

Другие задачи

Рекурсивные алгоритмы часто возникает при решении комбинаторных задач.

Пример 1. На плоской поверхности нарисован ряд клеток:

На первой клетке установлена шашка. Одним ходом шашку можно передвинуть вперед на одну или две клетки. Сколько существует маршрутов U(n) (способов) продвижения шашки на n-ю клетку?

Рассмотрим несколько частных решений:

U(1) = 1 (единственный маршрут –– оставаться на месте)

U(2) = 1 (единственный маршрут –– ход на одну клетку)

U(3) = 2 (ход на одну клетку и ход на две)

U(4) = 3

Каков алгоритм вычисления U(n), n > 2?

На клетку n можно попасть либо с клетки n–1, либо с клетки n–2. Отсюда имеем

U(n) = U(n–1) + U(n–2)

По рекуррентному соотношению легко записать рекурсивную функцию для подсчета числа маршрутов для любого n:

function U(n: integer): integer;

Begin

if n < 2 then

U:= 1 // существует один маршрут

Else

U:= U(n–1) + U(n–2)) // к-во маршрутов в общем случае

end;

Пример 2. Что напечатает следующая рекурсивная процедура от целого аргумента n ≥ 0 в результате вызова P(2)?

procedureP(n :integer);

Begin

ifn>0then

Begin

write(n);

P(n – 1); // рекурсивный вызов

write(n);

end;

Чтобы дать ответ, будем рассуждать так. Вызов P(2) означает выполнение последовательности операторов

write(2);

P(1);

write(2);

Рекурсивный (повторный) вызовов P(1), в свою очередь, можно заменить двумя операторами печати и вызовом P(0):

write(2);

write(1);

P(0);

write(1);

write(2);

Вызов P(0), когда процедура вызывается для значения 0, не выполняют никаких алгоритмических действий, поэтому просто вычеркнем его. В результате получим последовательность операторов печати, которая и дает ответ:

write(2);

write(1);

write(2);

Задачи для самостоятельного решения

1. Каждое число Фибоначчи равно сумме двух предыдущих чисел при условии, что первые два равны 1. Найдите n-ое число Фибоначчи.

2. Определить в виде рекурсивной функции быстрое возведение в целую степень n ≥ 0.

Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в n-ую степень за O(log(n)) умножений (вместо n умножений при обычном подходе).

Заметим, что для любого числа a и чётного числа n выполнимо очевидное тождество (следующее из ассоциативности операции умножения):

Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного n мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.

Осталось понять, что делать, если степень n нечётна. Здесь мы поступаем очень просто: перейдём к степени n-1, которая будет уже чётной:

Итак, мы фактически нашли рекуррентную формулу: от степени n мы переходим, если она чётна, к n/2, а иначе — к n-1.

3. Напишите рекурсивную функцию расчета степени N вещественного числа A (n – натуральное число).

4. Написать рекурсивную функцию вычисления количества цифр натурального числа n.

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

6. Напишите рекурсивную функцию нахождения НОД двух чисел.

7. Написать рекурсивную процедуру перевода натурального числа из десятичной системы счисления в двоичную.

8. Описать логическую рекурсивную функцию palindrom(S), которая дает значение true, если строка S является палиндромом (то есть читается одинаково слева направо и справа налево), и false в противном случае. Оператор цикла не использовать.

9. Найти наибольшее значение в линейном массиве a[1:n] размера n.

10. (Сортировка массива). Выбираем в массиве a[1:n] наибольший элемент и меняем его и последний элемент a[n] местами. На следующем шаге повторяем то же самое для еще не отсортированной части a[1: n–1] массива и т. д. При n = 1 массив уже упорядочен. Запрограммировать алгоритм в виде рекурсивной процедуры.

11. (Сортировка массива). Просматриваем массив a[1 : n] от начала к концу. Если два соседних элемента не упорядочены, то меняем их местами. В результате наибольший элемент переместится на последнее место. На следующем шаге повторяем то же самое для еще не отсортированной части a[1 : n–1] массива и т. д. При n = 1 массив уже упорядочен. Запрограммировать алгоритм в виде рекурсивной процедуры.

12. Оформить алгоритм поиска делением пополам в массиве a[1 : n] в виде рекурсивной процедуры или функции без использования оператора цикла.