Подпрограммы (функции)

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

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

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

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

Подпрограммы могут быть двух видов: подпрограмма без параметров и подпрограмма с параметрами. Обращение к подпрограмме может быть организовано из любого места основной программы или другой подпрограммы сколько угодно раз.

При работе с подпрограммами важными являются понятия формальных и фактических параметров. Формальные параметры — это идентификаторы входных данных для подпрограммы. Если формальные параметры получают конкретные значения, то они называются фактическими. Формальные параметры могут получить конкретные значения только в той программе, где производится обращение к данному модулю-подпрограмме. Тип и порядок записи фактических параметров должны быть такими же, как и формальных параметров. В противном случае результат работы программы будет непредсказуемым. Из этого следует, что фактические параметры используются при обращении к подпрограмме из основной, а формальные параметры — только в самом модуле.

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

При составлении подпрограмм с параметрами надо соблюдать следующие правила:

1) каждая подпрограмма имеет свое имя и список формальных параметров;

2) процедура из основной программы вызывается командой вызова, которая по форме ничем не отличается от вызова команды исполнителя. Результат присваивается одной или нескольким переменным, которые находятся в списке формальных параметров. Но результатом могут быть, конечно, не только значения переменных, но какое либо действие, выполненное ЭВМ.

Пример 1. Используем алгоритм нахождения наибольшего общего делителя двух натуральных чисел в качестве вспомогательного при решении задачи: составить программу вычитания дробей (a, b, c, d — натуральные числа). Результат представить в виде обыкновенной несократимой дроби.

Подпрограмма.

1. Ввести натуральные числа M, N.
2. Если M=N, перейти к п. 5, иначе к следующему пункту.
3. Если M>N, то M:=M-N, иначе N:=N-M.
4. Перейти к п. 2.
5. Передать значение M в основную программу.
6. Конец подпрограммы.

Основная программа.

1. Ввести значения A, B, C, D.
2. E:=A*D - B*C.
3. F:= B*D.
4. Если E=0, вывести значение E и перейти к п. 9, иначе перейти к следующему пункту.
5. M:=|E|, N:=F, перейти к подпрограмме вычисления НОД.
6. G := M.
7. E и F нацело разделить на G.
8. Вывести значения E и F на печать.
9. Конец программы.

 	
 	// программа НОД

 	#include <iostream.h>
 	#include <math.h>
 	
 	void Nod(int m, int n, int &k);
 	 	
 	void main()
 	{
 		int a, b, c, d, g, e, f;
 		cout << "Введите числители и знаменатели дробей:";
 		cin >> a >> b >> c >> d;
 		e = a * d - b * c;
 		f = b * d;
 		if (e==0) 
 			cout << "Ответ: " << e;
 		else
 		{
 			Nod(fabs(e),f,g);
 			e = e / g;
 			f = f / g;
 			cout << "Ответ: " << e << "/" << f;
 		}
 	}

 	void Nod(int m, int n, int &k)
 	{
 		while (m != n) 
 			if (m > n) m -= n; else n -= m;
 		k = m; 		 				
 	}

Как видно из примера, объявление подпрограммы-функции находится в разделе описаний прототипов функций, а реализация после основной функции main. В заголовке подпрограммы содержится список формальных параметров с указанием их типа, которые условно можно разделить на входные и выходные (перед ними стоит &). Вообще при обращении к функции со списком параметров без &, внутри функции используются копии параметров, которые после выполнения удаляются. Знак & указывает компилятору что необходимо использовать саму переменную, а не ее копию. При обращении к функции указывается ее имя и список фактических параметров. Формальные и фактические параметры должны соответствовать по количеству и по типу.

Описание функции в С++ осуществляется следующим образом:

  тип_возвращаемого_значения <Имя функции>(<список фактических параметров>);

Например,

		void Nod(int e, int f, int &k);
		
		int f1(float a);
		
		long f2();

Функция всегда возвращает единственное значение. Как видно из примера 1, мы использовали тип void в качестве возращаемого типа. Т.е. указали компилятору, что наша функция не возвращает никакого значения.

Покажем, как изменится подпрограмма из примера, если ее записать в виде функции, возвращающей само значение НОД (без использования возвращаемой переменной).

int Nod(int m, int n)
{
    while (m!=n)
    	if (m > n) m -=n; else n -= m;
    return (n);
}

Итак, в теле функции хотя бы один раз встречается команда return, которая указывает, какое значение вернуть в качестве значения функции.

Вызов функции в основной будет следующим:

		g = Nod(fabs(e), f);

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

При решении задач целесообразно проанализировать условие, записать решение в крупных блоках (не являющихся операторами C++), детализировать каждый из блоков (записав в виде блоков, возможно, по-прежнему не операторов C++), и т.д., продолжать до тех пор, пока каждый из блоков не будет реализован с помощью операторов языка.

Пример 2. Дано натуральное число n. Переставить местами первую и последнюю цифры этого числа.

 	void main()
 	{
 		int n;
 		cout << "Введите натуральное число: ";
 		cin >> n;
 		if (Impossible(n))
 			cout << "Невозможно переставить цифры, возникнет переполнение!";
 		else
 		{
 			Change(n);
 			cout << "Ответ: " << n;
 		}
 	}

Можно заметить, что необходимо детализировать логическую функцию Impossible, которая диагностирует, возможна ли перестановка, и функцию Change, которая эту перестановку (в случае, если она возможна) выполняет.

	int Impossible(int n)
	{
		if(Number(n)<5)
			return (0);
		else return ((n % 10 >= 3)&&((((n % 10000)/10)*10 + n / 10000)> 32768 % 10000));
	}

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

int Number(int n)
{
	int vsp = 0;
	while (n > 0)
	{
		vsp++;
		n = n / 10;		
	}
	return (vsp);
}

Наконец, последняя функция.

void Change(int &n)
{
	int kol = Number(n);
	int p = n % 10;
	if(kol>1)
		s = n / pow(10, kol - 1);
	else
		s = 0;
	int r = (n % pow(10, kol - 1)) /10;
	n = p * pow(10, kol - 1) + r*10 + s;	
}

Возможны также подпрограммы, которые вызывают сами себя. Они называются рекурсивными. Создание таких подпрограмм является красивым приемом программирования, но не всегда целесообразно из-за чрезмерного расхода памяти ЭВМ.

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

// программа максимальная цифра
#include <iostream.h>

int Maximum(long n);

void main()
{
	long A;
	cout << "Введите натуральное число: ";
	cin >> A;
	cout << "Максимальная цифра равна " << Maximum(A);
}

int Maximum(long n);
{
	if (n < 10)
		return(n);
	else
		if ((n % 10) > Maximum (n / 10))
			return (n % 10);
		else
			return (Maximum(n / 10))
}

При создании функции Maximum было использовано следующее соображение: если число состоит из одной цифры, то она является максимальной, иначе если последняя цифра не является максимальной, то ее следует искать среди других цифр числа. При написании рекурсивного алгоритма следует позаботиться о граничном условии, когда цепочка рекурсивных вызовов обрывается и начинается ее обратное «раскручивание». В нашем примере это условие N < 10.

Более подробно о рекурсии говорится в следующей статье.

1. Какие алгоритмы называют вспомогательными?
2. Какое количество вспомогательных алгоритмов может присутствовать в основном алгоритме?
3. Можно ли вспомогательные алгоритмы, написанные для решения данной задачи, использовать при решении других задач, где их применение было бы целесообразно?
4. Какие параметры называют формальными? фактическими?
5. Какое соответствие должно соблюдаться между формальными и фактическими параметрами?
6. Может ли фактических параметров процедуры (функции) быть больше, чем формальных? А меньше?
7. Существуют ли подпрограммы без параметров?
8. Существуют ли ограничения на число параметров подпрограмм? Если нет, то чем же всё-таки ограничивается это количество в С++?
9. В каком разделе объявляются и в каком реализуются подпрограммы в С++?
10. Какого типа может быть значение функции?
11. Расскажите о методе последовательной детализации при разработке программ.
12. Какие подпрограммы называют рекурсивными?
13. Что такое граничное условие при организации рекурсивной подпрограммы?