SDA Lucrarea 2 Backup: Diferență între versiuni
De la WikiLabs
Jump to navigationJump to search
| Linia 15: | Linia 15: | ||
Pașii de rezolvare a unei probleme folosind ''Divide-et-impere'': | 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 î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>'''. | # Se rezolvă problemele '''P<sub>a</sub>''' și '''P<sub>b</sub>''' (folosind eventual același algoritm) și se 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'''. | # '''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 se 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.
