Тема 8 Функції та їх  використання

Лекція 24

Покажчики на функцію

Синтаксис мови С++ дозволяє використовувати покажчик на функцію.

Як відомо, ім’я будь−якої функції являє собою покажчик−константу, що дорівнює адресі початку входження у функцію, тобто адресі її першої машинної команди. Крім констант, можна також описувати покажчики−змінні на функцію у вигляді:

type (*name) (список аргументів);

де type — тип значення, що повертається функцією;*name — ім’я змінної−покажчика на функцію.Покажчики на функцію потрібні в таких випадках:

·         для використання як формальних аргументів у інших функціях;

·         для непрямого виклику інших (резидентних) функцій (програм) початок входу в які записується у відоме місце пам’яті.

Приклад Програмно реалізувати обчислення суми та різниці двох чисел з використанням покажчика на функцію для доступу до інших функцій.

/* використання покажчика на функцію для доступа до інших функцій — difference() і sum() */

#inciude <iostream.h>

#include <conio.h>

int difference (int, int); // прототип функції difference()

int sum(int, int);            // прототип функции sum()

void main ( )

{

int (*fun) (int, int);

int x = 20, у = 5, z;

//присвоєння вказівника fun адреси функції difference()

fun = difference;

z = fun(x, у);               // вызов функции fun()

cout << "z = " << z << endl;

// присвоєння вказівника fun адреси функції sum()

fun = sum;

z = fun(x, y);

cout << "z = " << z << endl;

getch();

}

// функція визначення різниці двох чисел — difference()

int difference(int a, int b)

{ return (a−b); }

// функція визначення суми двох чисел — sum()

int sum(int a, int b)

{ return (a + b); }

Результати обчислень:

z = 15

z = 25

Покажчики на функції, як і звичайні змінні, можна об’єд­нати в масиви. Так, коли функції мають прототипи вигляду:

int god (const void*, const void *);

int chena (const void*, const void *);

int nazv (const void*, const void *);

int avtor (const void*, const void *);

можна описати функцію

int (*fcmp[4]) () {god, chena, nazv, avtor};

У результаті буде створено масив функцій, який матиме звичайний доступ до елементів, тобто:

int і=0;

fcmp [і] (pt1, pt2); — виклик функції god (pt1, pt2)

У цьому випадку, замінивши індекс, можна викликати ін­шу функцію.

Крім повернення результату виконання функцій у вигляді даних за значенням, можливо також здійснити повернення результату за допомогою операцій розіменування<*> чи одержання адреси «&».

Операція розіменування «*» означає, що функція повертає адресу на об’єкт. Функції в такому випадку з’являються як по­кажчики на функцію, тобто у вигляді:

type * fname (список формальних аргументів)

Описані таким способом функції повинні повертати покаж­чик на тип (адресу), наприклад:

char dayweek (int data)

{ static char *weekday[ ] = {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”} ;

return weekday [data % 7]; }

Тут функція dayweek() одержує значення data, тобто число днів, що пройшли з якоїсь визначеної дати, і повертає день тижня у вигляді покажчика на char, оскільки weekday —це масив покажчиків на char.

При оголошенні функції як покажчика на функцію резуль­тат можна передавати шляхом одержання адреси, тобто ви­користовуючи символ “&”. Така функція буде мати структуру:

type *funame (список формальних аргументів){ static type х;   // тіло функції   ……………………   return &x;}

Оскільки значенням покажчика є адреса, то функція може повернути адресу об’єкта того ж типу, що і тип покажчика, який повертається. За необхідності повернення результату функції за посиланням доцільніше використовувати операцію одержання адреси “&” і функцію описувати у вигляді:

type funame (список формальних аргументів)

 

Рекурсивні функції

 

Мова С підтримує можливість звернення функції самої до себе — рекурсію.Розрізняють пряму і непряму рекурсії. Функція називається прямо рекурсивною, якщо містить у своє­му тілі виклик самої себе. Якщо ж функція викликає іншу функцію, що у свою чергу викликає першу, то така функція називається непрямо рекурсивною.Рекурсивні функції найчастіше використовуються для компактної реалізації рекурсивних алгоритмів.

Класичні приклади використання рекурсії — реалізація операції піднесення до степеня і обчислення факторіала числа. Зазначимо, що ці приклади популярні тільки через їхню зруч­ність для пояснення поняття рекурсії, однак вони не дають ви­грашу в програмній реалізації порівняно з ітераційним спосо­бом розв’язання цих задач.

Розглянемо рекурсивну функцію обчислення факторіала. Для того щоб одержати значення факторіала числа n!, необхід­но помножити на n факторіал числа (n−1)!.Ураховуючи, що 0! = 1 та 1! = 1, наведемо приклад цієї функції:

long fact (long n)

{

return (n>l) ? n * fact (n−1) : 1;

}

Рекурсивні функції є зручним засобом породження комбі­наторних об’єктів заданого виду.

Приклад Вивести на екран усі зростаючі послідовності дов­жиною k, елементами яких є натуральні числа від 1 до n. Передбача­ється, що k не перевищує n, інакше таких послідовностей не існує.

Програма буде оперувати з масивом а0… аk−1 і цілою змін­ною t. Припускаючи, що а0… at — зростаюча послідовність на­туральних чисел з відрізку 1…n, рекурсивна функцій generate() друкує всі її зростаючі продовження до довжини k.

/* вивести на екран всі зростаючі послідовності довжиною k, елементами яких являются натуральні числа від 1 до n */

#include <iostream.h>

#include <conio.h>const int m=20;/* максимальна размірність масиву зростаючої послідовності */

int t=1, n, k, a[m];/* k — довжина зростаючої послідовності n — довжина відрізку натуральних чисел, з котрх формуються послідовності*/

/* generate() — рекурсивная функция генерации возрастающих последовательностей */

void generate()

{

int і;

if (t == k)

//одна з послідовностей повністю сформована

{

// вивід послідовності

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

cout << a[i] <<' ';

cout << endl;

}

else

//формування послідовності

{ t++;

for (i = a[t−2] +1; і <= t−k+n; i++)

{ a[t−1] = i;

generate(); // рекурсивний виклик функції generate()

}

t−−;

}

}

void main()

{ int j;

cout << "input k, n (k<n)\n k=";

cin >> k;

cout << "n=";

сіn >> n;

cout <<endl;

for (j = 1; j<=n−k+l; j++)

{a[t−1]=j;

generate();

}

getch();

}

Класичним прикладом використання рекурсії є також швид­ке сортування — один з найефективніших методів сортування.

Загальний алгоритм швидкого сортування здійснюється та­ким чином:

·         з масиву вибирається деякий опорний елемент аі, (частіше — центральний);

·         виконується процес розподілу масиву, що переміщує всі елементи, менші або рівні аі, вліво від нього, а всі елементи, більші або рівні аі, — вправо;

·         тепер масив складається з двох підмасивів, причому лі­вий менше або дорівнює правому