[C++, programare dinamică] Problema înmulțirii optime a matricelor

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Se dau N matrice, considerate cu elemente numere reale, identificate printr-un vector de dimensiuni D. Astfel, matricea 1 ≤ i ≤ N are dimensiunea (D[i – 1], D[i]). Se cere găsirea numărului minim de înmulțiri scalare necesare pentru calcularea produsului celor N matrice. FișierulContinuă lectura „[C++, programare dinamică] Problema înmulțirii optime a matricelor”

[C++, programare dinamică] Problema submatricei de sumă maximă pe R

Problema este de la finalul acestei pagini (fragment din carte). c) Se dă o matrice și se cere determinarea unui dreptunghi de sumă maximă. Ultimul algoritm prezentat poate fi extins pentru rezolvarea problemei în O(N3). Cum? Ultimul algoritmul prezentat în pagina de la linkul de mai sus este: maximul global este inițial primul număr. suma maximăContinuă lectura „[C++, programare dinamică] Problema submatricei de sumă maximă pe R”

[C++, programare dinamică] Problema subsecvenței de produs maxim pe R

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Enunțul problemei b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative). Pentru două rezolvări care se aplică doarContinuă lectura „[C++, programare dinamică] Problema subsecvenței de produs maxim pe R”

[C++, programare dinamică] Problema celui mai lung subșir comun

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Se dau două șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Se cere găsirea unui șir de caractere C de lungime maximă care este subșir atât a lui A cât și a lui B. Șirurile A și B seContinuă lectura „[C++, programare dinamică] Problema celui mai lung subșir comun”

[C++, programare dinamică] Problema subșirului crescător maximal

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Considerăm un vector A cu N elemente numere întregi. Un subșir a lui A este o secvență de elemente nu neapărat consecutive ale lui A, dar a căror ordine relativă în A este păstrată. Un subșir crescător al lui A este un subșir alContinuă lectura „[C++, programare dinamică] Problema subșirului crescător maximal”

[C++, programare dinamică] Problema subsecvenței de produs maxim

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Enunțul problemei b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative). Rezolvarea completă Este aici. Mai jos suntContinuă lectura „[C++, programare dinamică] Problema subsecvenței de produs maxim”

[C++, programare dinamică] Problema subsecvenței de sumă maximă

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Considerăm un număr natural N și un vector A cu N elemente numere întregi. O subsecvență [st, dr] a vectorului A reprezintă suma tuturor elementelor acelei subsecvențe. Se cere determinarea unei subsecvențe de sumă maximă. Datele de intrare se citesc din fișierul subsecv.in, iarContinuă lectura „[C++, programare dinamică] Problema subsecvenței de sumă maximă”

[C++, programare dinamică] Subsecvența de sumă maximă – aflarea pozițiilor de început și sfârșit din cei doi vectori, nerecursiv

Aceasta este o continuare la articolul de la acest link. Aici nu se scrie în fișier ci pe ecran. Vizual Rezolvare #include <iostream>using namespace std;void subsecv(int A[], int S[], int n, int &st, int &sf){ sf = -1; int max = -(1 << 30); // -infinit for (int i = 1; i <= n; ++i)Continuă lectura „[C++, programare dinamică] Subsecvența de sumă maximă – aflarea pozițiilor de început și sfârșit din cei doi vectori, nerecursiv”

[C++, programare dinamică] Problemă – algoritmul lui Lee (c) – afișarea tuturor drumurilor optime

Introducere în problema labirintului aici. Enunț c) Modificați funcția de afișare a drumului astfel încât să afișeze toate drumurile minime existente. Explicație Cum se cere modificarea funcției existente, nu crearea unei noi funcții, există opțiunea de a transforma funcția din recursivă în nerecursivă și de a folosi un arbore (fiecare nod al arborelui are celContinuă lectura „[C++, programare dinamică] Problemă – algoritmul lui Lee (c) – afișarea tuturor drumurilor optime”

[C++, programare dinamică] Problema labirintului – algoritmul lui Lee

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Am prezentat problema labirintului în cadrul secțiunii despre backtracking. Similar, se dă o matrice pătratică de dimensiune N, cu valori de 0 sau de 1, codificând un labirint. Valoarea 0 reprezintă o cameră deschisă, iar valoarea unu o cameră închisă. Se cere de dataContinuă lectura „[C++, programare dinamică] Problema labirintului – algoritmul lui Lee”