Laboratorium nr 12
Temat: Funkcje zaprzyjaźnione i wstęp do algorytmów programowania. Algorytm rekurencji.
1. Funkcje zaprzyjaźnione
W przypadku istnienie w deklaracji klasy zmiennych typu private, dostęp do nich jest ograniczony
do danego obiektu, wynika to z faktu, że w C++ jednostką chronioną przed niepowołanym dostępem jest
klasa, a nie obiekt. Oznacza to, że funkcja składowa danej klasy może używać wszystkich składowych
prywatnych dowolnego obiektu tej samej klasy. Natomiast do składowych prywatnych jakiegoś obiektu
nie ma dostępu funkcja innej klasy, ani jakakolwiek funkcja niezależna. Rozwiązaniem tego problemu
jest zastosowanie funkcji zaprzyjaźnionych. Funkcja zaprzyjaźniona posiada dostęp do prywatnych
danych obiektu lub obiektów danej klasy. Deklaracja:
class klasa {
private:
typ dana;
public:
…
friend typ funkcja (np. const class klasa &);
}
!argumentem funkcji jest najczęściej referencja do obiektu danej klasy
Uwaga:
C++ pozwala na domyślne przekazywanie parametrów przez referencję, a nie wartość. Oznacza to,
że pomimo wywołania funkcji z pewnymi argumentami, a nie wskaźnikami, argumenty te będą
automatycznie przekazywane przez referencję. W tym celu, należy jedynie w deklaracji funkcji
poprzedzić argument operatorem & - funkcja ta będzie wówczas działać w stylu języka, w którym
parametry są przekazywane przez referencję, np.
friend klasa * funkcja (const class klasa &);
2. Algorytmy programowania. Algorytm rekurencji.
Algorytmem lub algorytmem programowania nazywamy taki tok postępowania, który prowadzi
do rozwiązanie określonego zadania . Dobry algorytm charakteryzuje się:
●
jednoznacznie zdefiniowaną procedurą pozwalającą na rozwiązanie zadanego problemu,,
●
wykorzystaniem odpowiednich struktur danych ,
●
minimalną ilością kroków prowadzących do rozwiązania, uniwersalnością i możliwością
wielokrotnego wykorzystania
Przykłady algorytmów programowania to: generator liczb pseudolosowych, rekurencja, sortowanie,
kompresja danych, itp.
Algorytm rekurencji
Rekurencję stosuje się w algorytmach rozwiązujących takie problemy, które można wykonać za
pomocą procedur uzyskanych dla prostszych problemów tej samej klasy, jak wyznaczenie wartości
funkcji silnia:
1
2
...
1
...
)!
2
(
)
1
(
)!
1
(
!
⋅
⋅
⋅
−
⋅
=
=
−
⋅
−
⋅
=
−
⋅
=
x
x
x
x
x
x
x
x
Rozwiązanie głównego problemu składa się z wyników cząstkowych, wyznaczanych przez podprogram
wykonywany rekurencyjnie. Taki naturalny zapis algorytmów wspierany jest poprzez mechanizm
wywołań rekurencyjnych – funkcja może zawierać wywołanie samej siebie.
Uwaga: taki sposób wykonywania programu charakteryzuje się:
●
przejrzystym zapisem algorytmu,
●
dużym zaangażowaniem pamięci i długim czasem wykonania
●
zastosowanie rekurencyjnego wywoływania funkcji przedstawiają poniższe przykłady służące do
określenia ograniczenia zastosowania rekurencji oraz obliczania wartości silni.
# include <stdio.h>
int zlicz(int i){
float tab[1000];
printf("\nKrok nr=%d",i);
zlicz(++i);
return i;
}
int main() {
zlicz(0);
return 0;
}
# include <stdio.h>
int silnia(int x) {
if (x==0) return 1;
else return x*silnia(x-1);
}
int main() {
int liczba;
printf("Podaj liczbe=");
scanf("%d",&liczba);
printf("\nSilnia(%d)=%d",liczba,silnia(liczba));
return 0;
}
Zadanie: Każde wywołanie funkcji zlicz(…) zajmuje na stosie pewną ilość miejsca. Kiedy miejsce na
stosie skończy się, aplikacja przerwie swoje działanie. Wyznaczyć liczbę kroków rekurencji w zależności
od wielkości tablicy tab[n] oraz oszacować rozmiar dostępnego stosu.
main.cpp
#include "klasa.h"
// funkcja friend
void wyswietl(rekord *obiekt){
if(obiekt!=NULL) {
cout<<obiekt->imie<<"\t";
cout<<obiekt->nazwisko<<"\t";
cout<<obiekt->telefon<<"\n";
wyswietl(obiekt=obiekt->nastepny);
}
else cout << "Koniec listy\n";
};
int main() {
class lista *baza;
baza=new lista();
baza->dodaj("Jan","Nowak","1");
baza->dodaj("Jan","Nowak","2");
baza->dodaj("Jan","Nowak","3");
wyswietl(baza->pierwszy);
return 0;
};
klasa.h
#include <iostream>
#include <string.h>
using namespace std;
class rekord {
private:
public:
char imie[10];
char nazwisko[25];
char telefon[10];
class rekord *nastepny;
rekord(char *i, char *n, char *t);
rekord();
};
class lista : public rekord {
public:
class rekord *pierwszy;
void dodaj(char *i,char *n,char *t);
lista(char *i="Imie", char
*n="Nazwisko", char *t="Telefon");
friend void wyswietl(rekord
*obiekt);
};
klasa.cpp
#include "klasa.h"
// klasa rekord
rekord::rekord(char *i, char *n, char *t){
strcpy(imie,i);
strcpy(nazwisko,n);
strcpy(telefon,t);
nastepny=NULL;
};
rekord::rekord(){
};
// klasa lista
void lista::dodaj(char *i,char *n,char *t){
class rekord *obiekt=this->pierwszy;
while (obiekt->nastepny!=NULL) {
obiekt=obiekt->nastepny;
};
obiekt->nastepny=new rekord;
strcpy(obiekt->nastepny->imie,i);
strcpy(obiekt->nastepny->nazwisko,n);
strcpy(obiekt->nastepny->telefon,t);
obiekt->nastepny->nastepny=NULL;
};
lista::lista(char *i,char *n,char *t)
:rekord(i,n,t) {
this->pierwszy=this;
};
3) Zadanie: Zmodyfikuj program bazy danych z poprzednich ćwiczeń tak, aby umożliwiał wyświetlania i
kasowania wszystkich danych w bazie w oparciu o funkcje zaprzyjaźnione i algorytm rekurencji.