ФУНКЦИИ. ПРОДОЛЖЕНИЕФУНКЦИИ. ПРОДОЛЖЕНИЕ
5.1 Рекурсия
Функция называется рекурсивной, если для вычисления ее значения в заданной точке можно использовать одно или несколько ее значений, вычисленных в других точках. Примером такой функции является факториал, который определяется как функция, заданная на множестве целых неотрицательных чисел при помощи равенства
Из определения факториала следует очевидное равенство
выражающее его значение в точке Другим примером является функция, определенная на множестве натуральных чисел при помощи равенства
Ее значения называются числами Фибоначи.
Пример 5.1 - Применение рекурсии для вычисления факториала
int FactRec (int n){ if (! n) return 1; else return n*Fact (n -1); }
Пример 5.2 - Применение рекурсии для вычисления чисел Фибоначи
int FiRec (int n){ switch (n){ case 1: case 2: return 1; default: return FiRec (n -1)+ FiRec (n -2); } }
Пример 5.3 – Вычисление определителя
# include < stdio.h > double Determinant (double* pA, int Dim){ if (Dim ==1) return pA [0]; int i,j,k; int sgn =1; double det =0; // Память для элементов минора порядка Dim -1 double* pM=new double [(Dim- 1)*(Dim -1)]; // Разложение определителя по строке с номером нуль // j - номер столбца for (j =0; j<Dim; j ++){ // Вычисление элементов минора элемента (0, j) // Выбор строки for (i =0; i <(Dim -1); i ++){ // Выбор столбца for (k =0; k <(Dim -1); k ++) // Копирование if (k < j) pM [ i *(Dim -1)+ k ]= pA [(i +1)* Dim + k ]; else pM [ i *(Dim -1)+ k ]= pA [(i +1)* Dim + k +1]; } // Вычисление алгебраического дополнения det += pA [ j ]* sgn * Determinant (pM, Dim -1); sgn *=-1; } delete [] pM; return det; } void main (){ int Dim =4; double A []={2,0,3,0, 3,3,0,5, 1,2,1,2, 1,3,2,1}; double d=Determinant (A, Dim); printf (" d =% f \n ", d); }
После прогона приложения на дисплее появится значение определителя d=-20.000000
Пример 5.4 – Сортировка выбором минимального элемента
#include<stdio.h> // Выбор номера минимального элемента int IndexMinItem(int* A,int n){ int Index; if(n==1) return 0; if(n>1){ Index=IndexMinItem(A,n-1); if(A[Index]>A[n-1]) Index=n-1; } return Index; } // Обмен значениями void Change(int* a,int* b){ int t=*a; *a=*b; *b=t; } // Сортировка выбором минимального элемента // с применением рекурсии void SortMinRec(int* pA,int Dim){ if(Dim==1) return; int Num=IndexMinItem(pA,Dim); Change(pA,pA+Num); SortMinRec(pA+1,Dim-1); }
5.2 Обобщенные функции
При решении различных задач возникает необходимость в использовании функций, которые отличаются друг от друга только типами формальных параметров. В качестве очевидного примера можно назвать задачу сортировки (упорядочивания) однотипных объектов. В первых редакциях языка Си в таких случаях требовалось определять собственную функцию для каждого типа сортируемых объектов. Теперь этого можно уже не делать, благодаря появлению в языке Си нового понятия, которое получило название обобщенной функции. Именно так называется множество функций, которые отличаются друг от друга только типами формальных параметров. Определение обобщенной функции называется шаблоном (template). Главное отличие шаблона от определения обычной функции заключается в том, что он позволяет использовать в качестве параметров не только объекты, но и их типы. В шаблоне они заменяются идентификаторами, которые называются параметрами обобщенной функции. Определение шаблона начинается со служебного слова template. За ним в угловых скобках следует список параметров обобщенной функции, обозначающих типы данных. Каждый элемент списка состоит из служебного слова class и выбранного программистом идентификатора: < class Парам_1,..., class Парам_n >. Далее следует идентификатор Тип, обозначающий тип возвращаемого обобщенной функцией значения. Он может быть одним из параметров, перечисленных в угловых скобках, или идентификатором конкретного типа как встроенного, так и абстрактного. Затем идут ее имя и в круглых скобках, как обычно, список формальных параметров, включающий типы и имена объектов: (Тип_1 Имя_1,..., Тип_m Имя_m). Очевидно, что вместо конкретных типов данных в этом списке могут стоять параметры из угловых скобок. Завершается шаблон телом обобщенной функции, в котором также вместо конкретных типов могут использоваться параметры из угловых скобок. Наглядно шаблон можно представить в виде следующей схемы
template <class Парам_1,..., class Парам_n>; Тип Имя (Тип_1 Имя_1,..., Тип_m Имя_m){ // Тело функции }
Для вызова конкретной функции из всего множества функций, определяемых шаблоном, используется ее имя. По определению, оно состоит из имени обобщенной функции и следующего за ней в угловых скобках набора идентификаторов конкретных типов. Пусть Type_1,...,Type_n – конкретные типы, а Obj_1,...,Obj_m – объекты типов Type_1,...,Type_m соответственно, тогда для вызова функции с именем Имя<Type_1,...,Type_n>; достаточно поместить в текст приложения следующую команду
Имя<Type_1,...,Type_n> (Obj_1,...,Obj_m);
В качестве примера использования обобщенной функции рассмотрим задачу сортировки объектов. Очевидно, что сортировать можно объекты любых типов (как встроенных, так и абстрактных), если для них определены отношение порядка
// Шаблон функции пузырьковой сортировки template <class T> void Sort (T* Array, int iDim) { int i,j; for (i=0; i<iDim-1; i++) for (j=0; j<iDim-i-1; j++) if (Array [ j ] <=Array [ j+1 ]); else { T temp=Array [ j ]; Array [ j ] =Array [ j+1 ]; Array [ j+1 ] =temp; } }
Воспользуемся этим шаблоном для сортировки объектов встроенного типа int.
Пример 5.7 - Cортировка объектов типов int и String #include <stdio.h>; #include <string.h>; template <class T> void Sort (T* Array, int iDim) { int i,j; for (i=0; i<iDim-1; i++) for (j=0; j<iDim-i-1; j++) if (Array [ j ] <=Array [ j+1 ]); else { T temp=Array [ j ]; Array [ j ] =Array [ j+1 ]; Array [ j+1 ] =temp; } } void main (){ int i; // Множество объектов типа int int A [ 4 ] = { 3, 8, 1, 0 }; Sort<int>;(A, 4); // Можно короче // Sort (A, 4); for (i=0; i<4; i++) printf (" %d ", A [ i ]); printf ("\n";); }
После выполнения приложения на экране дисплея должно появиться следующее сообщение: 0 1 3 8 Заметим, что свойство языка Си, известное под именем перегрузки функций, позволяет в вызовах функций сортировки опустить угловые скобки. То есть написать Sort (A, 4)вместо Sort<int>;(A, 4).
5.3 Перегрузка функций
Синтаксические правила первых редакций языка Си требовали, чтобы каждая функция программы имела индивидуальное или, другими словами, уникальное имя. Современные редакции разрешают программисту использовать один и тот же идентификатор для обозначения различных функций, определенных в программе. Такое свойство языка Си называется перегрузкой функций, а сами функции – перегруженными. Перегруженные функции должны определяться программистом таким образом, чтобы информация, содержащаяся в их вызове, позволяла компилятору правильно выбрать нужную из них. Поэтому перегруженные функции отличаются между собой количеством или типами параметров. В самом деле, для вычисления абсолютной величины можно вместо двух вышеуказанных функций с разными именами определить две функции с одним именем. Компилятор сумеет сделать правильный выбор по типу фактического параметра, указанного в вызове функции. Ниже предлагается два примера перегрузки функций. В первом примере решается задача отображения элементов таблицы. Для каждого способа хранения таблицы приведена своя функция. Во втором примере решается задача освобождения памяти, занимаемой таблицей. Пример 5.5 – Отображение таблиц void ShowTable (int* pT, int h, int w){ for (int i=0; i<h; i++){ for (int j=0; j<w; j++) printf ("%10d", pT [ i*w+j ]); printf ("\n";); } }
void ShowTable (int** ppT, int h, int w){ for (int i=0; i<h; i++){ for (int j=0; j<w; j++) printf ("%10d", ppT [ i ][ j ]); printf ("\n";); } }
Пример 5.6 – Освобождение памяти
void FreeTable (int* pT){ delete [] pT; }
void FreeTable (int** ppT, int h){ for (int k=0; k<h; k++) delete [] ppT [ k ]; delete [] ppT; }
5.4 Указатели на функции
Множество всех функций, возвращающих объект типа Type и имеющих формальные параметры типов Type_1,...,Type_n, образует тип, который обозначается конструкцией вида
Type (Type_1,...,Type_n). Например, для обозначения множества всех функций, возвращающих тип int и не имеющих формальных параметров, необходимо использовать конструкцию int (). Конструкция void (int,int) обозначает множество функций, возвращающих тип void и имеющих два параметра типа int. Адрес блока памяти, содержащий команду, с которой начинается выполнение функции, называется ее адресом. Для получения адреса функции используется операция, обозначаемая символом амперсанд &, а ее единственным операндом служит имя функции. Таким образом, если Fun – имя функции, то & Fun – ее адрес. Адреса функций хранятся в переменных, называемых указателями на функции. В соответствии с правилами, для создания указателя с именем pf на Type (Type_1,...,Type_n) в текст необходимо поместить следующую команду
Type (* pf)(Type_1,...,Type_n);
Адрес функции может использоваться для ее вызова или служить фактическим параметром. Перед вызовом функции с помощью ее адреса необходимо, во-первых, создать указатель на вызываемую функцию и, во-вторых, присвоить ему ее адрес. Поэтому для вызова функции Fun () с фактическими параметрами Ob_1,..., Ob_n требуется в общем случае три команды:
// Создание указателя Type (* pf)(Type_1,...,Type_n); // Получение адреса pf =& Func; // Вызов функции (* pf)(Ob_1,...,Ob_n).
Разрешается использовать указатель без его разыменования. В этом случае последняя команда (вызов функции) принимает вид:
pf (Ob_1,...,Ob_n).
Пример 5.4 - Вызов функции с помощью ее указателя
#include <stdio.h>; int Min (int a, int b){ return a <= b? a: b; } void main (){ int a=1, b=2; // Создание указателя на функцию int (* pf)(int, i nt); // Получение адреса pf=&Min; // Вызов функции int Resp =(* pf)(a,b); // Или в краткой форме // Resp=pf (a,b); printf ("Min (%d,%d) =%d\n", a, b, Resp); }
Ранее была рассмотрена функция, обеспечивающая уточнение корня уравнения f (x)=0, отделенного в интервале [ a,b ], методом деления отрезка пополам. В качестве параметров она получала границы интервала и погрешность eps уточнения корня и имела следующий прототип
Dichotomy (double a, double b, double eps);
В соответствии с методом в ходе уточнения корня в теле функции Dichotomy () приходится неоднократно вычислять значения функции f из левой части уравнения. Для того, чтобы функция Dichotomy () была применима к уравнениям с разными левыми частями, программисту приходилось заботиться о том, чтобы они все имели одно и то же имя f. Использование указателей на функции позволяет освободиться от этого неудобного ограничения. В самом деле, все функции из левой части уравнения относятся к типу double (double). Поэтому целесообразно включить в список параметров функции Dichotomy () указатель на тип double (double) и присваивать ему адрес левой части решаемого уравнения f (x)=0.
Пример 5.х – Уточнение корня методом деления отрезка пополам
double Dichotomy (double a, double b, double eps, double (* pf)(double)){ double x,delta; x=(a+b)/2; delta=(b-a)/2; while(delta>eps){ if(pf(a)*pf(x)<=eps) b=x; else a=x; x=(a+b)/2; delta=(b-a)/2; } return x; }
void main(){ double a=2,b=6,e=0.001; double res=Dichotomy(0,6,e,&Fun2); printf("x=%f\n",x); double(*pf[])(double)={&Fun1,&Fun2,&Fun3}; printf("f1=%f f2=%f\n",pf[0](3),pf[1](2)); }
double Fun1(double x){ return x-3; } double Fun2(double x){ return exp(x-2)-x-1;
|
.
, 
,
через значение в точке 
.
, 
, 
.
и бинарная операция, обозначаемая для удобства тем же символом. Для каждой пары объектов 
и 
результат бинарной операции равняется единице, если 
, или нулю в противном случае. Так как алгоритм сортировки не зависит от типа объектов, то для его представления удобно воспользоваться понятием обобщенной функции. Очевидно, что ее единственным параметром будет тип сортируемых объектов. Ниже предлагается шаблон обобщенной функции пузырьковой сортировки по возрастанию в предположении, что сортируемые объекты хранятся в массиве.
