40 80 30 50 60 20 10

Поменяем их местами:

 40 10 30 50 60 20 80

Продолжим движение, находим еще одну удовлетворяющую условиям поиска пару чисел:

 40 10 30 50 60 20 80

Меняем их местами:

 40 10 30 20 60 50 80

Когда левая отметка зайдет за правую, останавливаем движение.

 40 10 30 20 60 50 80

Меняем число над правой отметкой (из двух отмеченных оно теперь левее!) местами с разделителем

   20 10 30 40 60 50 80

   и разделение массива закончено

Теперь аналогичную процедуру необходимо проделать над левой и правой половинками массива, при условии, что они имеют длину более одного элемента. Таким образом, базой рекурсии для рассмотренного алгоритма будет подмассив размером 1 или 0 элементов, который, очевидно, не требует сортировки. Шаг рекурсии – сортировка левого и правого подмассивов после операции разделения исходного массива.

Программная реализация алгоритма сортировки по Хоару представлена в листинге 1.

Листинг 1. Сортировка массива методом быстрой обменной сортировки.

#include<iostream.h>

#include <stdlib.h>

#include<conio.h>

int m[10]={96,95,93,45,96,17,64,78,21,19};

/*

sorting – функция разделения массива. Прнимает параметры left и right – границы подмассива для разделения. Через параметр middle возвращает вызвавшей функции место разделтеля по итогам разделения

*/

sorting(int left,int right,int& middle)

{

int sep=left,t, RightBorder=right;

while(left<=right)

{

while(m[left]<=m[sep]&&left<=RightBorder) left++;

while(m[right]>=m[sep]&&right>sep) right--;

if (left<right)

{t=m[left];

m[left]=m[right];

m[right]=t;

}

}

t=m[sep];

m[sep]=m[right];

m[right]=t;

middle=right;

}

/*hoer – функция сортировки массива m по возрастанию методом Хоара.

Параметры задают индексы начала и конца сортируемого подмассива

*/

hoer(int left,int right)

{

int mid;

if (left<right) //пока подмассив больше 1-го элемента

{sorting(left,right,mid);//разделение массива

hoer(left,mid-1); //сортировка левого подмассива

hoer(mid+1,right); //сортировка правого подмассива

}

}

int main()

{

clrscr();

randomize();

for(int i=0;i<10;i++)

cout<<m[i]<<' ';

сout<<'\n';

hoer(0,9); //сортируем весь массив m

for(i=0;i<10;i++)

cout<<m[i]<<' ';

return 0;

}

Рекурсия – очень мощный инструмент, позволяющий решать широкий спектр задач. Из приведенных выше примеров должен стать понятен принцип применения рекурсии на практике: если решение задачи можно свести к решению аналогичной задачи с меньшим объемом данных (меньшим количеством операций), то здесь может быть эффективна рекурсия.

Однако необходимо учитывать, что зачастую использование рекурсивных методов в чистом виде может оказаться неэффективным из-за слишком большого количества вариантов рекурсивных спусков. В этом случае рекурсию дополняют такими методами решения задач, как динамическое программирование, отсечение и др.

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

1. Что такое рекурсия?

2. Приведите примеры рекурсии в различных отраслях знаний.

3. Что общего и в чем разница между циклическим и рекурсивным способами организации вычислений?

4. Объясните термины «база рекурсии» и «шаг рекурсии». Определите базу рекурсии и шаг рекурсии для своей задачи.

5. Что такое «рекурсивное зацикливание»? К каким последствиям оно приводит?

6. Каково главное ограничение при использовании рекурсии?

7. Что такое явная и косвенная рекурсии?

8. Оцените, от чего зависит глубина рекурсии в алгоритме решения вашей задачи.

Порядок выполнения работы

1. Ознакомьтесь с теоретическими основами разработки и программной реализации рекурсивных алгоритмов в настоящих указаниях и конспектах лекций.

2. Получите вариант задания у преподавателя.

3. Составьте алгоритм решения задачи согласно варианту задания, оформите его в графической форме.

4. Используя разработанный алгоритм, напишите программу.

5. Отладьте разработанную программу и покажите результаты работы про­граммы преподавателю.

6. Составьте отчет по лабораторной работе.

7. Отчитайте работу преподавателю.

Содержание отчета

Отчет по лабораторной работе должен содержать следующие сведения:

• название и цель работы;

• вариант задания;

• графическую схему алгоритма решения задачи;

• листинг разработанной программы с комментариями;

- результаты работы программы

Пример выполнения лабораторной работы.

Написать рекурсивную функцию printd(), печатающую целое число в виде последовательности символов ASCII (т. е. цифр, образующих запись этого числа), а также вычисляющую сумму цифр в десятичной записи числа:

#include <stdio.h>

#include <conio.h>

int printd(int num) /* параметр num - печатаемое число */

{ int i, sumTmp=0;

if (num < 0)

{putchar('-'); num = -num;}

if ((i = num/10) != 0) // пока в числе есть цифры

sumTmp=printd(i); /* Рекурсивный вызов функции */

putchar(num % 10 + '0');//преобразуем цифру числа в

//код символа и выводим на экран

sumTmp+=num%10; //накапливаем сумму цифр

return sumTmp;

}

int main()

{

int value, sum;

scanf("%d", &value);

sum=printd(value);

printf("\nSum=%d", sum);

_getch();

return 0;

}

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

Примечание: при ращении задач обязательно использовать рекурсивный вызов.

1. Найти первые N чисел Фибоначчи двумя способами: с помощью рекурсии и с помощью итерации. Сравнить эффективность алгоритмов.

2. Написать функцию сложения двух чисел, используя только прибавление единицы.

3. Написать функцию умножения двух чисел, используя только операцию сложения.

4. Вычислить сумму элементов одномерного массива.

5. Вычислить несколько значений функции Аккермана для неотрицательных чисел m и n:

6. Написать функцию C(m,n) вычисления биномиальных коэффициентов по следующей формуле:

7. Проверить, является ли фрагмент строки с i-го по j-й символ палиндромом.

8. Подсчитать количество цифр в заданном числе.

9. Вычислить, используя рекурсию, выражение

10. Написать функцию которая методом деления отрезка пополам (методом дихотомии) находит с точностью 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.

11. Ввести последовательность чисел (окончание ввода – 0) и вывести их в обратном порядке.

12. Подсчитать сумму цифр в десятичной записи заданного числа.

Дополнительные варианты заданий.

1*. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0). Написать программу поиска минимального пути для произвольной пары городов.

2*. Вычислить определитель матрицы, пользуясь формулой разложения по первой строке:

где матрица B_k получается из A вычеркиванием первой строки и k-го столбца.

3*. Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.

4*. Несколько человек должны перейти ночью реку через мост. По мосту одновременно могут пройти только 2 человека, в наличии имеется лишь один фонарик (двое переходят мост, обязательно с фонарем, затем один должен вернуться назад с фонариком). Если заданы скорости движения каждого человека s_i, написать программу, которая предложит схему прохождения всех людей через мост за наименьшее время.

5*. Задан набор слов. Построить из них любую цепочку таким образом, чтобы символ в конце слова совпадал с символом в начале следующего.

6*. Написать процедуру печати всех перестановок из n символов.

Литература