Algorytmika i Programowanie.
Funkcje cz. II
Zakład Zastosowań Informatyki
w In\
ynierii LÄ…dowej
Wydział In\
ynierii LÄ…dowej
Politechnika Warszawska
SÅ‚awomir Czarnecki
Rekurencja
" Jeśli funkcja zawiera w swoim kodzie wywołanie siebie samej, to
taką funkcję nazywamy rekurencyjną a wywołanie nazywamy
wywołaniem rekurencyjnym.
" Rekurencyjne wywołania mogą być bardziej skomplikowane i np.
rekurencyjna funkcja fun1 mo\
e wywoływać funkcję fun2, a ta z kolei
mo\
e wywoływać funkcję fun1.
" Rekurencja jawić się mo\
e jako doskonały przepis na tworzenie
nieskończonych pętli i tak niestety się najczęściej dzieje jeśli
napiszemy niepoprawnie funkcjÄ™ rekurencyjnÄ….
" Zatrzymanie nieskończonej pętli (czyli wyjście z programu, który
się zawiesił) na komputerze PC w systemie Windows polega na
jednoczesnym naciśnięciu klawiszy Ctrl-Alt-Del, o czym szczególnie
warto pamiętać przed rozpoczęciem pisania programów z funkcjami
rekurencyjnymi.
" Warunkiem bezwzględnie koniecznym, jaki musi być spełniony
w ka\
dej wersji funkcji rekurencyjnej jest poprawne sformułowanie
tzw. warunku stopu.
" W jakich dziedzinach mo\
na w naturalny sposób sięgać do
rozwiązań programistycznych u\
ywajÄ…c tej techniki definiowania
funkcji ?
" Odpowiedz
nie jest wcale taka oczywista, poniewa\
w bardzo wielu i
ró\
nych dziedzinach \
ycia i nauki (szczególnie matematyki)
spotykamy się z problemami, które mają charakter zadań szczególnie
predysponujący do szukania ich rozwiązań na drodze myślenia
w kategoriach rekurencji.
" Prostym przykładem problemu rekurencyjnego jest napisanie
kodu silni liczby N, jako iloczynu kolejnych liczb 1×2×3...×N.
" Przeanalizujmy jednak inny (jeszcze prostszy) przykład.
" Napiszmy kod w formie funkcji rekurencyjnej poszukiwania n-tej
potęgi liczby x ( xn ).
double power(double x,int n)
{
if(n < 0)
{
cout << endl
<< "Negative index, program terminated.";
exit(1);
}
if(n)
return x*power(x, n-1);
else
return 1.0;
}
double power(double x,int n)
" Poniewa\
zamierzamy tylko
{
obliczać dodatnie potęgi
if(n < 0)
liczby x, od razu na poczÄ…tku
{
sprawdzamy oczywisty
cout << endl
warunek i w przypadku jego
<< "Negative index, program terminated.";
exit(1);
niespełnienia, kończymy
}
wykonywanie programu.
if(n)
" Brak tego warunku, ze
return x*power(x, n-1);
względu na postać naszej
else
funkcji rekurencyjnej,
return 1.0;
} prowadziłby do nieskończonej
pętli.
" W instrukcji if mamy zagwarantowane wyjście z funkcji rekurencyjnej
w przypadku kiedy wartość wykładnika potęgi n będzie równa 0,
bowiem w tym przypadku zwracana będzie wartość 1.0. We wszystkich
pozostałych przypadkach,  prowokowane są wywołania rekurencyjne
za instrukcjÄ… return, w wyra\
eniu x*power(x, n-1), z wykładnikiem
potęgi zmniejszonym w stosunku do aktualnej jego wartości o jeden.
" Widzimy zatem, \
e wewnÄ…trz funkcji power(...), w przypadku gdy
przy jej pierwszym wywołaniu wartość wykładnika n będzie ostro
większa od zera, nastąpi kolejne wywołanie tej samej funkcji, ale
tym razem z wykładnikiem zmniejszonym o 1.
" Mo\
na Å‚atwo zauwa\
yć, \
e liczba wywołań rekurencyjnych funkcji
power(...) będzie dokładnie równa n (nie licząc pierwszego
wywołania funkcji).
" UWAGA ! Z reguły nie potrafimy w tak prosty sposób przewidzieć
liczby wywołań rekurencyjnych, co w szczególnie trudnych
przypadkach mo\
e wymagać bardzo wnikliwej i subtelnej analizy
matematycznej problemu.
" Mechanizm kolejnych wywołań rekurencyjnych został
zilustrowany poni\
ej dla wartości wykładnika potęgi n = 3.
double power(x,3)
3
x*x*x
double power(double x,int n)
{
...
return x*power(x, n-1);
...
}
x*x 2
double power(double x,int n)
{
...
return x*power(x, n-1);
...
}
x 1
double power(double x,int n)
{
...
return x*power(x, n-1);
...
}
1 0
double power(double x,int n)
{
...
return 1.0;
...
}
f& Największy wspólny dzielnik (NWD) dwóch liczb naturalnych jest
iloczynem wspólnych dla tych liczb współczynników ich
rozkładów na czynniki pierwsze.
Ä„% Algorytm Euklidesa  wersja rekurencyjna
Å›% Pre: m i n  dwie liczby naturalne > 0.
Å›% Post: NWD tych liczb: m i n
Algorithm
long nwd(long m,long n)
{
if((n <= m) && (m % n == 0))
return n;
else if(m < n)
return nwd(n,m);
else
return nwd(n,m%n);
}
#include
using namespace std;
long nwd (long m,long n)
{
if((n <= m) && (m % n == 0))
return n;
else if(m < n)
return nwd(n,m);
else
return nwd(n,m%n);
}
void main()
{
long m,n,NWD;
cout<charakterystyczne cechy:
jeden lub kilka prostych przypadków problemu (nazywanych
przypadkami stopu) majÄ… proste, nierekurencyjne rozwiÄ…zanie,
dla innych przypadków,umiemy utworzyć proces (u\
ywajÄ…c
techniki rekurencyjnej) sformułowania przypadku ogólniejszego
w terminach przypadków mniej ogólnych i prostszych,
powy\
szy proces prowadzić powinien do najprostszych
przypadków stopu (patrz początek).
" Algorytmy rekurencyjne mają w uproszczeniu następującą
 architekturę , którą mo\
na zapisać w tzw. pseudo-kodzie przy
u\
yciu instrukcji if
if osiągnięto przypadek stopu
rozwiÄ…\
problem
else
zredukuj problem u\
ywajÄ…c rekurencji.
" Pomimo tego, \
e rozwiÄ…zania rekurencyjne sÄ… generalnie mniej
efektywne od ich iteracyjnych odpowiedników (głównie z powodu
du\
ej liczby wywołań funkcji), to jednak w wielu przypadkach
rozumowanie rekurencyjne umo\
liwia i to w bardzo naturalny,
a często nawet w zaskakująco prosty sposób, uzyskać rozwiązanie
problemu, dla którego rozwiązanie iteracyjne jest niezwykle trudne
lub wręcz niemo\
liwe do znalezienia.
" Z tego właśnie powodu, rekurencja pełni bardzo wa\
nÄ… rolÄ™
w algorytmice i programowaniu.
" Poprawność matematyczną algorytmów rekurencyjnych dowodzi
się metodami indukcji matematycznej i z tego właśnie powodu
etap konstruowania algorytmu rekurencyjnego dla konkretnego
problemu ma tak ścisły związek z notacją i technikami dowodzenia
indukcyjnego.
Klasyczny problem rekurencyjny: Wie\
e z Hanoi
" Problem (nie matematycznej natury) dotyczy krÄ…\
ków uło\
onych w wie\
y
(powiedzmy F) jeden na drugim, od największego na samym dole do najmniejszego
na samej górze, które przy dysponowaniu dwoma dodatkowymi i identycznymi
wie\
ami (powiedzmy A i T), nale\
y przenieść na jedną z nich (powiedzmy na
wie\
ę T) stosując następujące trzy reguły:
1. za ka\
dym razem mo\
na przenosić tylko jeden krą\
ek
2. krÄ…\
ek wolno pobierać z wie\
y wyłącznie z samej góry i podobnie wolno kłaść go
na samą górę w innej wie\
y
3. przy ka\
dym przenoszeniu krÄ…\
ka, nie mo\
na dopuścić do sytuacji aby krą\
ek o
większej średnicy le\
ał na krą\
ku o mniejszej średnicy
DysponujÄ…c zatem tylko trzema wie\
ami (F, A, T), musimy stosujÄ…c powy\
sze trzy
reguły przenieść dowolną ustaloną liczbę krą\
ków z pierwszej wie\
y F na trzeciÄ…
wie\
Ä™ T, korzystajÄ…c dodatkowo tylko z drugiej wie\
y pomocniczej A.
1
2
3
T
F A
(To)
(From) (Auxiliary)
1
2
3
T
F A
(To)
(From) (Auxiliary)
2
Krok 1
1
3
Krok 2
1
3 2
1
Krok 3
3 2
1
Krok 4
3
2
Krok 5
3
1
2
2
Krok 6
3
1
1
2
Krok 7
3
T
F A
(To)
(From) (Auxiliary)
Jak rozwiązać problem dla 4, 5, ... , n krą\
ków ?
" Znajdziemy rozwiÄ…zanie dla dowolnej liczby n-krÄ…\
ków
wykorzystujÄ…c technikÄ™ rekurencyjnÄ….
" Idea pomysłu, polega na tym, aby powtarzać (rekurencyjnie) ka\
dy
problem dla n-krÄ…\
ków dzieląc go na dwa podproblemy:
problem z n-1 dyskami i
problem z 1-dyskiem
w celu osiągnięcia przypadku tylko z 1-dyskiem, który jest trywialny i
który potrafimy rozwiązać.
Algorytm wie\
y z Hanoi
Pre: N = liczba krÄ…\
ków (dysków) (zakładamy, \
e N > 0)
" Wie\
e F,A,T będą reprezentowane przez tablicę liczb naturalnych
" KrÄ…\
ek o największej średnicy ma przyporządkowaną liczbę N.
" KrÄ…\
ek o najmniejszej średnicy ma przyporządkowaną liczbę 1.
" Pozostałe krą\
ki sÄ… oznaczone przez numery od 2 do N 1
w zale\
ności od ich średnic.
Stan poczÄ…tkowy:
F[N 1]=1 A[N 1]=0 T[N 1]=0
F[N 2]=2 A[N 2]=0 T[N 2]=0
F[N 3]=3 A[N 3]=0 T[N 3]=0
... ... ...
F[ 1 ]= N 1 A[ 1 ]=0 T[ 1 ]=0
F[ 0 ]= N A[ 0 ]=0 T[ 0 ]=0
F[i]=0 , A[i]=0 lub T[i]=0 (i=0,1,.., N 1) oznacza puste
miejsce  brak krÄ…\
ka.
 Post:
Stan końcowy:
F[N 1]=0 A[N 1]=0 T[N 1]=1
F[N 2]=0 A[N 2]=0 T[N 2]=2
F[N 3]=0 A[N 3]=0 T[N 3]=3
... ... ...
F[ 1 ]=0 A[ 1 ]=0 T[ 1 ]= N 1
F[ 0 ]=0 A[ 0 ]=0 T[ 0 ]= N
ALGORYTM (z elementarnym dowodem)
Jeśli n = 1 (przypadek elementarny) to przenieś dysk 1 z FROM
na TO.
Jeśli n >= 2 to załó\
my, \
e potrafimy przenieść n  1 dysków z
dowolnej wie\
y na innÄ… dowolnÄ… wie\
ę (zało\
enie indukcyjne).
Wtedy nasz problem mo\
e być zredukowany do 3 pod-problemów.
- Pod-problem 1: przenieś górne n  1 dysków z FROM na
AUXILIARY u\
ywajÄ…c TO jako wie\
Ä™ pomocniczÄ…
(zało\
enie indukcyjne).
Teraz, na AUXILIARY mamy wszystkie górne n  1 dysków
z FROM a na FROM pozostał tylko największy dysk n.
- Pod-problem 2: przenieś największy dysk n z FROM na
TO (przypadek elementarny).
Teraz wie\
a FROM jest pusta.
- Pod-problem 3: przenieś wszystkie n  1 dysków z AUXILIARY
na TO u\
ywajÄ…c FROM jako wie\
Ä™ pomocniczÄ…
(zało\
enie indukcyjne).
" Wartości liczby n"[1,2,...,N] będą zale\
eć od poziomu rekurencji i
tablice FROM,AUXILIARY,TO oznaczać będą ró\
ne, fizycznie
istniejÄ…ce N wymiarowe tablice F lub A lub T tak\
e w zale\
ności od
aktualnego wywołania funkcji rekurencyjnej.
" Oznacza to na przykład, \
e mo\
liwe jest następujące  przypisanie
FROM = A
AUXILIARY = T
TO = F
dla jakiegoś wywołania rekurencyjnego funkcji.
n-1
n
FROM AUXILIARY TO
Pod-problem 1: przenieś górne n  1 dysków z FROM na
AUXILIARY u\
ywajÄ…c TO jako wie\
Ä™ pomocniczÄ…
(zało\
enie indukcyjne)
FROM AUXILIARY TO
Pod-problem 2: przenieś największy dysk n z FROM na TO
(przypadek elementarny)
FROM AUXILIARY TO
Pod-problem 3: przenieś wszystkie n  1 dysków z AUXILIARY
na TO u\
ywajÄ…c FROM jako wie\
Ä™ pomocniczÄ…
(zało\
enie indukcyjne)
#include
Wie\
e z Hanoi  implementacja algorytmu
#include
using namespace std;
Tylko dla wywoływania funkcji bibliotecznej
const int N=3;
getchar() - patrz implementacja funkcji
int F[N]={0};
actualState()
int A[N]={0};
int T[N]={0};
void initHanoi();
void actualState();
void move(int* FROM,int* TO);
void hanoi(int* FROM,int* AUXILIARY,int* TO,int n);
void main(void)
{
initHanoi();
actualState();
hanoi(F,A,T,N);
}
//inicjalizacja tablicy F liczbami naturalnymi od N do 1
void initHanoi()
{
cout<for(int k = 0 ; k < N ; k++)
F[k] = N - k;
}
//funkcja actualSate() wyświetla stan aktualny tablic F,A,T
void actualState()
{
for(int k = N  1 ; k > -1 ; k--)
{
cout<cout<<"F["<cout<<" A["<cout<<" T["<}
cout<getchar();
}
void move(int* FROM,int* TO){ //funkcja move(int* FROM,int* TO)
static int counter=1; //static zmienna zainicjalizowana 1
int a; //zmienna oznaczajÄ…ca przenoszony dysk
cout<for(int i = 0 ; i < N ; i++) //szuka dysku na samym wierzchu FROM
if((FROM[i] == 0) | | (i == N-1)) //czyli puste miejsce albo ostatni dysk
if(FROM[i] == 0)
{
a = FROM[i-1]; //zabiera go
FROM[i-1] = 0; //... oznacza puste miejsc jako 0
break;
}
else
{
a = FROM[i]; //zabiera go
FROM[i] = 0; //... oznacza puste miejsce jako 0
break;
}
for(i = 0 ; i < N ; i++) //szuka pierwszego wolnego miejsca na TO
if(TO[i] == 0) //... takie musi siÄ™ znalez
ć
{
TO[i] = a; //wkłada zabrany wcześniej dysk na to wolne miejsce
break;
}
actualState();
counter++; //inkrementuje licznik counter wywołań funkcji o 1
}
void hanoi(int* FROM,int* AUXILIARY,int* TO,int n)
Rekurencyjna
{
funkcja hanoi(..)
if(n == 1)
move(FROM,TO); //przypadek elementarny
else
{
//Pod-problem 1
//z FROM na AUXILIARY przy pomocy TO
hanoi(FROM,TO,AUXILIARY,n-1);
//Pod-problem 2
//z FROM na TO
Dwa wywołania funkcji
move(FROM,TO);
hanoi(..)
//Pod-problem 3
//z AUXILIARY na TO przy pomocy FROM
hanoi(AUXILIARY,FROM,TO,n-1);
}
}
Uruchomienie programu dla N=3
Dla większej liczby dysków N = 5 otrzymamy następujący wydruk:
Wywołania Wywołania
funkcji Funkcji
move(...) move(...)
1  6 7  13
Wywołania Wywołania
funkcji funkcji
move(...) move(...)
14  20 21  27
Wywołania
Całkowita liczba
funkcji
przeniesień krą\
ków:
move(...)
2N  1= 25  1 = 31.
28  31
" For N = 64 we have 264  1 i.e. about 18 billions (in England) or
18 trillions (in USA) moves of disks from tower to tower.
" Assuming, that we have only 1 microsecond for one move, the total
time needed to move all 64 disks from tower F to tower T is about:
5000 centuries !
Wskaz
niki do funkcji
" Wskaz
nik danego typu mo\
e przechowywać adres zmiennej tego
samego typu  taka była dotychczas rola wskaz
nika.
" OkazujÄ™ siÄ™ jednak, \
e istnieją w języku C++ wskaz
niki, które
mogą przechowywać tak\
e ... adresy funkcji, tj. adresy miejsca w
pamięci operacyjnej, w którym został umieszczony początek kodu
funkcji (podobnie jak adres pierwszego elementu tablicy).
" Zyskujemy przez to dodatkowÄ… mo\
liwość wywoływania funkcji
przez odpowiednie u\
ycie wskaz
nika do funkcji.
" Nie ma w języku C++ uniwersalnego wskaz
nika na funkcje,
podobnie jak nie ma uniwersalnego wskaz
nika na typy podstawowe.
" W momencie definiowania wskaz
nika na funkcjÄ™, musimy zatem
dokładnie określić jakiego typu adresy funkcji ma on przechowywać
tzn. sprecyzować typ zwracanej wartości i listę parametrów funkcji.
" Dopiero wtedy i po uprzednim zainicjalizowaniu takiego wskaz
nika
adresem zdefiniowanej ju\
wcześniej funkcji, mamy dodatkową
mo\
liwość jej wywoływania właśnie poprzez ten wskaz
nik.
Deklarowanie wskaz
ników do funkcji
" Zadeklarujmy wskaz
nik pfun, którym będziemy mogli wskazywać
funkcje (przechowywać adresy funkcji), które mają dwa parametry
typu odpowiednio double* , int i które zwracają wartości typu
double.
" Deklaracja takiego wskaz
nika jest następująca:
double (*pfun)(double*, int);
" DeklaracjÄ™ takÄ… czytamy, pfun, jest wskaz
nikiem na funkcje, których
lista parametrów składa się z dwóch argumentów: pierwszego typu
wskaz
nik na double i drugiego typu int, i które zwracają wartości
typu double.
" Nawiasy wokół identyfikatora pfun oraz gwiazdki *, są bezwzględnie
konieczne, poniewa\
bez tych nawiasów byłaby to deklaracja funkcji,
której lista parametrów składałaby się z dwóch argumentów:
pierwszego typu wskaz
nik na double i drugiego typu int, i która
zwracałaby wskaz
nik na typ double :
double *pfun(double*, int);
double *pfun(double*, int); double (*pfun)(double*, int);
" To jest prototyp funkcji, która ma dwa parametry i zwraca wskaz
nik
na typ double.
" To jest deklaracja wskaz
nika na funkcje, które mają dwa parametry i
zwracają wartości typu double.
" Ogólna zasada deklaracji wskaz
ników na funkcje:
zwracany_typ (*nazwa_wskaz
nika)(lista_parametrów_funkcji);
" Wskaz
nik mo\
e tylko wskazywać na funkcje, które zwracają
ten sam zwracany_typ i które mają taką samą
lista_parametrów_funkcji wyspecyfikowaną w deklaracji.
" To nam pokazuje, \
e deklaracja wskaz
nika na funkcje ma trzy
składniki:
zwracany_typ funkcji
nazwa_wskaz
nika poprzedzona gwiazdkÄ… *
lista_parametrów_funkcji
" Mo\
emy inicjalizować wskaz
nik na funkcjÄ™ w momencie jego
deklaracji, np.
double f(double* x); //Deklaracja funkcji
double (*pfun)(double*) = f; //Deklaracja i inicjalizacja wskaz
nika
//na funkcje
#include
" W zaprezentowanym
using namespace std;
obok programie,
long sum(long a,long b);// Function prototype
pokazany został
long product(long a,long b);// Function prototype
przykład u\
ycia
int main()
wskaz
ników do funkcji
{
//Pointer to function declaration
" Deklarujemy wskaz
nik
long (*pdo_it)(long,long);
pdo_it do funkcji, który
pdo_it = product;
będzie mógł wskazywać
cout << endl
dowolną z dwóch funkcji
//Call product thru a pointer
sum(...) lub product(...).
<< "3*5 = " << pdo_it(3, 5);
pdo_it = sum;//Reassign pointer to sum()
cout << endl
<< "3*(4+5) + 6 = "
//Call thru a pointer twice
<< pdo_it(product(3, pdo_it(4, 5)), 6);
cout << endl;
return 0;
}
#include
using namespace std;
long sum(long a,long b);// Function prototype
long product(long a,long b);// Function prototype
// Function to multiply two values
long product(long a, long b)
{
return a*b;
}
// Function to add two values
long sum(long a, long b)
{
return a+b;
}
#include
" W tym miejscu
using namespace std;
inicjalizujemy wskaz
nik
long sum(long a,long b);// Function prototype
na funkcje, adresem
long product(long a,long b);// Function prototype
funkcji product(...)
int main()
w instrukcji:
{
//Pointer to function declaration
pdo_it = product;
long (*pdo_it)(long,long);
(nazwa funkcji jest w tym
pdo_it = product;
momencie automatycznie
cout << endl
konwertowana na jej
//Call product thru a pointer
adres)
<< "3*5 = " << pdo_it(3, 5);
pdo_it = sum;//Reassign pointer to sum()
" Funkcja product() jest
cout << endl
wywoływana poprzez
<< "3*(4+5) + 6 = "
wskaz
nik pdo_it
//Call thru a pointer twice
bezpośrednio w
<< pdo_it(product(3, pdo_it(4, 5)), 6);
wyra\
eniu instrukcji
cout << endl;
return 0;
wyjścia.
}
#include
using namespace std;
long sum(long a,long b);// Function prototype
long product(long a,long b);// Function prototype
int main()
{
//Pointer to function declaration
long (*pdo_it)(long,long);
" Nazwa wskaz
nika
pdo_it = product;
wraz z argumentami
cout << endl
ujętymi w parę
//Call product thru a pointer
<< "3*5 = " << pdo_it(3, 5); nawiasów jest u\
yta w
pdo_it = sum;//Reassign pointer to sum()
sposób dokładnie taki
cout << endl
sam jakby to była
<< "3*(4+5) + 6 = "
nazwa funkcji.
//Call thru a pointer twice
<< pdo_it(product(3, pdo_it(4, 5)), 6);
cout << endl;
return 0;
}
#include
" Teraz wskaz
nik pdo_it
using namespace std;
będzie przechowywał
long sum(long a,long b);// Function prototype
adres innej funkcji
long product(long a,long b);// Function prototype
sum(...).
int main()
" U\
ywamy go ponownie,
{
//Pointer to function declaration
tym razem nawet w
long (*pdo_it)(long,long);
bardziej zło\
onej instrukcji
pdo_it = product;
i to razem z wywołaniem
cout << endl
bezpośrednim funkcji
//Call product thru a pointer
product(...).
<< "3*5 = " << pdo_it(3, 5);
pdo_it = sum;//Reassign pointer to sum()
" Przykład ten ilustruje fakt,
cout << endl
\
e wskaz
nik do funkcji
<< "3*(4+5) + 6 = "
mo\
emy u\
ywać dokładnie
//Call thru a pointer twice
w ten sam sposób jak
<< pdo_it(product(3, pdo_it(4, 5)), 6);
funkcję na którą wskazuje.
cout << endl;
return 0;
}
" Po uruchomieniu programu, na ekranie zobaczymy następujący
wydruk:
potwierdzający poprawność u\
ycia wskaz
nika do funkcji w naszym
programie.
Wskaz
nik do funkcji jako argument funkcji
#include
#include
using namespace std;
const int JMAX = 40;
//U\
ycie metody bisekcji znajdowania pierwiastka funkcji func, o którym
//wiadomo, \
e le\
y pomiędzy x1 i x2. Pierwiastek jest zwracany z dokładnością
//+- xacc.
double rtbis(double (*func)(double),double x1,double x2,double xacc);
" Wskaz
niki do funkcji przydajÄ…
double myFunction(double x);
void main()
szczególnie w sytuacjach kiedy
{
piszemy jakÄ…Å› procedurÄ™ (u\
yto
double XACC = 1.0e-7;
jako synonimu słowa funkcja),
double X1=3;
w której w naturalny sposób
double X2=4;
pojawia się konieczność u\
ycia
double root;
root=rtbis(myFunction,X1,X2,XACC);
funkcji jako parametru.
cout<}
double myFunction(double x)
{
return pow(sin(x)+0.57721566,3);
}
f(x) = (sin(x)+0.57721566)3
double rtbis(double (*func)(double),double x1,double x2,double xacc)
UWAGA! Przykład alternatywnego sposobu u\
ycia wskaz
nika do funkcji
{
int j;
" Funkcja rtbis(...) ma parametr
double dx,f,fmid,xmid,rtb;
func, który jest wskaz
nikiem
f=(*func)(x1);
na funkcję (oczywiście
fmid=(*func)(x2);
odpowiedniego typu).
if(f*fmid >= 0.0)
cout<rtb = f < 0.0 ? (dx=x2-x1,x1) : (dx=x1-x2,x2);
for(j=1;j<=JMAX;j++)
" U\
yta jest metoda bisekcji
{
fmid=(*func)(xmid=rtb+(dx *= 0.5));
znajdowania pierwiastka
if(fmid <= 0.0)
funkcji func, o którym
rtb=xmid;
wiadomo, \
e le\
y pomiędzy
if((fabs(dx) < xacc) || (fmid == 0.0))
x1 i x2.
return rtb;
" Pierwiastek jest zwracany
}
cout<jako wartość lokalnej zmiennej
return 0.0;
rtb w momencie osiągnięcia
}
dokładności ą xacc.
#include
#include
using namespace std;
const int JMAX = 40;
double rtbis(double (*func)(double),double x1,double x2,double xacc);
double myFunction(double x);
void main()
{
double XACC = 1.0e-7;
double X1=3;
" Przykład wywołania (gotowej)
double X2=4;
funkcji rtbis(...) z parametrami
double root;
myFunction , X1 , X2 , XACC,
root=rtbis(myFunction,X1,X2,XACC);
z których pierwszym parametrem
cout<jest wskaz
nik do zdefiniowanej
}
(gdzieÅ›) w programie funkcji
" W tym przypadku parametr jest
myFunction(...) dla której
przekazywany explicite jako
poszukiwany jest pierwiastek
nazwa funkcji (bez uprzedniego
w przedziale (X1,X2) z
deklarowania wskaz
nika).
dokładnością XACC.
f(x) = (sin(x)+0.57721566)3
Tablice wskaz
ników do funkcji
" W podobny sposób jak dla zwykłych wskaz
ników, mo\
emy
deklarować tablice wskaz
ników do funkcji.
" Mo\
emy tak\
e inicjalizować takie tablice w momencie ich deklaracji.
" Poka\
emy przykład deklaracji tablicy wskaz
ników do funkcji:
double sum(double, double); // Prototyp funkcji
double product(double, double); // Prototyp funkcji
double difference(double, double); // Prototyp funkcji
double (*pfun[3])(double,double) = { sum, product, difference };
" Ka\
dy z elementów tej tablicy zostanie zainicjalizowany odpowiednim
adresem funkcji umieszczonym na liście inicjalizacyjnej pomiędzy
nawiasami { ... }.
" Wywołanie funkcji product(...) mo\
e być dokonane np. w następujący
sposób: pfun[1](2.5, 3.5);
" W nawiasie kwadratowym [...] umieszczamy numer składowej tej
tablicy, który przechowuje adres funkcji product(...).
Dynamiczne alokowanie pamięci dla tablic wskaz
ników do funkcji
" Operator new nie mo\
e być u\
yty w kontekście alokowania funkcji
(nie ma bowiem nawet takiego pojęcia w języku C++), ale mo\
e być
u\
yty do alokowania tablicy wskaz
ników do funkcji.
" Dynamiczne alokowanie tablicy wskaz
ników do funkcji jest podobne
do alokowania tablic zwykłych typów (a raczej do alokowania tablic
wskaz
ników do zwykłych typów).
" W poni\
szym przykładzie alokujemy, w sposób dynamiczny za
pomocÄ… operatora new, trzy-elementowÄ… tablicÄ™ wskaz
ników do
funkcji, których argumentem jest double* (wskaz
nik na typ double)
i które zwracają wartości typu double.
double(*(*p))(double*)= new (double (*[3])(double*));
...
delete [] p; ... pamiętajmy, \
e dynamicznie alokowane
tablice same siÄ™ nie usuwajÄ… !
" Zauwa\
my, \
e deklarujÄ…c tablicÄ™ wskaz
ników do funkcji, musimy
u\
yć  podwójny wskaz
nik **  , a nie jak pozornie by nam siÄ™ w
pierwszej chwili wydawało  pojedynczy wskaz
nik *  (bo przecie\

nie chcemy deklarować tablicy dwuwymiarowej !):
double(*(*p))(double*)
" Powy\
szy zapis czytamy bowiem następująco:
p jest wskaz
nikiem
*p ...
na wskaz
nik ...
*(*p) tu właśnie  powstaje podwójny wskaz
nik
na funkcjÄ™
(*(*p))(...) ,
której argumentem jest wskaz
nik na double
(*(*p))(double*)
i która zwraca typ double
double(*(*p))(double*)
" Wynika to oczywiście z faktu, \
e nasza tablica (jednowymiarowa)
ma przechowywać elementy, które są wskaz
nikami.
" Zauwa\
my dalej, \
e pierwszym elementem w tej tablicy będzie
wskaz
nik (konkretnie wskaz
nik na funkcjÄ™)
" Zatem element ten wskazywać będzie wskaz
nik na ten element, czyli
wskaz
nik na wskaz
nik na funkcję, czyli mówiąc jeszcze inaczej:
adresem pierwszego elementu w naszej tablicy będzie
wskaz
nik na wskaz
nik na funkcjÄ™.
" Co zatem z prawÄ… stronÄ…
new (double (*[3])(double*)),
w której rezerwowana jest pamięć dla takiej tablicy ?
" Powy\
szy zapis czytamy następująco ( od środka ):
tworzona jest tablica
[...]
trzy-elementowa
[3]
wskaz
ników
*[3]
na funkcje
(*[3])(...)
których argumentem jest wskaz
nik na double
(*[3])(double*)
i które zwracają wartość typu double
(double (*[3])(double*))
" Operator new (zgodnie z jego definicjÄ…) zwraca adres pierwszego
elementu tworzonej tablicy  inaczej mówiąc zwraca wskaz
nik na
jej pierwszy element, czyli w naszym przypadku zwraca wskaz
nik
na wskaz
nik na funkcję (bo elementami tej tablicy są właśnie
wskaz
niki na funkcjÄ™).
" PrzyjmujÄ…c nazwÄ™ tej tablicy jako p zwracany jest w takim razie
**p ...  stąd podwójny wskaz
nik.
" Zauwa\
my, \
e jeśli potraktujemy argument  naszych funkcji
(double*) jako tablice, na przykład jako dwuelementowe tablice
utworzone dynamicznie
double* y=new double[2];
to wtedy definicja 3-elementowej tablicy takich funkcji, w instrukcji
double(*(*p))(double*)= new (double (*[3])(double*));
będzie matematycznie równowa\
na definicji funkcji wektorowej
p: R2 R3 ; "y"R2 p(y)=(p0(y), p1(y),p2(y))"R3
gdzie dla ka\
dego k"{0,1,2}
pk:R2 R
jest funkcją rzeczywistą dwóch zmiennych y=(y0,y1)"R2.
" Poni\
ej zilustrujemy zastosowanie tablicy trzech funkcji:
fun0 , fun1 , fun2:
double fun0(double* x)
{
return x[0]*x[1];
}
double fun1(double* x)
{
return x[0]+x[1];
}
double fun2(double* x)
{
return x[1]-x[0];
}
#include
using namespace std;
double fun0(double* x); //Function prototype
double fun1(double* x); //Function prototype
double fun2(double* x); //Function prototype
void main()
{
int k,n,m;
n=2;//inicjalizowane podczas wykonywania programu !
m=3;// inicjalizowane podczas wykonywania programu !
double(*(*p))(double*)=NULL;
double* y=NULL;
p= new (double (*[m])(double*));
y=new double[n];
p[0] =fun0;
p[1] =fun1;
p[2] =fun2;
y[0] =10;
y[1] =11;
for(k=0;kcout<if(y!=NULL)
delete [] y;
double fun0(double* x){return x[0]*x[1];}
if(p!=NULL)
double fun1(double* x){return x[0]+x[1];}
delete [] p;
}
double fun2(double* x){return x[1]-x[0];}
Przeładowanie nazw funkcji
" Załó\
my, \
e mamy funkcję, która zwraca maksymalną wartość
tablicy typu double, która jest przekazywana jako argument:
double maxdouble(double* array, int len)
{
double max = array[0];
for(int i=1; iif(maxmax = array[i];
return max;
}
" Chcielibyśmy zdefiniować teraz funkcję, która zwraca maksymalną
wartość tablicy typu long, która tak\
e jest przekazywana jako
tej funkcji. Funkcja taka mogłaby mieć deklarację analogiczną do
poprzedniej, np.:
long maxlong(long* array, int len);
Na czym polega przeładowanie nazw funkcji ?
" Przeładowanie nazwy funkcji pozwala nam na u\
ywanie tej samej
nazwy dla ró\
nych funkcji.
" Jeśli jednak dopuszczamy ju\
takÄ… mo\
liwość, to skąd kompilator
mo\
e wiedzieć, której wersji funkcji (o tej samej nazwie) ma w danej
instrukcji u\
yć.
" Kluczem do odpowiedzi jest lista parametrów funkcji.
" Funkcje, które mają ró\
ne listy parametrów, mogą mieć te same
nazwy.
" Przykładowo, nic nie stoi na przeszkodzie, aby trzy poni\
ej
zadeklarowane funkcje miały te same nazwy:
int max(int* array,int len);
long max(long* array,int len);
double max(double* array,int len);
" Podsumowując, wszystkie funkcje, które mają tą samą nazwę, muszą
równocześnie ró\
nić się listą swoich parametrów.
" Uwaga ! Zwracany typ przez funkcję nie ró\
nicuje funkcji w
kwestii przeładowania nazw.
" Oznacza to, \
e na przykład, nie mo\
emy zdefiniować funkcji
double max(long* array, int len);
poniewa\
ró\
niłaby się ona od wcześniej zadeklarowanej funkcji
long max(long* array, int len);
jedynie typem zwracanej wartości.
long max(long* x,int len) " Definicje dwóch ró\
nych
{ funkcji o tej samej nazwie.
long max = x[0];
for(int i=1;iif(maxmax=x[i];
return max;
}
double max(double* x,int len)
{
double max=x[0];
for(int i=1;iif(maxmax=x[i];
return max;
}
#include
using namespace std;
long max(long* array, int len);
double max(double* array, int len);
int main()
{
long medium[]={57,577,5,566,49,328};
double large[]={5.7,57.7,5.0,56.6,4.9,3.21};
int lenmedium=sizeof medium/sizeof medium[0];
int lenlarge=sizeof large/sizeof large[0];
cout<cout<" Mamy dwie deklaracje
cout<przeładowanych funkcji max().
return 0;
} " W ka\
dej z instrukcji wyjścia
odpowiednia wersja funkcji
max() będzie wybrana przez
kompilator na podstawie listy
parametrów  ró\
nej w obu
przypadkach.
Szablony funkcji  krótka wzmianka
" Ostatni przykład, wskazuje na brak pewnej cechy w przeładowywaniu
nazw funkcji, które mają niemal identyczny kod, ró\
niÄ…cy siÄ™ w obu
definicjach tych funkcji wyłącznie typem przekazywanych parametrów
i konsekwentnie typem lokalnych zmiennych.
" Ta cecha to mo\
liwość napisania wspólnego kodu takich funkcji,
w którym to kodzie, pojawiające się typy zmiennych byłyby w jakiś
sposób sparametryzowane.
" Okazuje siÄ™, \
e jednak istnieje mo\
liwość automatycznego
generowania kodu takich funkcji w zale\
ności od typu u\
ywanych
zmiennych przekazywanych na liście parametrów, którą określamy
jako mo\
liwość tworzenia szablonów funkcji.
" Kod funkcji generowanej na podstawie jej szablonu ma wszystkie
cechy klasycznego kodu.
" Prześledz
my na prostym przykładzie funkcji max() jak wygląda
definiowanie szablonu takiej funkcji.
" Definiujemy szablon funkcji max() następująco:
template T max(T* x,int len)
" SÅ‚owo kluczowe template
{
identyfikuje to co jest dalej
T max = x[0];
napisane jako definicjÄ™
for(int i=1;iszablonu.
if(max" Nawiasy <...> zawierajÄ…
max=x[i];
typ u\
ywanych parametrów
return max;
do wygenerowania
}
odpowiedniej funkcji.
" SÅ‚owo kluczowe class przed T oznacza, \
e T jest typem parametru
dla tego szablonu.
template T max(T* x,int len)
" Gdziekolwiek uka\
e siÄ™ T w
{
definicji szablonu, będzie w tym
T max = x[0];
miejscu zastÄ…piony T przez
for(int i=1;iodpowiedni typ, np. long,
if(maxw momencie wywołania funkcji.
max=x[i];
return max;
}
#include
" Po uruchomieniu programu
using namespace std;
otrzymamy identyczny wynik
template T max(T* x,int len)
{
jak w poprzednim przykładzie.
T max = x[0];
for(int i=1;iif(maxmax=x[i];
return max;
}
int main()
{
long medium[]={57,577,5,566,49,328};
double large[]={5.7,57.7,5.0,56.6,4.9,3.21};
int lenmedium = sizeof medium/sizeof medium[0];
int lenlarge = sizeof large/sizeof large[0];
cout << endl << max(medium, lenmedium);
cout << endl << max(large, lenlarge);
cout << endl;
return 0;
}