Diferente pentru problema/lab-08-04 intre reviziile #12 si #13

Nu exista diferente intre titluri.

Diferente intre continut:

Să considerăm că am ales să rezolvăm problema în următorul mod: definim o matrice c de dimensiuni suficient de mari, în care elementul c[i][j] reprezintă valoarea C(i,j). Vom iniţializa linia 1 a matricei (C(1,0) = C(1,1) = 1) şi vom calcula, pe rând, aplicând relaţia de recurenţă, valorile C(i,j) până când am obţinut valoarea cerută de problemă: C(n,k).
Acest algoritm rezolvă problema, dar prezintă un dezavantaj. Pentru calculul unei valori, trebuie păstrată în memorie o matrice de dimensiuni relativ mari, care ocupă multă memorie. În plus, observăm că pentru a calcula C(i,j), care se va afla pe linia i în matrice, avem nevoie doar de valori de pe linia i-1. Astfel, putem aduce o economie de memorie majoră în program dacă în loc să păstrăm întreaga matrice în memorie, păstrăm doar doi vectori vim1[] şi vi[] care să reprezinte liniile i-1, respectiv i din matrice.
Acest algoritm rezolvă problema, dar prezintă un dezavantaj. Pentru calculul unei valori, trebuie păstrată în memorie o matrice de dimensiuni relativ mari, care ocupă multă memorie. În plus, observăm că pentru a calcula C(i,j), care se va afla pe linia i în matrice, avem nevoie doar de valori de pe linia i-1. Astfel, putem aduce o economie de memorie majoră în program dacă în loc să păstrăm întreaga matrice în memorie, păstrăm doar doi vectori vim1 şi vi care să reprezinte liniile i-1, respectiv i din matrice.
Avem acum două optiuni:
* După terminarea calulului valorilor de pe o linie, în vectorul vi[], putem să le copiem pe toate în vectorul vim1[] şi să continuăm calculul următoarei linii în vi[]. Această metodă, însă, presupune ca după fiecare linie să copiem "n" elemente dintr-un vector în altul, şi introduce un cost de eficienţă inutil (ceea ce am economisit la capitolul memorie, irosim la capitolul rapiditate a programului).
* Metoda mai rapidă şi mai elegantă este ca, în loc să copiem conţinutul lui vi[] în vim1[], să interschimbăm doar variabilele de tip pointer care indică către începutul acestor şiruri. Altfel spus, nu mutăm efectiv valorile prin memorie, ci doar le interschimbăm "rolul". În acest mod, se efectuează în loc de mutarea a "n" elemente, doar cele trei instrucţiuni ale interschimbării de variabilă.
* După terminarea calculului valorilor de pe o linie, în vectorul vi, putem să le copiem pe toate în vectorul vim1 şi să continuăm calculul următoarei linii în vi. Această metodă, însă, presupune ca după fiecare linie să copiem "n" elemente dintr-un vector în altul, şi introduce un cost de eficienţă inutil (ceea ce am economisit la capitolul memorie, irosim la capitolul rapiditate a programului).
* Metoda mai rapidă şi mai elegantă este ca, în loc să copiem conţinutul lui vi în vim1, să interschimbăm doar variabilele de tip pointer care indică către începutul acestor şiruri. Altfel spus, nu mutăm efectiv valorile prin memorie, ci doar le interschimbăm "rolul". În acest mod, se efectuează în loc de mutarea a "n" elemente, doar cele trei instrucţiuni ale interschimbării de variabilă pointer.
Să se scrie un program care calculează valoarea lui C(n,k) prin metoda descrisă mai sus, reducând matricea la doi vectori, şi schimbând după fiecare pas, rolul jucat de aceşti doi vectori.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.