Программирование на языке C в Microsoft Visual Studio 2010

Рекурсивные алгоритмы и функции

Разбить на страницы
Показывать лекцию целиком

Теоретическая часть

Рекурсивные функции (лат. recursio – возвращение) – в вычислительной математике – функции, определенные на множестве натуральных чисел и принимающие значения того же множества [18.1].

Рекурсивный алгоритм – это алгоритм, решающий задачу путем решения одного или нескольких более узких вариантов той же задачи [18.2]. Функция называется рекурсивной, если в ее определении содержится вызов этой же функции [18.3]. Рекурсивная функция может вызывать саму се6я или непосредственно, или косвенно через другую функцию [18.4]. Рекурсии целесообразно применять в задачах, которые можно разбить на множество меньших подобных задач [18.5]. Рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей с боле простыми данными.

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

Рекурсивный подход обычно предпочитается итеративному подходу в тех случаях, когда рекурсия более естественно отражает математическую сторону задачи и приводит к программе, которая проще для понимания и отладки. Другой причиной для выбора рекурсивного решения является то, что итеративное решение может не быть очевидным [18.4].

Наличие в задаче рекуррентного соотношения позволяет использовать рекурсию. Например, арифметическая прогрессия – последовательность чисел, в которой разность между последующими и предыдущими членами остается неизменной и называется разностью прогрессии [18.1]. То есть каждый следующий член прогрессии равен предыдущему, увеличенному на разность прогрессии.

Различают прямую и косвенную рекурсию. Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции. Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций [18.6]. Все функции, входящие в цепочку, тоже считаются рекурсивными.

В рекурсии простейшей формы рекурсивный вызов расположен в конце функции, непосредственно перед оператором возврата из функции (или возвращаемого значения). Такая рекурсия называется хвостовой или концевой. Хвостовая рекурсия является простейшей формой рекурсии, поскольку она действует подобно циклу [18.7]. Если в программе имеется хвостовая рекурсия, то ее лучше преобразовать к итерации.

Отметим особенности работы рекурсивных функций, характерных для тех языков программирования, которые поддерживают рекурсию. К этим языкам относится и язык С.

Когда функция вызывает сама себя (когда имеем дело с рекурсивной функцией), новый набор локальных переменных и параметров размещается в памяти в стеке, а код функции выполняется с самого своего начала, причем используются именно эти новые переменные. При рекурсивном вызове функции новая копия ее кода не создается. Новыми являются только значения, которые использует данная функция. При каждом возвращении из рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и сразу за рекурсивным вызовом возобновляется работа функции [18.8]. Выполнение функции возобновляется с "внутренней" точки ее вызова.

Общая схема определения рекурсивной функции

  • Существует условие, при котором функция выполняет свою задачу с использованием рекурсивных вызовов, соответствующих одной или нескольких "уменьшенным" версиям задачи.
  • Существует также условие, которое будет удовлетворено и при котором функция выполняет свою задачу без рекурсивных вызовов. Это условие называется базовым или условием останова [18.2,18.4-18.5-18.6].
    •

    Рассмотрим некоторые определения, относящиеся к рекурсии. Максимальное число рекурсивных вызовов без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. В практических приложениях важно убедиться, что максимальная глубина рекурсий не только конечна, но и достаточно мала [18.11].

    Существует три разных формы рекурсивных программ:

  • Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске).
  • Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).
  • Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий, как на рекурсивном спуске, так и на рекурсивном возврате).
    •

    Понятие рекурсии сходно с понятием математической индукции. У рекурсии, как и у математической индукции, есть база – аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии – способ сведения задачи к более простым задачам.

    Рекурсия обладает своими преимуществами и недостатками. Одно из преимуществ рекурсии состоит в том, что она предлагает простейшее решение некоторых задач программирования. Один из недостатков рекурсии заключается в том, что некоторые рекурсивные алгоритмы могут довольно-таки быстро исчерпать ресурс памяти компьютера. Наряду с этим рекурсию трудно документировать и поддерживать [18.7].

    Главное при оформлении рекурсивной функции – это правильное задание условия выхода из рекурсивных вызовов. Если при зацикливании программы при операторе цикла компьютер может выполнять такой цикл, не реагируя на любые действия пользователя, то при зацикливании из-за неправильного оформления рекурсивной функции неизбежно происходит аварийный останов, когда будет исчерпан объем оперативной памяти, которая выделяется при каждом рекурсивном вызове. При этом следует всегда помнить, что даже при правильном оформлении рекурсивной функции, необходимо учитывать объем вычислительной работы. Например, расчет факториала целого положительного числа – трудоемкая операция. В математической постановке задачи нет ничего сложного, но в случае программирования этого процесса для различных систем и компьютеров имеются свои ограничения. Например, это касается рекурсивного вычисления факториала.

    В то же время для некоторых задач рекурсивные функции вполне оправданы. В частности динамические информационные структуры включают рекурсивность в само определение обрабатываемых данных. Именно для таких данных применение рекурсивных алгоритмов не имеет конкуренции со стороны итерационных методов [18.6].

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

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

    int fact (int n) {
  if (n == 0)
    return 1;
    else
    return n * fact (n - 1);
}

    Эта исходная функция fact() не имеет хвостовой рекурсии т. к. выполняется перемножение после рекурсивного вызова (умножение на n ). Для исключения рекурсии сначала приведем fact () к виду с хвостовой рекурсией, например

    int fact (int n) {
  return fact_w (1,n);
}

    Вспомогательная функция fact_w () будет содержать хвостовую рекурсию. Ее программный код:

    int fact_w (int r, int n) {
  if (n == 0)
    return r;
  else
    return fact(r*n,n-1);
}

    В функции fact_w() хвостовая рекурсия присутствует в силу рекурсивного обращения только к самой функции в операторе return.

    Обратимся к известному положению об исключении хвостовой рекурсии: если функция f(x) содержит в конце рекурсивный вызов в виде return f(y), то рекурсию можно исключить путем присваивания x = y, и перехода goto на начало функции [18.14]. Программный код исключения хвостовой рекурсии:

    int fact_w (int r, int n) {
met:
  if (n == 0)
    return r;
  else {
    r = r*n;
    n = n-1;
    goto met;
  }
}

    Использование оператора goto нежелательно с точки зрения современных представлений и методов структурного программирования, преобразуем конструкцию с goto к циклу:

    int fact_w (int r, int n) {
  while (n != 0) {
    r = r*n;
    n = n-1;
  }
  return r;
}

    В качестве окончательной оптимизации можно исключить и вспомогательную функцию fact_w (), выполнив подстановку тела функции в точку ее вызова (inlining). В итоге получим следующий программный код функции, вычисляющей факториал числа:

    /*
* Оптимизация функции
* вычисления факториала числа
*/
int fact (int n)
 {
  int r = 1;
  while (n != 0) {
    r = r*n;
    n = n-1;
  }
  return r;
}

    В приведенной функции нет ни рекурсивных вызовов, ни оператора goto.

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

    Каждая функция в программе на языке С находится на одном уровне с остальными функциями, составляющие программный проект. Каждая из них может вызвать любую другую функцию или быть вызванной другими функциями. По этой причине функция main() может вызывать сама себя в рамках некоторой рекурсии или быть вызванной из других функций, хотя подобное встречается достаточно редко [18.7]. Следует только иметь в виду, что когда программа составляется из нескольких функций, выполнение этой программы начинается с первого оператора функции main().

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

    Практическая часть

    Пример 1. Напишите рекурсивную функцию определения наибольшего общего делителя двух целых чисел.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <stdlib.h>

// Прототип рекурсивной функции 
int gcd(int a, int b);

int main (void) {
	int a = 0, b = 0;
	int in;

// Проверка ввода двух целых чисел
		do {
printf("\n Enter the two different natural numbers, through the gap: ");
		in = scanf_s("%d%d", a, b);

		if (in != 2) {
		printf("\n Error input. Press any key to exit: ");
			_getch();
			exit(1);
		}

		if ( (a != b)  (b != 0) )
			break;
		if (b == 0)
			a = b;

	} while ( (a == b) );

// Вывод результата на консоль 
	printf("\n a = %d, b = %d, GCD = %d; \n", a, b, gcd(a,b));
	
	printf("\n\n Press any key: ");
	_getch();
	return 0;
}

// Определение рекурсивной функции
int gcd(int a, int b) {
	if ( (a % b) == 0) 
		return b;
	else 
		return gcd(b, a % b);
}

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

    Возможный результат выполнения программы приведен на рис 18.1.

    (рис 18.1) Наибольший общий делитель для чисел 123 и 45

    Задание 1

  • В программе оператор if используйте для рекурсивных вызовов, а оператор else используйте как условие останова.
  • B программу включите определение количества рекурсивных вызовов.
  • Видоизмените программу для случая ошибочного ввода чисел, сделайте, чтобы было повторное приглашение на ввод чисел.
  • Напишите функцию вычисления наибольшего общего делителя на основе итерации (с использованием операторов цикла).
    •

    Пример 2. Напишите рекурсивную функцию, которая выводит на консоль двоичный эквивалент целого десятичного числа, введенного пользователем с клавиатуры.

    Для решения примера отметим, что в двоичной системе счисления числа представлены в виде суммы степеней 2. Подобно тому, как в десятичной системе счисления число 234 означает $$2\times10^2 + 3\times10^1 + 4\times10^0$$, число 101 в двоичной системе означает $$1\times2^2 + 0\times2^1 + 1\times2^0$$ [7]. В двоичных числах используются только цифры 0 и 1.

    Очевидно, что за основу решения примера следует использовать целочисленное деление. Если введено число n, то оно может быть, либо четным, либо нечетным. Тогда остаток от деления на 2 будет равняться нулю для четных чисел и единице – для нечетных.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <locale.h>

// Прототип рекурсивной функции
void dec2bin(unsigned long int);

int main (void) {
	unsigned long int n;

	setlocale(LC_ALL, "Russian"); // для русских шрифтов

	printf("\n\t Введите целое десятичное число\n \
 (или не числовой символ для завершения программы): ");
	while (scanf_s("%ul", n) == 1)
	{
		printf("\n Двоичный эквивалент: ");
		dec2bin(n);

	printf("\n\n\t Введите целое десятичное число\n \
 (или не числовой символ для завершения программы): ");

	}

	return 0; // выход из программы
}

// Определение рекурсивной функции
void dec2bin(unsigned long int n) {
	int r;
	r = n % 2;

	if (n >= 2 ) 
		dec2bin(n/2);

	printf("%d", r);
	
	return;
}

    В программе шаги рекурсии осуществляются при условии, что аргумент рекурсивной функции больше или равен двум. Как только это условие нарушается, происходит распечатка результата и выход из функции. Например, при n = 10 остаток от целочисленного деления r = 10%2 = 0. В то же время аргумент функции dec2bin() будет равняться 5. Тогда остаток от целочисленного деления r = 5%2 = 1. Далее аргумент функции будет равняться 2 (5/2), так как аргумент функции определен через целое число. Остаток от целочисленного деления r = 2%2 = 0. Теперь аргумент рекурсивной функции будет равен 1, что прерывает рекурсивные вызовы функции (нарушается условие проверки оператором if ). Остаток от деления r = 1%2 = 1. Вывод результата на консоль будет осуществляться из стека по дисциплине LIFO (Last Input First Output – последним вошел, первым вышел).

    Пример выполнения программы показан на рис 18.2.

    (рис 18.2) Преобразование десятичных чисел в двоичные эквиваленты

    Задание 2

  • Какой тип рекурсии используется в приведенной программе?
  • В программу включите защиту от ввода отрицательных целых чисел.
  • Вывод результатов преобразования десятичных чисел в двоичные эквиваленты осуществите в текстовый файл с именем compX.txt, где Х – номер компьютера (1, 2, ...), на котором выполняется лабораторная работа. В текстовый файл занести также и преобразуемое десятичное число.
  • В программе вместо функции printf(), как функции вывода результата, примените функцию putchar().
  • В программу внесите изменения для подсчета количества рекурсивных вызовов.
  • Напишите программу преобразования десятичного числа в свой двоичный эквивалент на основе не рекурсивного подхода, а с помощью операций с разрядами.
  • Напишите программу с рекурсивной функцией вывода на консоль десятичного числа для введенного пользователем его двоичного эквивалента.
    •

    Пример 3. С использованием косвенной рекурсии напишите программу по решению следующей задачи. Строка состоит из клеток, пронумерованных от 1 до n. Состояние клетки можно изменить – если она пуста, поставить в нее шащку (занять ее), иначе убрать из нее шашку (освободить ее). Вначале строка пуста. Нужно занять все клетки, соблюдая следующее правило. Изменение клетки допустимо, если она имеет номер 1 или расположена непосредственно после занятой клетки, имеющей минимальный номер среди занятых клеток.

    Вход. Целое n, $$1\leqslant n \leqslant15$$.

    Выход. Последовательность элементов вида +i или –i, обозначающих соответственно занять клетку i и освободить клетку i [9].

    Например, при n = 3 выход имеет вид +1+2–1+3+1.

    В основу решения задачи положен программный код из [9].

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>   // для getch();
#include <stdlib.h> // для exit();

// Прототипы функций
void fillOnly(int);
void free_n(int);
void fill_n(int);

int main (void)
 {
	int n = 1; // размер строки
	int in = 1; // контроль ввода n

	printf("\n Enter a length of string (naturel number): ");
	in = scanf_s("%i", n);

	if (in != 1 || n < 1 || n > 15)
     {
		printf("\n Error input. Press any key to exit: ");
		_getch();
		exit(0);
	}
	puts("\n\tResult:");

	fill_n(n);

	printf("\n\n Press any key to exit: ");
	_getch();
	return 0;
}
   // Объявления функций
   // 1-я функция
void fillOnly(int n) {
	if (n == 1)
		printf("\t%+3d\n", 1);
	else {
		fillOnly(n-1);
		printf("\t%+3d\n", n);
		free_n(n-1);
	}
}

// 2-я функция
void free_n(int n)
 {
	if (n == 1)
		printf("\t%+3d\n", -1);

	else {
		fillOnly(n-1);
		printf("\t%+3d\n", -n);
		free_n(n-1);
	}
}

//3-я функция
void fill_n(int n)
 {
	if (n == 1)
		printf("\t%+3d\n", 1);
	else {
		if (n == 2)
			printf("\t%+3d\n\t%+3d\n", 1, 2);
		else {
			fillOnly(n-1);
			printf("\t%+3d\n", n);
			fill_n(n-2);
		}
	}
}

    В программе вывод результата на консоль выполнен в виде столбца. Для этого используется эскейп-последовательность \t в функциях printf(). Форматный вывод значений в функциях printf() выполнен с помощью спецификации %+3d, что позволяет автоматически устанавливать знаки чисел, под которые отводятся 3 позиции.

    Как видно из приведенного программного кода, в каждой из функций имеется вызов самой функции и других функций. Это указывает на косвенное обращение к функциям.

    Пример выполнения программы показан на рис 18.3.

    (рис 18.3) Пример заполнения и освобождения клеток

    Задание 3

  • В программе укажите рекурсивные функции. Объясните работу рекурсивных функций.
  • Проверьте работу программы при смене порядка объявлений функций.
  • Проверьте работу программы без использования прототипов функций.
  • Для случая, когда $$n \leqslant 5$$, предусмотрите вывод результата в строку, а не в столбец.
  • В программу добавьте программный код для подсчета рекурсивных вызовов, каждой из рекурсивных функций.
  • остройте зависимость числа комбинаций заполнения и освобождения клеток от введенного числа n.
    •

    Пример 4. "Ханойская башня". Напишите программу по решению следующей задачи. Имеется пирамида из n колец, лежащих на основании А (на стержне, на столбе) одно на другом в порядке убывания размеров. Кольца должны быть перемещены на основание В в том же порядке, в котором они были на основании А, при использовании "промежуточного" основания С. Единственными разрешенными перемещениями являются такие, при которых кольцо, взятое с вершины одной из пирамид, помещается на большее кольцо, либо на пустое основание. Осуществить выдачу на печать (на консоль, в текстовый файл) последовательности перемещений колец.

    "Ханойская башня" – известная задача. Алгоритм решения этой задачи достаточно подробно описан в [18.10].

    Решение задачи "Ханойская башня"

    Для рекурсивного решения этой задачи следует пройти три этапа.

    1-й этап – параметризация. В этой задаче естественным параметром является n – число колец. В число параметров можно включить также и три основания: А (исходное), В (конечное), С (промежуточное).

    2-й этап – поиск тривиальных случаев. Здесь тривиальным случаем будет такой, при котором n = 0; в этом случае просто нечего делать.

    3-й этап – редукция общего случая к более простому. Здесь надо отметить, что n колец могут быть перемещены с А на В следующим путем:

  • переноса (рекурсивно) n – 1 колец с вершины А (исходное основание) на С ("промежуточное" основание) с учетом правил: основание В (конечная цель) используется как промежуточное основание;
  • перемещения на В кольца (наибольшего диаметра), оставшегося на А;
  • переноса (рекурсивно) n – 1 других колец с С на В при соблюдении правил с А в качестве промежуточного основания.
    •

    Алгоритм решения задачи запишем в следующем виде:

    hanoi(n–1, A, C, B);
переместить (A, B);
hanoi(n–1, C, B, A);

    где hanoi() – имя рекурсивной функции [18.10].

    Пример промежуточного положения Ханойской башни при n = 4 показан на рис 18.4.

    (рис 18.4) Промежуточное положение Ханойской башни при n = 4

    Число элементарных перемещений равно 2n – 1, где n – количество исходных дисков [18.10]. С увеличением n число перемещений быстро нарастает.

    На рис 18.5 показана зависимость элементарных перемещений от числа дисков.

    (рис 18.5) Зависимость элементарных перемещений от числа дисков

    С учетом того, что перемещение диска – это есть рекурсивный вызов функции, то на каждый вызов требуется определенное время. Практически с любым конечным малым временем обработки рекурсивного вызова общее время работы рекурсивной функции для большого количества дисков n становится не выполнимым на существующих современных компьютерах. В соответствии с легендой конец света наступит при перемещении 64 дисков [18.10].

    В связи со степенным ростом числа рекурсивных вызовов в программе ограничимся величиной n = 15.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <math.h>

// Пртотип рекурсивной функции
void hanoi(int n,char a, char b, char c);

int main(void) 
{
     char a = 'A'; // исходное основание
     char b = 'B'; // конечное основание
     char c = 'C'; // промежуточное основание

	double n; // число дисков
	char str[81] = "15"; // инициализация строки

puts("\n Hanoi Tower; A - starting; B - end; C - intermediate");

	while (0.01) {       // 0.01 - как истинное значение
 		printf("\n Enter the number of disks: ");
		scanf_s(" %s",str, 80);
		n = atof(str);
		
		if ( n <= 0 || ceil(n) != n) {
			printf("\n Error input. Press any key: ");
			_getch();
			continue;
		}

		else if (n > 15.0) {
			printf("\n Very large number. Press any key: ");
			_getch();
			continue;
		}
		
         else
			break;
	}
	
     puts("\n Elementary transferences:");
	hanoi((int)n, a, b, c);

  
  printf("\n\n Press any key: ");
  _getch();
  return 0;
}

// Определение рекурсивной функции
void hanoi(int num, char a, char b, char c)
{
  if(num > 0) {

    hanoi(num-1,a,c,b);

    printf("\t%c --> %c\n",a,b);

    hanoi(num-1,c,b,a);

  }
  
}

    Результат выполнения программы при n = 5 показан на рис 18.6.

    (рис 18.6) Перемещения дисков в Ханойской башне при n = 5

    Задание 4

  • Определите тип рекурсии, используемой в программе.
  • Для случая, когда не все элементарные перемещения выводятся на экран дисплея, предусмотрите вывод результата программы в текстовый файл с именем compX.txt, где X – номер компьютера, на котором выполняется лабораторная работа.
  • Программным путем выполните подсчет общего количества обращений к рекурсивной функции. Сделайте также вывод порядкового номера перемещения на экран дисплея. Порядковый номер расположите слева от элементарного перемещения. Построить (в MS Excel или в MATLAB) зависимость количества обращений к рекурсивной функции от заданного числа дисков.
  • Измените аргументы рекурсивной функции: включить переменные типа int для определения имени (нумерации) основания.
  • Измените условие задачи "Ханойская башня". Сначала исходным основанием считать В, конечным С, промежуточным А. Затем принять за исходное основание С, промежуточным В, конечным А.
    •

    Пример 5. "Задача о рюкзаке". Есть 10 предметов, о которых известны их веса и стоимости. Требуется поместить в рюкзак предметы таким образом, чтобы они не превысили допустимый вес для рюкзака при максимальной стоимости выбранных предметов. Исходные параметры модели – характеристики предметов взяты из [11] и приведены в табл. 18.1.

    Характеристики предметов
    № п/п 1 2 3 4 5 6 7 8 9 10
    Вес 10 11 12 13 14 15 16 17 18 19
    Стоимость 18 20 17 19 25 21 27 23 25 24

    Данная задача широко известна [18.9-18.10-18.11], она еще называется задачей о ранце, или вариант с английского – "knapsack problem". Предполагается, что один и тот же предмет не может быть взят несколько раз.

    Для решения поставленной задачи используем рекурсивный алгоритм, описанный в [18.11], где также приводится фрагмент программы на языке программирования MODULA – 2.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <locale.h>

const int limW = 20; // предельный вес выбранных предметов
enum {N = 10}; // количество предметов

typedef struct {
	int weight; //// вес или размер предметов
	int value; //// стоимость или ценность предметов
} object;

// Формирование структурного типа с параметрами модели
object obj[] = {10,18, 11,20, 12,17, 13,19, 14,25, 15,21, 16,27, 17,23, 18,25, 19,24};

int maxv; // для инициализации стоимости предметов

// Рекурсивная функция
int TRY (int i, int tw, int av) {
	// Попытка включения предмета
	if (tw + obj[i].weight <= limW) 
		if (i < N-1) 
			TRY(i+1, tw + obj[i].weight, av );
		   
          else if (av > maxv) 
			maxv = av;
		// Попытка исключения предмета
	if (av > maxv + obj[i].value) 
		if (i < N-1) 
			TRY(i+1, tw, av - obj[i].value);
		else 
			maxv = av - obj[i].value;
	return maxv;	
}

// Главная функция программы
int main (void) {
	int i, price;
	int sumw = 0;
	int sumv = 0;
	setlocale(LC_ALL, "rus");

	maxv = obj[0].value; // инициализации стоимости предметов
	puts("\n\t\t\tЗАДАЧА О РЮКЗАКЕ");
	puts("\t\t  Характеристика предметов");
	for (i = 0; i < (4*N + 12); i++)
		printf("%s", "_");

	printf("\n\n %12s", "Вес:");
	for (i = 0; i < N; i++) {
		sumw += obj[i].weight;
		printf(" %3d", obj[i].weight); }

	printf("\n %12s", "Стоимость:");
	for (i = 0; i < N; i++) {
		sumv += obj[i].value;
		printf(" %3d", obj[i].value); }
	printf("\n ");
	for (i = 0; i < (4*N + 12); i++)
		printf("%s", "_");

printf("\n\n %32s: %d\n", "Общий вес всех предметов", sumw);
printf(" %32s: %d\n", "Общая стоимость всех предметов", sumv);
	printf(" %32s: %d\n ", "Допустимый вес рюкзака", limW);
	     for (i = 0; i < (4*N + 12); i++)
      printf("%s", "_");
	// Вызов рекурсивной функции с начальными параметрами
	price = TRY(0,0,sumv);
printf("\n\n  Стоимость выбранных предметов: %d\n ", price );
	for (i = 0; i < (4*N + 12); i++)
		printf("%s", "_");

	printf("\n\n ... Нажмите любую клавишу: ");
	_getch();
	return 0;
}

    Пример выполнения программы показан на рис 18.7.

    (рис 18.7) Пример выполнения программы решения задачи о рюкзаке

    Представленная программа основана на следующем алгоритме [18.11]. В рекурсивной функции TRY() определены две ситуации для выбора предмета в рюкзак. Если речь идет о включении то объект (предмет со своим весом и стоимостью) можно включить в выборку для укладки в рюкзак, если он подходит по весовым ограничениям. Если он не подходит, то попытки добавить еще один объект в текущую выборку можно прекратить. Когда же речь идет об исключении, то критерием приемлемости, т. е. возможности продолжения построения текущей выборки, будет то, что после данного исключения общая ценность (стоимость) будет не меньше полученного до этого момента оптимума. В данной программе реализована схема с возвратами, использующая некоторые ограничения для уменьшения роста потенциального дерева поиска, называется алгоритмом ветвей и границ [18.11].

    Задание 5

  • Подсчитайте количество рекурсивных вызовов функции TRY() в зависимости от величины допустимого веса рюкзака, начиная от 10 до 120 с шагом в 10 условных единиц. Постройте график полученной зависимости (в MS EXCEL или в MATLAB).
  • Рекурсивную функцию TRY() расположите в отдельном файле с именем compX.c, где Х – номер компьютера, на котором выполняется лабораторная работа.
  • Сформирйте массив данных о предметах по случайному равномерному закону из интервала [10; 20*Х], где Х – номер компьютера, на котором выполняется лабораторная работа. Размер массива выберите случайно из следующего интервала натуральных чисел: [10; 18].
  • В программу внесите изменения, которые бы позволили определить номера предметов, отобранные в рюкзак. Соответственно укажите вес и стоимость каждого предмета.
    •

    Пример 6. Напишите программу сортировки одномерного массива целых чисел на основе рекурсивного алгоритма быстрой сортировки Хоара.

    Суть алгоритма быстрой сортировки заключается в следующем. Выбираем наугад какой-либо элемент х исходного массива. Будем просматривать слева наш массив до тех пор, пока не встретим элемент ai > x, затем будем просматривать массив справа, пока не встретим $$a_i \leqslant х$$. Поменяем местами эти два элемента и продолжим процесс просмотра и обмена до тех пор, пока оба просмотра не встретятся. В результате исходный массив окажется разбитым на две части, левая часть будет содержать элементы меньше или равные х, а правая часть – элементы больше х. Применив эту процедуру разделения к левой и правой частям массива от точки встречи, получим четыре части и т. д., пока в каждой части окажется только один элемент [18.12]. В качестве граничного элемента х для разделения обычно выбирают средний элемент массива.

    Программный код решения примера:

    /* Быстрая сортировка Хоара.
* Рекурсивный вариант.
*/

#include <stdio.h>
#include <conio.h>

// Массив, подлежащий сортировке по возрастанию
int A[] = {1, 5, 7, -5, 0, 12, 8, 5, 4, -10, 3, 6, 18};

// Прототип рекурсивной функции
void Quick_Sort(int A[], int L, int R);

int main (void) {
	int i;
	int N;

	N = sizeof(A)/sizeof(A[0]);

	puts("\n\t\t QUICK SORT");
	printf("\n\t The original array of size %d:\n ", N);
	for (i = 0; i < N; i++)
		printf(" %3d ", A[i]);
     
// Вызов рекурсивной функции сортировки
	Quick_Sort(A, 0, N-1);

	printf("\n\n\t The sorting array:\n ");
	for (i = 0; i < N; i++)
		printf(" %3d ", A[i]);

	printf("\n\n ... Press any key: ");
	_getch();
	return 0;
}
// Определение рекурсивной функции
void Quick_Sort(int A[], int L, int R) {
	int i, j, k;
	int x; // граничный элемент для разделения массива
	i = L;
	j = R;
	x = A[(int)(L + R)/2];
	do { while (A[i] < x)
		i++;
	while (x < A[j])
		j--;
	if (i <= j) {
		k = A[i]; A[i] = A[j]; A[j] = k;
		i++; j--;
	}
	} while (i < j);

	if (L < j)
		Quick_Sort(A, L, j);

	if (i < R)
		Quick_Sort(A, i, R); 
}

    Пример выполнения программы показан на рис 18.8.

    (рис 18.8) Пример быстрой сортировки одномерного массива

    Задание 6

  • В программу внесите изменения для сортировки вещественных данных.
  • В программу внесите изменения для сортировки массива по убыванию.
  • Рекурсивную функцию программы разместите во внешнем файле с именем compX.c, где Х – номер компьютера, на котором выполняется лабораторная работа.
  • 4Размерность массива, подлежащего сортировке, и данные массива задайте случайно из интервалов [10; 100] и [10Х; 50Х], где Х – номер компьютера, на котором выполняется лабораторная работа.
  • Подсчитайте количество рекурсивных вызовов при сортировке массивов, задаваемых случайным образом.
    •

    Пример 7. Напишите программу сортировки одномерного массива целых чисел на основе рекурсивного алгоритма слиянием.

    При алгоритме слиянием сортировку производят по частям, а затем соединяют отдельные части в единое целое [18.5].

    Выберем следующую схему разбиения данных. Будем разрезать массив данных на две равные части, образуя два подмассива. Затем сортировка слиянием рекурсивно вызывает себя для каждого из двух подмассивов. Конечным шагом является слияние двух сортированных подмассивов в один сортированный массив [18.13].

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

    Алгоритм сортировки слиянием может быть использован при сортировке внешних данных, например данных, записанных в отдельные файлы [18.5].

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <stdlib.h>

// Заданный произвольный числовой массив
int A[] = {9, 3, 4, 5, 8, 1, 0, 3, 2, -3, 12, 10, -7, 8};

// Основная функция сортировки, merge - сливать, соединять
void merge (int arr[],int *temp,int start,int mid,int end)
 {
	int i = 0; // для временного массива
	int i_lower = start;
	int i_upper = mid + 1;
	int i_arr = start;

	// Пока ни один из подмассивов не пуст
	while ( (i_lower <= mid)  (i_upper <= end) ) {
		if (arr[i_lower] < arr[i_upper])
			temp[i++] = arr[i_lower++];
		else
			temp[i++] = arr[i_upper++];
	} // end while

	// Случай, когда в одном из подмассивов остались элементы
	   if (i_lower <= mid) {
		// assert (i_upper > end);
		for ( ; i_lower <= mid; temp[i++] = arr[i_lower++]);
	}
	   else 
	for ( ; i_upper <= end; temp[i++] = arr[i_upper++]) ;
	// Когда размер массива равен end - start + 1
		if (i == end - start + 1)
	for ( i = 0; i_arr <= end;  arr[i_arr++] = temp[i++]) ;
} // end merge

// Рекурсивная сортировка подмассивов
void sub (int arr[], int *temp, int head, int tail ) {
	// head - голова
	// tail - хвост
	int mid;
	if (head >= tail)
		return;
	if (tail > head) {
		// Средняя точка массива
		mid = (head + tail) / 2;
		// assert ( (mid >= head)  (mid <= tail) );
		if (mid >= head  mid <= tail) {
			// Сортировка подмассивов
			sub (arr, temp, head, mid);
			sub (arr, temp, mid+1, tail);
			// Объединение результатов
			merge (arr, temp, head, mid, tail);
		}
	}
} // end sub

// Функция как интерфейс, для удобства вызова программы
void merge_sort (int arr[], int size)  {
	int head = 0;
	int tail = size - 1;
	int *temp;
	temp = (int *) malloc (size*sizeof(int)); 
	sub (arr, temp, head, tail);
	free(temp);
} 

int main (void) {
	int i;
	int N;

	N = sizeof(A)/sizeof(A[0]);
	// Вывод на консоль исходного массива
	printf("\n\t The original array of size %d:\n ", N);
	for (i = 0; i < N; i++)
		printf(" %2d", A[i]);

	// Вызов функции для сортировки массива
	merge_sort (A, N);
	// Вывод на консоль отсортированного массива
	printf("\n\n\t After sorting:\n ");
	for (i = 0; i < N; i++)
		printf(" %2d", A[i]);

	printf("\n\n ... Press any key: ");
	_getch();
	return 0;
}

    Пример выполнения программы показан на рис 18.9.

    (рис 18.9) Пример сортировки слиянием одномерного массива

    В алгоритме сортировки слиянием можно выделить три этапа.

  • Сортируемый массив разбивается на две половины примерно одинакового размера.
  • Каждая из получившихся половин сортируется отдельно (каким-либо известным алгоритмом, в том числе и с помощью алгоритма слиянием ).
  • Два упорядоченных массива половинного размера соединяются в один. Рекурсивное разбиение заданного массива происходит до тех пор, пока размер массива не достигнет единицы. Далее решается задача – нетривиальная задача – соединение двух упорядоченных массивов в один.
    •

    Алгоритм сортировки слиянием был изобретен Джоном фон Нейманом в 1945 г.

    Сортировка слиянием считается предпочтительной в случае, когда требуется застраховаться от наихудшего случая, возможного при использовании быстрой сортировки [18.12].

    Задание 7

  • Все вспомогательные функции программы разместите во внешние файлы с именами compX_1.c, compX_2.c и т. д., где Х – номер компьютера, на котором выполняется лабораторная работа (1, 2, ...). Протестируйте программу на контрольном примере. Подсчитайте количество рекурсивных вызовов.
  • Подготовьте два не отсортированных массива и произведите их слияние в один отсортированный массив. Данные массивов задаются случайно по равномерному закону из интервалов [–5Х; 5Х] и [0; 10Х], где Х – номер компьютера, на котором выполняется лабораторная работа (1, 2,...). Размерности массивов должны задаваться с клавиатуры из интервала [10; 20].
  • Напишите программу по сортировке слиянием двух массивов, расположенных в текстовых файлах (внешняя сортировка слиянием). Результат сортировки разместите также в текстовый файл с именем compX.txt, где Х – номер компьютера, на котором выполняется лабораторная работа.
    •

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

  • Когда следует применять рекурсивные алгоритмы?
  • Какие известны методы и приемы устранения "хвостовой" рекурсии?
  • Какие проблемы могут возникать при реализации рекурсивных алгоритмов на электронных вычислительных машинах?
  • В чем отличие глубины рекурсии от рекурсивного вызова?
  • Какие задачи в программировании можно назвать, где применение рекурсии оправдано?
    •
    Страницы:

    Теоретическая часть

    Рекурсивные функции (лат. recursio – возвращение) – в вычислительной математике – функции, определенные на множестве натуральных чисел и принимающие значения того же множества [18.1].

    Рекурсивный алгоритм – это алгоритм, решающий задачу путем решения одного или нескольких более узких вариантов той же задачи [18.2]. Функция называется рекурсивной, если в ее определении содержится вызов этой же функции [18.3]. Рекурсивная функция может вызывать саму се6я или непосредственно, или косвенно через другую функцию [18.4]. Рекурсии целесообразно применять в задачах, которые можно разбить на множество меньших подобных задач [18.5]. Рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей с боле простыми данными.

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

    Рекурсивный подход обычно предпочитается итеративному подходу в тех случаях, когда рекурсия более естественно отражает математическую сторону задачи и приводит к программе, которая проще для понимания и отладки. Другой причиной для выбора рекурсивного решения является то, что итеративное решение может не быть очевидным [18.4].

    Наличие в задаче рекуррентного соотношения позволяет использовать рекурсию. Например, арифметическая прогрессия – последовательность чисел, в которой разность между последующими и предыдущими членами остается неизменной и называется разностью прогрессии [18.1]. То есть каждый следующий член прогрессии равен предыдущему, увеличенному на разность прогрессии.

    Различают прямую и косвенную рекурсию. Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции. Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций [18.6]. Все функции, входящие в цепочку, тоже считаются рекурсивными.

    В рекурсии простейшей формы рекурсивный вызов расположен в конце функции, непосредственно перед оператором возврата из функции (или возвращаемого значения). Такая рекурсия называется хвостовой или концевой. Хвостовая рекурсия является простейшей формой рекурсии, поскольку она действует подобно циклу [18.7]. Если в программе имеется хвостовая рекурсия, то ее лучше преобразовать к итерации.

    Отметим особенности работы рекурсивных функций, характерных для тех языков программирования, которые поддерживают рекурсию. К этим языкам относится и язык С.

    Когда функция вызывает сама себя (когда имеем дело с рекурсивной функцией), новый набор локальных переменных и параметров размещается в памяти в стеке, а код функции выполняется с самого своего начала, причем используются именно эти новые переменные. При рекурсивном вызове функции новая копия ее кода не создается. Новыми являются только значения, которые использует данная функция. При каждом возвращении из рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и сразу за рекурсивным вызовом возобновляется работа функции [18.8]. Выполнение функции возобновляется с "внутренней" точки ее вызова.

    Общая схема определения рекурсивной функции

  • Существует условие, при котором функция выполняет свою задачу с использованием рекурсивных вызовов, соответствующих одной или нескольких "уменьшенным" версиям задачи.
  • Существует также условие, которое будет удовлетворено и при котором функция выполняет свою задачу без рекурсивных вызовов. Это условие называется базовым или условием останова [18.2,18.4-18.5-18.6].
    •

    Рассмотрим некоторые определения, относящиеся к рекурсии. Максимальное число рекурсивных вызовов без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. В практических приложениях важно убедиться, что максимальная глубина рекурсий не только конечна, но и достаточно мала [18.11].

    Существует три разных формы рекурсивных программ:

  • Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске).
  • Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).
  • Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий, как на рекурсивном спуске, так и на рекурсивном возврате).
    •

    Понятие рекурсии сходно с понятием математической индукции. У рекурсии, как и у математической индукции, есть база – аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии – способ сведения задачи к более простым задачам.

    Рекурсия обладает своими преимуществами и недостатками. Одно из преимуществ рекурсии состоит в том, что она предлагает простейшее решение некоторых задач программирования. Один из недостатков рекурсии заключается в том, что некоторые рекурсивные алгоритмы могут довольно-таки быстро исчерпать ресурс памяти компьютера. Наряду с этим рекурсию трудно документировать и поддерживать [18.7].

    Главное при оформлении рекурсивной функции – это правильное задание условия выхода из рекурсивных вызовов. Если при зацикливании программы при операторе цикла компьютер может выполнять такой цикл, не реагируя на любые действия пользователя, то при зацикливании из-за неправильного оформления рекурсивной функции неизбежно происходит аварийный останов, когда будет исчерпан объем оперативной памяти, которая выделяется при каждом рекурсивном вызове. При этом следует всегда помнить, что даже при правильном оформлении рекурсивной функции, необходимо учитывать объем вычислительной работы. Например, расчет факториала целого положительного числа – трудоемкая операция. В математической постановке задачи нет ничего сложного, но в случае программирования этого процесса для различных систем и компьютеров имеются свои ограничения. Например, это касается рекурсивного вычисления факториала.

    В то же время для некоторых задач рекурсивные функции вполне оправданы. В частности динамические информационные структуры включают рекурсивность в само определение обрабатываемых данных. Именно для таких данных применение рекурсивных алгоритмов не имеет конкуренции со стороны итерационных методов [18.6].

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

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

    int fact (int n) {
  if (n == 0)
    return 1;
    else
    return n * fact (n - 1);
}

    Эта исходная функция fact() не имеет хвостовой рекурсии т. к. выполняется перемножение после рекурсивного вызова (умножение на n ). Для исключения рекурсии сначала приведем fact () к виду с хвостовой рекурсией, например

    int fact (int n) {
  return fact_w (1,n);
}

    Вспомогательная функция fact_w () будет содержать хвостовую рекурсию. Ее программный код:

    int fact_w (int r, int n) {
  if (n == 0)
    return r;
  else
    return fact(r*n,n-1);
}

    В функции fact_w() хвостовая рекурсия присутствует в силу рекурсивного обращения только к самой функции в операторе return.

    Обратимся к известному положению об исключении хвостовой рекурсии: если функция f(x) содержит в конце рекурсивный вызов в виде return f(y), то рекурсию можно исключить путем присваивания x = y, и перехода goto на начало функции [18.14]. Программный код исключения хвостовой рекурсии:

    int fact_w (int r, int n) {
met:
  if (n == 0)
    return r;
  else {
    r = r*n;
    n = n-1;
    goto met;
  }
}

    Использование оператора goto нежелательно с точки зрения современных представлений и методов структурного программирования, преобразуем конструкцию с goto к циклу:

    int fact_w (int r, int n) {
  while (n != 0) {
    r = r*n;
    n = n-1;
  }
  return r;
}

    В качестве окончательной оптимизации можно исключить и вспомогательную функцию fact_w (), выполнив подстановку тела функции в точку ее вызова (inlining). В итоге получим следующий программный код функции, вычисляющей факториал числа:

    /*
* Оптимизация функции
* вычисления факториала числа
*/
int fact (int n)
 {
  int r = 1;
  while (n != 0) {
    r = r*n;
    n = n-1;
  }
  return r;
}

    В приведенной функции нет ни рекурсивных вызовов, ни оператора goto.

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

    Каждая функция в программе на языке С находится на одном уровне с остальными функциями, составляющие программный проект. Каждая из них может вызвать любую другую функцию или быть вызванной другими функциями. По этой причине функция main() может вызывать сама себя в рамках некоторой рекурсии или быть вызванной из других функций, хотя подобное встречается достаточно редко [18.7]. Следует только иметь в виду, что когда программа составляется из нескольких функций, выполнение этой программы начинается с первого оператора функции main().

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

    Практическая часть

    Пример 1. Напишите рекурсивную функцию определения наибольшего общего делителя двух целых чисел.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <stdlib.h>

// Прототип рекурсивной функции 
int gcd(int a, int b);

int main (void) {
	int a = 0, b = 0;
	int in;

// Проверка ввода двух целых чисел
		do {
printf("\n Enter the two different natural numbers, through the gap: ");
		in = scanf_s("%d%d", a, b);

		if (in != 2) {
		printf("\n Error input. Press any key to exit: ");
			_getch();
			exit(1);
		}

		if ( (a != b)  (b != 0) )
			break;
		if (b == 0)
			a = b;

	} while ( (a == b) );

// Вывод результата на консоль 
	printf("\n a = %d, b = %d, GCD = %d; \n", a, b, gcd(a,b));
	
	printf("\n\n Press any key: ");
	_getch();
	return 0;
}

// Определение рекурсивной функции
int gcd(int a, int b) {
	if ( (a % b) == 0) 
		return b;
	else 
		return gcd(b, a % b);
}

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

    Возможный результат выполнения программы приведен на рис 18.1.

    (рис 18.1) Наибольший общий делитель для чисел 123 и 45

    Задание 1

  • В программе оператор if используйте для рекурсивных вызовов, а оператор else используйте как условие останова.
  • B программу включите определение количества рекурсивных вызовов.
  • Видоизмените программу для случая ошибочного ввода чисел, сделайте, чтобы было повторное приглашение на ввод чисел.
  • Напишите функцию вычисления наибольшего общего делителя на основе итерации (с использованием операторов цикла).
    •

    Пример 2. Напишите рекурсивную функцию, которая выводит на консоль двоичный эквивалент целого десятичного числа, введенного пользователем с клавиатуры.

    Для решения примера отметим, что в двоичной системе счисления числа представлены в виде суммы степеней 2. Подобно тому, как в десятичной системе счисления число 234 означает $$2\times10^2 + 3\times10^1 + 4\times10^0$$, число 101 в двоичной системе означает $$1\times2^2 + 0\times2^1 + 1\times2^0$$ [7]. В двоичных числах используются только цифры 0 и 1.

    Очевидно, что за основу решения примера следует использовать целочисленное деление. Если введено число n, то оно может быть, либо четным, либо нечетным. Тогда остаток от деления на 2 будет равняться нулю для четных чисел и единице – для нечетных.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <locale.h>

// Прототип рекурсивной функции
void dec2bin(unsigned long int);

int main (void) {
	unsigned long int n;

	setlocale(LC_ALL, "Russian"); // для русских шрифтов

	printf("\n\t Введите целое десятичное число\n \
 (или не числовой символ для завершения программы): ");
	while (scanf_s("%ul", n) == 1)
	{
		printf("\n Двоичный эквивалент: ");
		dec2bin(n);

	printf("\n\n\t Введите целое десятичное число\n \
 (или не числовой символ для завершения программы): ");

	}

	return 0; // выход из программы
}

// Определение рекурсивной функции
void dec2bin(unsigned long int n) {
	int r;
	r = n % 2;

	if (n >= 2 ) 
		dec2bin(n/2);

	printf("%d", r);
	
	return;
}

    В программе шаги рекурсии осуществляются при условии, что аргумент рекурсивной функции больше или равен двум. Как только это условие нарушается, происходит распечатка результата и выход из функции. Например, при n = 10 остаток от целочисленного деления r = 10%2 = 0. В то же время аргумент функции dec2bin() будет равняться 5. Тогда остаток от целочисленного деления r = 5%2 = 1. Далее аргумент функции будет равняться 2 (5/2), так как аргумент функции определен через целое число. Остаток от целочисленного деления r = 2%2 = 0. Теперь аргумент рекурсивной функции будет равен 1, что прерывает рекурсивные вызовы функции (нарушается условие проверки оператором if ). Остаток от деления r = 1%2 = 1. Вывод результата на консоль будет осуществляться из стека по дисциплине LIFO (Last Input First Output – последним вошел, первым вышел).

    Пример выполнения программы показан на рис 18.2.

    (рис 18.2) Преобразование десятичных чисел в двоичные эквиваленты

    Задание 2

  • Какой тип рекурсии используется в приведенной программе?
  • В программу включите защиту от ввода отрицательных целых чисел.
  • Вывод результатов преобразования десятичных чисел в двоичные эквиваленты осуществите в текстовый файл с именем compX.txt, где Х – номер компьютера (1, 2, ...), на котором выполняется лабораторная работа. В текстовый файл занести также и преобразуемое десятичное число.
  • В программе вместо функции printf(), как функции вывода результата, примените функцию putchar().
  • В программу внесите изменения для подсчета количества рекурсивных вызовов.
  • Напишите программу преобразования десятичного числа в свой двоичный эквивалент на основе не рекурсивного подхода, а с помощью операций с разрядами.
  • Напишите программу с рекурсивной функцией вывода на консоль десятичного числа для введенного пользователем его двоичного эквивалента.
    •

    Пример 3. С использованием косвенной рекурсии напишите программу по решению следующей задачи. Строка состоит из клеток, пронумерованных от 1 до n. Состояние клетки можно изменить – если она пуста, поставить в нее шащку (занять ее), иначе убрать из нее шашку (освободить ее). Вначале строка пуста. Нужно занять все клетки, соблюдая следующее правило. Изменение клетки допустимо, если она имеет номер 1 или расположена непосредственно после занятой клетки, имеющей минимальный номер среди занятых клеток.

    Вход. Целое n, $$1\leqslant n \leqslant15$$.

    Выход. Последовательность элементов вида +i или –i, обозначающих соответственно занять клетку i и освободить клетку i [9].

    Например, при n = 3 выход имеет вид +1+2–1+3+1.

    В основу решения задачи положен программный код из [9].

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>   // для getch();
#include <stdlib.h> // для exit();

// Прототипы функций
void fillOnly(int);
void free_n(int);
void fill_n(int);

int main (void)
 {
	int n = 1; // размер строки
	int in = 1; // контроль ввода n

	printf("\n Enter a length of string (naturel number): ");
	in = scanf_s("%i", n);

	if (in != 1 || n < 1 || n > 15)
     {
		printf("\n Error input. Press any key to exit: ");
		_getch();
		exit(0);
	}
	puts("\n\tResult:");

	fill_n(n);

	printf("\n\n Press any key to exit: ");
	_getch();
	return 0;
}
   // Объявления функций
   // 1-я функция
void fillOnly(int n) {
	if (n == 1)
		printf("\t%+3d\n", 1);
	else {
		fillOnly(n-1);
		printf("\t%+3d\n", n);
		free_n(n-1);
	}
}

// 2-я функция
void free_n(int n)
 {
	if (n == 1)
		printf("\t%+3d\n", -1);

	else {
		fillOnly(n-1);
		printf("\t%+3d\n", -n);
		free_n(n-1);
	}
}

//3-я функция
void fill_n(int n)
 {
	if (n == 1)
		printf("\t%+3d\n", 1);
	else {
		if (n == 2)
			printf("\t%+3d\n\t%+3d\n", 1, 2);
		else {
			fillOnly(n-1);
			printf("\t%+3d\n", n);
			fill_n(n-2);
		}
	}
}

    В программе вывод результата на консоль выполнен в виде столбца. Для этого используется эскейп-последовательность \t в функциях printf(). Форматный вывод значений в функциях printf() выполнен с помощью спецификации %+3d, что позволяет автоматически устанавливать знаки чисел, под которые отводятся 3 позиции.

    Как видно из приведенного программного кода, в каждой из функций имеется вызов самой функции и других функций. Это указывает на косвенное обращение к функциям.

    Пример выполнения программы показан на рис 18.3.

    (рис 18.3) Пример заполнения и освобождения клеток

    Задание 3

  • В программе укажите рекурсивные функции. Объясните работу рекурсивных функций.
  • Проверьте работу программы при смене порядка объявлений функций.
  • Проверьте работу программы без использования прототипов функций.
  • Для случая, когда $$n \leqslant 5$$, предусмотрите вывод результата в строку, а не в столбец.
  • В программу добавьте программный код для подсчета рекурсивных вызовов, каждой из рекурсивных функций.
  • остройте зависимость числа комбинаций заполнения и освобождения клеток от введенного числа n.
    •

    Пример 4. "Ханойская башня". Напишите программу по решению следующей задачи. Имеется пирамида из n колец, лежащих на основании А (на стержне, на столбе) одно на другом в порядке убывания размеров. Кольца должны быть перемещены на основание В в том же порядке, в котором они были на основании А, при использовании "промежуточного" основания С. Единственными разрешенными перемещениями являются такие, при которых кольцо, взятое с вершины одной из пирамид, помещается на большее кольцо, либо на пустое основание. Осуществить выдачу на печать (на консоль, в текстовый файл) последовательности перемещений колец.

    "Ханойская башня" – известная задача. Алгоритм решения этой задачи достаточно подробно описан в [18.10].

    Решение задачи "Ханойская башня"

    Для рекурсивного решения этой задачи следует пройти три этапа.

    1-й этап – параметризация. В этой задаче естественным параметром является n – число колец. В число параметров можно включить также и три основания: А (исходное), В (конечное), С (промежуточное).

    2-й этап – поиск тривиальных случаев. Здесь тривиальным случаем будет такой, при котором n = 0; в этом случае просто нечего делать.

    3-й этап – редукция общего случая к более простому. Здесь надо отметить, что n колец могут быть перемещены с А на В следующим путем:

  • переноса (рекурсивно) n – 1 колец с вершины А (исходное основание) на С ("промежуточное" основание) с учетом правил: основание В (конечная цель) используется как промежуточное основание;
  • перемещения на В кольца (наибольшего диаметра), оставшегося на А;
  • переноса (рекурсивно) n – 1 других колец с С на В при соблюдении правил с А в качестве промежуточного основания.
    •

    Алгоритм решения задачи запишем в следующем виде:

    hanoi(n–1, A, C, B);
переместить (A, B);
hanoi(n–1, C, B, A);

    где hanoi() – имя рекурсивной функции [18.10].

    Пример промежуточного положения Ханойской башни при n = 4 показан на рис 18.4.

    (рис 18.4) Промежуточное положение Ханойской башни при n = 4

    Число элементарных перемещений равно 2n – 1, где n – количество исходных дисков [18.10]. С увеличением n число перемещений быстро нарастает.

    На рис 18.5 показана зависимость элементарных перемещений от числа дисков.

    (рис 18.5) Зависимость элементарных перемещений от числа дисков

    С учетом того, что перемещение диска – это есть рекурсивный вызов функции, то на каждый вызов требуется определенное время. Практически с любым конечным малым временем обработки рекурсивного вызова общее время работы рекурсивной функции для большого количества дисков n становится не выполнимым на существующих современных компьютерах. В соответствии с легендой конец света наступит при перемещении 64 дисков [18.10].

    В связи со степенным ростом числа рекурсивных вызовов в программе ограничимся величиной n = 15.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <math.h>

// Пртотип рекурсивной функции
void hanoi(int n,char a, char b, char c);

int main(void) 
{
     char a = 'A'; // исходное основание
     char b = 'B'; // конечное основание
     char c = 'C'; // промежуточное основание

	double n; // число дисков
	char str[81] = "15"; // инициализация строки

puts("\n Hanoi Tower; A - starting; B - end; C - intermediate");

	while (0.01) {       // 0.01 - как истинное значение
 		printf("\n Enter the number of disks: ");
		scanf_s(" %s",str, 80);
		n = atof(str);
		
		if ( n <= 0 || ceil(n) != n) {
			printf("\n Error input. Press any key: ");
			_getch();
			continue;
		}

		else if (n > 15.0) {
			printf("\n Very large number. Press any key: ");
			_getch();
			continue;
		}
		
         else
			break;
	}
	
     puts("\n Elementary transferences:");
	hanoi((int)n, a, b, c);

  
  printf("\n\n Press any key: ");
  _getch();
  return 0;
}

// Определение рекурсивной функции
void hanoi(int num, char a, char b, char c)
{
  if(num > 0) {

    hanoi(num-1,a,c,b);

    printf("\t%c --> %c\n",a,b);

    hanoi(num-1,c,b,a);

  }
  
}

    Результат выполнения программы при n = 5 показан на рис 18.6.

    (рис 18.6) Перемещения дисков в Ханойской башне при n = 5

    Задание 4

  • Определите тип рекурсии, используемой в программе.
  • Для случая, когда не все элементарные перемещения выводятся на экран дисплея, предусмотрите вывод результата программы в текстовый файл с именем compX.txt, где X – номер компьютера, на котором выполняется лабораторная работа.
  • Программным путем выполните подсчет общего количества обращений к рекурсивной функции. Сделайте также вывод порядкового номера перемещения на экран дисплея. Порядковый номер расположите слева от элементарного перемещения. Построить (в MS Excel или в MATLAB) зависимость количества обращений к рекурсивной функции от заданного числа дисков.
  • Измените аргументы рекурсивной функции: включить переменные типа int для определения имени (нумерации) основания.
  • Измените условие задачи "Ханойская башня". Сначала исходным основанием считать В, конечным С, промежуточным А. Затем принять за исходное основание С, промежуточным В, конечным А.
    •

    Пример 5. "Задача о рюкзаке". Есть 10 предметов, о которых известны их веса и стоимости. Требуется поместить в рюкзак предметы таким образом, чтобы они не превысили допустимый вес для рюкзака при максимальной стоимости выбранных предметов. Исходные параметры модели – характеристики предметов взяты из [11] и приведены в табл. 18.1.

    Характеристики предметов
    № п/п 1 2 3 4 5 6 7 8 9 10
    Вес 10 11 12 13 14 15 16 17 18 19
    Стоимость 18 20 17 19 25 21 27 23 25 24

    Данная задача широко известна [18.9-18.10-18.11], она еще называется задачей о ранце, или вариант с английского – "knapsack problem". Предполагается, что один и тот же предмет не может быть взят несколько раз.

    Для решения поставленной задачи используем рекурсивный алгоритм, описанный в [18.11], где также приводится фрагмент программы на языке программирования MODULA – 2.

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <locale.h>

const int limW = 20; // предельный вес выбранных предметов
enum {N = 10}; // количество предметов

typedef struct {
	int weight; //// вес или размер предметов
	int value; //// стоимость или ценность предметов
} object;

// Формирование структурного типа с параметрами модели
object obj[] = {10,18, 11,20, 12,17, 13,19, 14,25, 15,21, 16,27, 17,23, 18,25, 19,24};

int maxv; // для инициализации стоимости предметов

// Рекурсивная функция
int TRY (int i, int tw, int av) {
	// Попытка включения предмета
	if (tw + obj[i].weight <= limW) 
		if (i < N-1) 
			TRY(i+1, tw + obj[i].weight, av );
		   
          else if (av > maxv) 
			maxv = av;
		// Попытка исключения предмета
	if (av > maxv + obj[i].value) 
		if (i < N-1) 
			TRY(i+1, tw, av - obj[i].value);
		else 
			maxv = av - obj[i].value;
	return maxv;	
}

// Главная функция программы
int main (void) {
	int i, price;
	int sumw = 0;
	int sumv = 0;
	setlocale(LC_ALL, "rus");

	maxv = obj[0].value; // инициализации стоимости предметов
	puts("\n\t\t\tЗАДАЧА О РЮКЗАКЕ");
	puts("\t\t  Характеристика предметов");
	for (i = 0; i < (4*N + 12); i++)
		printf("%s", "_");

	printf("\n\n %12s", "Вес:");
	for (i = 0; i < N; i++) {
		sumw += obj[i].weight;
		printf(" %3d", obj[i].weight); }

	printf("\n %12s", "Стоимость:");
	for (i = 0; i < N; i++) {
		sumv += obj[i].value;
		printf(" %3d", obj[i].value); }
	printf("\n ");
	for (i = 0; i < (4*N + 12); i++)
		printf("%s", "_");

printf("\n\n %32s: %d\n", "Общий вес всех предметов", sumw);
printf(" %32s: %d\n", "Общая стоимость всех предметов", sumv);
	printf(" %32s: %d\n ", "Допустимый вес рюкзака", limW);
	     for (i = 0; i < (4*N + 12); i++)
      printf("%s", "_");
	// Вызов рекурсивной функции с начальными параметрами
	price = TRY(0,0,sumv);
printf("\n\n  Стоимость выбранных предметов: %d\n ", price );
	for (i = 0; i < (4*N + 12); i++)
		printf("%s", "_");

	printf("\n\n ... Нажмите любую клавишу: ");
	_getch();
	return 0;
}

    Пример выполнения программы показан на рис 18.7.

    (рис 18.7) Пример выполнения программы решения задачи о рюкзаке

    Представленная программа основана на следующем алгоритме [18.11]. В рекурсивной функции TRY() определены две ситуации для выбора предмета в рюкзак. Если речь идет о включении то объект (предмет со своим весом и стоимостью) можно включить в выборку для укладки в рюкзак, если он подходит по весовым ограничениям. Если он не подходит, то попытки добавить еще один объект в текущую выборку можно прекратить. Когда же речь идет об исключении, то критерием приемлемости, т. е. возможности продолжения построения текущей выборки, будет то, что после данного исключения общая ценность (стоимость) будет не меньше полученного до этого момента оптимума. В данной программе реализована схема с возвратами, использующая некоторые ограничения для уменьшения роста потенциального дерева поиска, называется алгоритмом ветвей и границ [18.11].

    Задание 5

  • Подсчитайте количество рекурсивных вызовов функции TRY() в зависимости от величины допустимого веса рюкзака, начиная от 10 до 120 с шагом в 10 условных единиц. Постройте график полученной зависимости (в MS EXCEL или в MATLAB).
  • Рекурсивную функцию TRY() расположите в отдельном файле с именем compX.c, где Х – номер компьютера, на котором выполняется лабораторная работа.
  • Сформирйте массив данных о предметах по случайному равномерному закону из интервала [10; 20*Х], где Х – номер компьютера, на котором выполняется лабораторная работа. Размер массива выберите случайно из следующего интервала натуральных чисел: [10; 18].
  • В программу внесите изменения, которые бы позволили определить номера предметов, отобранные в рюкзак. Соответственно укажите вес и стоимость каждого предмета.
    •

    Пример 6. Напишите программу сортировки одномерного массива целых чисел на основе рекурсивного алгоритма быстрой сортировки Хоара.

    Суть алгоритма быстрой сортировки заключается в следующем. Выбираем наугад какой-либо элемент х исходного массива. Будем просматривать слева наш массив до тех пор, пока не встретим элемент ai > x, затем будем просматривать массив справа, пока не встретим $$a_i \leqslant х$$. Поменяем местами эти два элемента и продолжим процесс просмотра и обмена до тех пор, пока оба просмотра не встретятся. В результате исходный массив окажется разбитым на две части, левая часть будет содержать элементы меньше или равные х, а правая часть – элементы больше х. Применив эту процедуру разделения к левой и правой частям массива от точки встречи, получим четыре части и т. д., пока в каждой части окажется только один элемент [18.12]. В качестве граничного элемента х для разделения обычно выбирают средний элемент массива.

    Программный код решения примера:

    /* Быстрая сортировка Хоара.
* Рекурсивный вариант.
*/

#include <stdio.h>
#include <conio.h>

// Массив, подлежащий сортировке по возрастанию
int A[] = {1, 5, 7, -5, 0, 12, 8, 5, 4, -10, 3, 6, 18};

// Прототип рекурсивной функции
void Quick_Sort(int A[], int L, int R);

int main (void) {
	int i;
	int N;

	N = sizeof(A)/sizeof(A[0]);

	puts("\n\t\t QUICK SORT");
	printf("\n\t The original array of size %d:\n ", N);
	for (i = 0; i < N; i++)
		printf(" %3d ", A[i]);
     
// Вызов рекурсивной функции сортировки
	Quick_Sort(A, 0, N-1);

	printf("\n\n\t The sorting array:\n ");
	for (i = 0; i < N; i++)
		printf(" %3d ", A[i]);

	printf("\n\n ... Press any key: ");
	_getch();
	return 0;
}
// Определение рекурсивной функции
void Quick_Sort(int A[], int L, int R) {
	int i, j, k;
	int x; // граничный элемент для разделения массива
	i = L;
	j = R;
	x = A[(int)(L + R)/2];
	do { while (A[i] < x)
		i++;
	while (x < A[j])
		j--;
	if (i <= j) {
		k = A[i]; A[i] = A[j]; A[j] = k;
		i++; j--;
	}
	} while (i < j);

	if (L < j)
		Quick_Sort(A, L, j);

	if (i < R)
		Quick_Sort(A, i, R); 
}

    Пример выполнения программы показан на рис 18.8.

    (рис 18.8) Пример быстрой сортировки одномерного массива

    Задание 6

  • В программу внесите изменения для сортировки вещественных данных.
  • В программу внесите изменения для сортировки массива по убыванию.
  • Рекурсивную функцию программы разместите во внешнем файле с именем compX.c, где Х – номер компьютера, на котором выполняется лабораторная работа.
  • 4Размерность массива, подлежащего сортировке, и данные массива задайте случайно из интервалов [10; 100] и [10Х; 50Х], где Х – номер компьютера, на котором выполняется лабораторная работа.
  • Подсчитайте количество рекурсивных вызовов при сортировке массивов, задаваемых случайным образом.
    •

    Пример 7. Напишите программу сортировки одномерного массива целых чисел на основе рекурсивного алгоритма слиянием.

    При алгоритме слиянием сортировку производят по частям, а затем соединяют отдельные части в единое целое [18.5].

    Выберем следующую схему разбиения данных. Будем разрезать массив данных на две равные части, образуя два подмассива. Затем сортировка слиянием рекурсивно вызывает себя для каждого из двух подмассивов. Конечным шагом является слияние двух сортированных подмассивов в один сортированный массив [18.13].

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

    Алгоритм сортировки слиянием может быть использован при сортировке внешних данных, например данных, записанных в отдельные файлы [18.5].

    Программный код решения примера:

    #include <stdio.h>
#include <conio.h>
#include <stdlib.h>

// Заданный произвольный числовой массив
int A[] = {9, 3, 4, 5, 8, 1, 0, 3, 2, -3, 12, 10, -7, 8};

// Основная функция сортировки, merge - сливать, соединять
void merge (int arr[],int *temp,int start,int mid,int end)
 {
	int i = 0; // для временного массива
	int i_lower = start;
	int i_upper = mid + 1;
	int i_arr = start;

	// Пока ни один из подмассивов не пуст
	while ( (i_lower <= mid)  (i_upper <= end) ) {
		if (arr[i_lower] < arr[i_upper])
			temp[i++] = arr[i_lower++];
		else
			temp[i++] = arr[i_upper++];
	} // end while

	// Случай, когда в одном из подмассивов остались элементы
	   if (i_lower <= mid) {
		// assert (i_upper > end);
		for ( ; i_lower <= mid; temp[i++] = arr[i_lower++]);
	}
	   else 
	for ( ; i_upper <= end; temp[i++] = arr[i_upper++]) ;
	// Когда размер массива равен end - start + 1
		if (i == end - start + 1)
	for ( i = 0; i_arr <= end;  arr[i_arr++] = temp[i++]) ;
} // end merge

// Рекурсивная сортировка подмассивов
void sub (int arr[], int *temp, int head, int tail ) {
	// head - голова
	// tail - хвост
	int mid;
	if (head >= tail)
		return;
	if (tail > head) {
		// Средняя точка массива
		mid = (head + tail) / 2;
		// assert ( (mid >= head)  (mid <= tail) );
		if (mid >= head  mid <= tail) {
			// Сортировка подмассивов
			sub (arr, temp, head, mid);
			sub (arr, temp, mid+1, tail);
			// Объединение результатов
			merge (arr, temp, head, mid, tail);
		}
	}
} // end sub

// Функция как интерфейс, для удобства вызова программы
void merge_sort (int arr[], int size)  {
	int head = 0;
	int tail = size - 1;
	int *temp;
	temp = (int *) malloc (size*sizeof(int)); 
	sub (arr, temp, head, tail);
	free(temp);
} 

int main (void) {
	int i;
	int N;

	N = sizeof(A)/sizeof(A[0]);
	// Вывод на консоль исходного массива
	printf("\n\t The original array of size %d:\n ", N);
	for (i = 0; i < N; i++)
		printf(" %2d", A[i]);

	// Вызов функции для сортировки массива
	merge_sort (A, N);
	// Вывод на консоль отсортированного массива
	printf("\n\n\t After sorting:\n ");
	for (i = 0; i < N; i++)
		printf(" %2d", A[i]);

	printf("\n\n ... Press any key: ");
	_getch();
	return 0;
}

    Пример выполнения программы показан на рис 18.9.

    (рис 18.9) Пример сортировки слиянием одномерного массива

    В алгоритме сортировки слиянием можно выделить три этапа.

  • Сортируемый массив разбивается на две половины примерно одинакового размера.
  • Каждая из получившихся половин сортируется отдельно (каким-либо известным алгоритмом, в том числе и с помощью алгоритма слиянием ).
  • Два упорядоченных массива половинного размера соединяются в один. Рекурсивное разбиение заданного массива происходит до тех пор, пока размер массива не достигнет единицы. Далее решается задача – нетривиальная задача – соединение двух упорядоченных массивов в один.
    •

    Алгоритм сортировки слиянием был изобретен Джоном фон Нейманом в 1945 г.

    Сортировка слиянием считается предпочтительной в случае, когда требуется застраховаться от наихудшего случая, возможного при использовании быстрой сортировки [18.12].

    Задание 7

  • Все вспомогательные функции программы разместите во внешние файлы с именами compX_1.c, compX_2.c и т. д., где Х – номер компьютера, на котором выполняется лабораторная работа (1, 2, ...). Протестируйте программу на контрольном примере. Подсчитайте количество рекурсивных вызовов.
  • Подготовьте два не отсортированных массива и произведите их слияние в один отсортированный массив. Данные массивов задаются случайно по равномерному закону из интервалов [–5Х; 5Х] и [0; 10Х], где Х – номер компьютера, на котором выполняется лабораторная работа (1, 2,...). Размерности массивов должны задаваться с клавиатуры из интервала [10; 20].
  • Напишите программу по сортировке слиянием двух массивов, расположенных в текстовых файлах (внешняя сортировка слиянием). Результат сортировки разместите также в текстовый файл с именем compX.txt, где Х – номер компьютера, на котором выполняется лабораторная работа.
    •

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

  • Когда следует применять рекурсивные алгоритмы?
  • Какие известны методы и приемы устранения "хвостовой" рекурсии?
  • Какие проблемы могут возникать при реализации рекурсивных алгоритмов на электронных вычислительных машинах?
  • В чем отличие глубины рекурсии от рекурсивного вызова?
  • Какие задачи в программировании можно назвать, где применение рекурсии оправдано?
    •
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^