Diferență între revizuiri ale paginii „SDA Lucrarea 2 Backup”
De la WikiLabs
Jump to navigationJump to search| Linia 6: | Linia 6: | ||
= Funcțiile recursive - Clasa de algoritmi ''Divide-et-impera'' = | = Funcțiile recursive - Clasa de algoritmi ''Divide-et-impera'' = | ||
| + | |||
| + | Definirea și utilizarea funcțiilor recursive se pot recapitula citind [[PC Laborator 10]]. | ||
| + | |||
| + | == Divide-et-impera == | ||
| + | |||
| + | Clasa de algoritmi ''divide-et-impera'' se referă la algoritmii în care problema inițială se împarte în două probleme de același fel, în care datele de intrare nu se suprapun, se rezolvă aceste două subprobleme obținând două rezultate parțiale care apoi se combină pentru a obține rezultatul final. | ||
| + | |||
| + | Pașii de rezolvare a unei probleme folosind ''Divide-et-impere'': | ||
| + | # Se împarte problema inițială '''P''' (adică datele de intrare) în două probleme de același fel, '''P<sub>a</sub>''' și '''P<sub>b</sub>'''. În mod optim această împărțire se face exact la jumătate. | ||
| + | # Se rezolvă problemele '''P<sub>a</sub>''' și '''P<sub>b</sub>''' (folosind eventual același algoritm) și obțin două rezultate parțiale '''R<sub>a</sub>''' și '''R<sub>b</sub>'''. | ||
| + | # '''R<sub>a</sub>''' și '''R<sub>b</sub>''' se combină într-un mod care ține de aplicație și se obține rezultatul final '''R'''. | ||
Versiunea de la data 6 martie 2016 19:13
În acest laborator veți relua și recapitula noțiunile legate funcții recursive și citire și scriere din fișiere.
Utilizarea fișierelor in C
Pentru a recapitula modurile de scriere și citire din fișiere în limbajul C, puteți recapitula PC Laborator 13.
Funcțiile recursive - Clasa de algoritmi Divide-et-impera
Definirea și utilizarea funcțiilor recursive se pot recapitula citind PC Laborator 10.
Divide-et-impera
Clasa de algoritmi divide-et-impera se referă la algoritmii în care problema inițială se împarte în două probleme de același fel, în care datele de intrare nu se suprapun, se rezolvă aceste două subprobleme obținând două rezultate parțiale care apoi se combină pentru a obține rezultatul final.
Pașii de rezolvare a unei probleme folosind Divide-et-impere:
- Se împarte problema inițială P (adică datele de intrare) în două probleme de același fel, Pa și Pb. În mod optim această împărțire se face exact la jumătate.
- Se rezolvă problemele Pa și Pb (folosind eventual același algoritm) și obțin două rezultate parțiale Ra și Rb.
- Ra și Rb se combină într-un mod care ține de aplicație și se obține rezultatul final R.
