M.A. Jankowska, G. Sypniewska-Kamińska LABORATORIUM NR 02
TEMAT : REKURENCJA W C++. WYBRANE ZAAWANSOWANE ZAGADNIENIA ZWIĄZANE Z FUNKCJAMI W C++
I. Funkcje rekurencyjne
Wywołanie funkcji C++ może mieć miejsce nie tylko w innej funkcji, z czym mieliśmy do czynienia dotychczas. Wywołanie funkcji może wystąpić także w jej własnej definicji. Funkcję, która wywołuje samą siebie nazywamy funkcją rekurencyjną.
Przepisz, skompiluj i wykonaj zamieszczony poniżej kod programu. Przeanalizuj jego działanie.
#include "stdafx.h"
#include <iostream>
using namespace std;
int silnia_rekurencja(int n);
int silnia_iteracja(int n);
int _tmain(int argc, _TCHAR* argv[])
{
cout << "Program oblicza wartosc funkcji silnia dla argumentow n <= 12" << endl; int n = 20;
while (n >=13)
{
cout << "Podaj wartosc n z przedzialu [0,12]. n = "; cin >> n;
}
cout << endl<< "n! = " << silnia_rekurencja(n)<< endl; cout << endl<< "n! = " << silnia_iteracja(n)<< endl; return 0;
}
int silnia_iteracja(int n)
{
int s = 1;
for (int i=1; i<=n;i++)
s = s*i;
return s;
}
int silnia_rekurencja(int n)
{
int s;
// zakończenie rekurencji po spełnieniu warunku if (n == 1) return 1;
s = n*silnia_rekurencja(n-1); // wywołanie funkcji silnia_rekurencja return s;
}
Funkcję n! określoną dla argumentów naturalnych można zdefiniować na dwa sposoby: definicja 1
n!=1⋅2⋅...⋅( n−1)⋅ n
definicja 2
1!=1,
n!= n⋅( n−1)! dla n>1
Pierwsza z przytoczonych wyżej definicji funkcji n! określa wartość funkcji w sposób bezpośredni dla każdego naturalnego argumentu n.
Druga z definicji określa bezpośrednio wartość funkcji tylko dla pewnego argumentu, w tym przypadku dla n=1. Wartości funcji dla argumentów n>1 określone są poprzez odwołanie do definicji tej samej funkcji dla argumentu mniejszego o jeden.
Definicje tego typu nazywane są definicjami rekurencyjnymi.
W zamieszczonym powyżej kodzie programu zdefiniowano dwie funkcje C++ realizujące to samo zadanie obliczenia wartości funkcji silnia. Funkcja silnia_iteracja oblicza wartość n! według algorytmu iteracyjnego, wynikającego z definicji 1.
Funkcja silnia_rekurencja oblicza wartość n! zgodnie z rekurencyjną definicją 2. Funkcja ta wywołuje samą siebie.
Aby ten proces nie trwał w nieskończoność, w definicji funkcji musi wystąpić przynajmniej jedna instrukcja return, realizowana po spełnieniu określonego warunku. W powyższym przykładzie rekurencyjny proces zostaje zakończony, gdy w wyniku zmniejszania Laboratorium 2
1
M.A. Jankowska, G. Sypniewska-Kamińska argumentu funkcji o jeden przyjmie on wartość n=1, dla której funkcja jest określona bezpośrednio.
if (n==1) return 1;
ZADANIA
1. Zmodyfikuj obie funkcje, tak aby obliczały wartość także dla argumentu n = 0. ( 0!=1 ) 2. Napisz funkcję rekurencyjną, która realizuje obliczanie n wyrazów ciągu Fibonacciego.
Rekurencyjna definicja ciągu Fibonacciego to 0 dla n=0,
F =
n
1 dla n=1,
F
+ F
dla n>1.
n−2
n−1
// systemy_Lab_02c.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
int Fibonacci_rekurencja(int n);
int Fibonacci_iteracja(int n);
int _tmain(int argc, _TCHAR* argv[])
{
cout << "Program oblicza wyrazy ciagu Fibonacciego" << endl; int n=100;
while ( n > 42)
{
cout << "Podaj wartosc n z przedzialu [1,42]. n = "; cin >> n;
}
cout << endl<< "F_"<<n<< " = " << Fibonacci_rekurencja(n)<< endl; cout << endl<< "F_"<<n<< " = " << Fibonacci_iteracja(n)<< endl; return 0;
}
int Fibonacci_rekurencja(int n)
{
int s;
if (n==1) return 1;
if (n==0 ) return 0;
s = Fibonacci_rekurencja(n-2)+Fibonacci_rekurencja(n-1);
// wywolanie funkcji
}
int Fibonacci_iteracja(int n)
{
if (n==1) return 1;
if (n==0) return 0;
int s, fpp=0,fp=1;
for(int i = 2; i<=n ;i++)
{
s = fpp + fp;
fpp = fp;
fp = s;
}
return s;
}
II. Modyfikator const
Gdy stosujemy mechanizm przekazywania argumentu do funkcji przez referencję, to parametr funkcji jest traktowany jak alias przekazywanego argumentu. Oznacza to, że przy wywołaniu funkcji parametr funkcji zostaje zainicjalizowany adresem aktualnego argumentu. Funkcja uzyskuje bezpośredni dostęp do argumentu aktualnego, może go zatem zmieniać. Przekazywanie argumentów przez referencję łączy w sobie zalety przekazywania prez wskaźnik, takie jak możliwość modyfikacji argumentu przez funkcję oraz szybsze działanie (nie ma konieczności kopiowania wartości), z prostotą implementacji właściwą przekazywaniu przez wartość (nie występują operacje adresowania i wyłuskiwania).
Poniżej zamieszczono kod programu wywołującego funkcję, która zmienia znak argumentu w przypadku, gdy argument ma Laboratorium 2
2
M.A. Jankowska, G. Sypniewska-Kamińska wartość ujemną.
#include "stdafx.h"
#include <iostream>
using namespace std;
float funkcja_wb(float& x);
int _tmain(int argc, _TCHAR* argv[])
{
float a;
cout << "Podaj dowolna liczbe wymierna: _ "; cin >>a; cout << endl<<"Jej wartosc bezwzgledna = "<< funkcja_wb(a); cout << endl<<"Po wywołaniu funkcji a = "<< a <<endl;
}
float funkcja_wb(float& x)
{
if( x < 0.0f) x = -x;
return x;
}
Próba wywołania funkcji funkcja_wb z parametrem będącym stałą zakończy się niepowodzeniem. Jeżeli na przykład w powyższym programie umieścimy instrukcję cout << endl<<"Wartosc bezwzgledna liczby -20.5 "<< funkcja_wb(-20.5); to po kompilacji pojawi się komunikat o błędzie error C2664: 'funkcja_wb' : cannot convert parameter 1 from 'float' to 'float &'
Można stosować mechanizm przekazywania parametrów przez referencję z jawną deklaracją, że argument funkcji nie zostanie zmodyfikowany. W nagłówku funkcji należy wówczas poprzedzić typ parametru formalnego kwalifikatorem const. Kompilator sprawdza (i ewentulnie wysyła komunikat o błędzie), czy w ciele funkcji parametr nie jest zmieniany pojawiając się jako lewa strona instrukcji przypisania albo w instrukcjach inkrementacji i dekrementacji. Użycie modyfikatora const zabezpiecza argument funkcji przed zmianami przy zachowaniu wszelkich zalet związanych z przekazywaniem parametrów przez referencję. W roli argumentów mogą w takim przypadku występować także stałe.
float funkcja_wb1(const float& x)
{
float w = x;
if( x < 0.0f ) w = -x;
return w;
}
III. Wskaźniki i referencje jako wynik funkcji W wyniku działania funkcji, z wyjątkiem funkcji typu void, w miejscu jej wywołania zostaje zwrócona pojedyncza wartość określonego typu. Funkcja może zwracać jako wynik także wskaźnik albo referencję. Rozwiązania te stwarzają całkiem nowe możliwości dla programisty. Między innymi zwracanie jako wyniku wskaźnika sprawia, że funkcja może przekazać dowolną ilość danych w postaci tablicy zainicjalizowanej zwracanym wskaźnikiem. Należy zapamiętać, że przy próbie zwrócenia adresu lokalnej zmiennej automatycznej funkcji wygenerowane zostanie ostrzeżenie, a program nie będzie działał poprawnie. Rozwiązaniem jest utworzenie za pomocą operatora new zmiennej/zmiennych wskaźnikowej w obszarze pamięci wolnej (na stercie).
Poniżej zamieszczono kod programu wywołującego funkcję, która przydziela pamięć jednowymiarowej tablicy dynamicznej.
// systemy_Lab_02e.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
double* rozlokuj_wektor(int n);
int _tmain(int argc, _TCHAR* argv[])
{
int n;
cout << "Okresl liczbe elemntow wektora n = "; cin >> n;
Laboratorium 2
3
M.A. Jankowska, G. Sypniewska-Kamińska double* w;
w = rozlokuj_wektor(n);
for (int i = 0; i<n; i++)
{
w[i] = pow(static_cast<double>(i), 1.0/3.0); cout <<i<<" : "<< w[i] <<endl;
}
delete [] w;
return 0;
}
double * rozlokuj_wektor(int n)
{
double* ptab = new double[n];
return ptab;
}
ZADANIA
1. Napisz i uruchom program wywołujący funkcję, która przydziela pamięć dwuwymiarowej tablicy dynamicznej.
// systemy_Lab_02f.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
int ** rozlokuj_macierz(int& iw, int& ik); void show_mac(int ** x, int iw, int ik); int _tmain(int argc, _TCHAR* argv[])
{
int **A;
int ir=0, ic=0;
A = rozlokuj_macierz(ir,ic);
srand(static_cast<int>(time(0)));
for(int i = 0; i<ir; i++)
{
for (int k = 0; k<ic; k++)
{
A[i][k]=static_cast<int>(rand()/double(RAND_MAX)*900+100);
}
}
show_mac(A, ir, ic);
for (int i = 0; i<ir;i++)
{
delete [] A[i];
}
delete A;
return 0;
}
int ** rozlokuj_macierz(int& iw, int& ik)
{
cout << "Okresl liczbe wierszy tablicy ? "; cin >> iw;
cout << "Okresl liczbe kolumn tablicy ? "; cin >> ik;
int ** parray;
parray = new int* [iw];
for(int i = 0; i <iw; i++)
{
parray[i] = new int [ik];
}
return parray;
}
void show_mac(int ** x, int iw, int ik)
{
for (int i = 0; i<iw; i++)
{
for (int j = 0; j<ik;j++)
{
cout << x[i][j]<<setw(6);
}
Laboratorium 2
4
M.A. Jankowska, G. Sypniewska-Kamińska cout << endl;
}
}
2. Zmodyfikuj oba ostatnie programy w taki sposób, aby wywoływały funkcje których zadaniem jest zwolnienie pamięci zajmowanej przez jednowymiarową oraz tablicę dwuwymiarową.
// systemy_Lab_02g.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
int ** rozlokuj_macierz(int& iw, int& ik); void show_mac(int ** x, int iw, int ik); void zwolinij_pamiec(int iw, int ** parray); int main(int argc, _TCHAR* argv[])
{
int **A;
int ir=0, ic=0;
A = rozlokuj_macierz(ir,ic);
srand(static_cast<int>(time(0)));
for(int i = 0; i<ir; i++)
{
for (int k = 0; k<ic; k++)
{
A[i][k]=static_cast<int>(rand()/double(RAND_MAX)*900+100);
}
}
show_mac(A, ir, ic);
zwolinij_pamiec( ir, A);
return 0;
}
int ** rozlokuj_macierz(int& iw, int& ik)
{
cout << "Okresl liczbe wierszy tablicy ? "; cin >> iw;
cout << "Okresl liczbe kolumn tablicy ? "; cin >> ik;
int ** parray;
parray = new int* [iw];
for(int i = 0; i <iw; i++)
{
parray[i] = new int [ik];
}
return parray;
}
void show_mac(int ** x, int iw, int ik)
// tablica jest przekazana przez wskaznik
{
for (int i = 0; i<iw; i++)
{
for (int j = 0; j<ik;j++)
{
cout << x[i][j]<<setw(6);
}
cout << endl;
}
}
void zwolinij_pamiec(int iw, int ** parray)
{
for (int i = 0; i<iw;i++)
{
delete [] parray[i];
}
delete parray;
}
Laboratorium 2
5