[C++, programare dinamică] Problemă cu algoritmul lui Lee (b)

Introducere în problema labirintului aici. Enunț b) Dați un exemplu pe care soluția recursivă efectuează cu mult mai mulți pași decât e necesar. Explicație Soluția recursivă efectuează mai mulți pași decât soluția nerecursivă cu cât se fac mai multe apeluri recursive pentru poziții deja calculate, ceea ce echivalează cu cât există mai multe poziții înContinuă lectura „[C++, programare dinamică] Problemă cu algoritmul lui Lee (b)”

[C++, programare dinamică] Problemă cu algoritmul lui Lee (a)

Introducere în problema labirintului aici. Enunț a) Considerăm că o persoană pornește din (1, 1) și alta din (N, N). Cele două persoane se mișcă exact în același timp. Scrieți un program care determină coordonatele spre care acestea ar trebui să se îndrepte pentru a se întâlni cât mai rapid. Rezolvare #include <fstream>#include <queue>#include <utility>usingContinuă lectura „[C++, programare dinamică] Problemă cu algoritmul lui Lee (a)”

[C++, programare dinamică] Distanța Levenshtein

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. Asupra șirului A putem face următoarele trei operații: 1. Inserăm un caracter.2. Ștergem un caracter.3. Înlocuim un caracter cu orice alt caracter din alfabetul folosit. Se cere determinarea număruluiContinuă lectura „[C++, programare dinamică] Distanța Levenshtein”

[C++, programare dinamică] Numărul de numere de N cifre cu produsul cifrelor 0

Dându-se N, scrieți un program care determină câte numere de N cifre cu produsul cifrelor 0 există. ·        N este numărul de cifre ale numerelor cerute Fiindcă sunt în discuție numere în baza 10, rezultatul este întotdeauna 0 dacă produsul este mai mare decât 9N, 9 fiind cea mai mare cifră în baza 10. PentruContinuă lectura „[C++, programare dinamică] Numărul de numere de N cifre cu produsul cifrelor 0”

[C++, programare dinamică] Suma unor dreptunghiuri ale unei matrice

Enunț: Scrieți un program care răspunde eficient la mai multe interogări privind suma unor dreptunghiuri ale unei matrice. Se noteaza matricea data cu A, cu indici pornind de la i = 1 pana la H, cu j = 1 pana la W. Fie dreptunghiul a cărui sumă o căutăm cu atributele w, h, i (sauContinuă lectura „[C++, programare dinamică] Suma unor dreptunghiuri ale unei matrice”

[C++, programare dinamică] Numărul de numere de N cifre cu suma cifrelor K

Enunțul problemei: Dându-se N și K, scrieți un program care determină câte numere de Ncifre cu suma cifrelor K există. Analog pentru produs. În acest articol rezolvăm varianta problemei care ține cont de suma cifrelor, nu de produs. În primul rând remarcăm că rezultatul este întotdeauna 0 dacă K > 9 * N. După stabilireaContinuă lectura „[C++, programare dinamică] Numărul de numere de N cifre cu suma cifrelor K”

[C++, algoritmică] Numărarea parantezărilor booleane

Teoria este din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Teorie Fişierul paran.in conţine pe prima linie un număr natural N. Pe a doua linie se află N valori booleane (0 sau 1), iar a treia linie conţine N – 1 valori din mulţimea {-1, -2, -3}, reprezentând operatorii and, or, respectiv xor.Continuă lectura „[C++, algoritmică] Numărarea parantezărilor booleane”

[C++, algoritmică] Distanța Levenshtein cu reconstrucția pașilor de editare

Enunțul problemei: Se dau 2 șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Asupra șirului A putem face trei operații: 1. inserăm, 2. ștergem, 3. înlocuim un caracter. Se cere determinarea numărului minim de operații necesare transformării șirului de caractere A în șirul de caractere B. Ca inspirație, cartea AlgoritmicaContinuă lectura „[C++, algoritmică] Distanța Levenshtein cu reconstrucția pașilor de editare”

[C++, programare dinamică] Subsecvența de sumă maximă – problema (a) – suma și pozițiile de început și sfârșit

Enunțul subproblemei: a) Modificați implementările date pentru a afișa și pozițiile de început și de sfârșit a unei subsecvențe de sumă maximă. Problemă extrasă din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo. Fișier intrare 10-6 1 -3 4 5 -1 3 -8 -9 1 Fișier ieșire 11 4 7 Codul sursă #include <fstream>using namespaceContinuă lectura „[C++, programare dinamică] Subsecvența de sumă maximă – problema (a) – suma și pozițiile de început și sfârșit”