Note de curs, probleme algoritmică, 20 ianuarie 2014
În acest curs am discutat problemele:
Binary Lexicographic Sequence
Cerință
Se iau în considerare toate secvențele de 0 și 1 de lugime N, care nu conțin două cifre de 1 consecutive. Se cere afișarea celei de-a K-a secvențe în ordine lexicografică.
Rezolvare
Inițial, va trebui să calculăm numărul de astfel de secvențe de o anumită lungime.
Secvențele de lungime 1 sunt în număr de 2:
0 1
Secvențele de lungime 2 sunt în număr de 3:
00 01 10
Secvențele de lungime 3 sunt în număr de 5:
000 001 010 100 101
Secvențele de lungime 4 sunt în număr de 8:
0000 0001 0010 0100 0101 1000 1001 1010
Se observă că secvențele de lungime L se pot obține din mulțimea secvențelor de lungime L - 1 (prin adăugarea cifrei 0 în fața fiecări secvențe) reunită cu mulțimea secvențelor de lungime L - 2 (prin adăugarea cifrelor 10 în fața fiecărei secvențe).
Astfel, putem calcula funcția:
F(L) = numărul de secvențe de lungime L F(1) = 2 F(2) = 3 F(L) = F(L - 1) + F(L - 2)
După calcularea valorilor funcției F putem determina forma celei de-a K-a secvență de lungime N.
Inițial, va trebui să determinăm dacă cea de-a K-a secvență de lungime N începe cu cifra 0 sau cu cifrele 10. Știind că secvențele care încep cu 0 sunt primele în ordine lexicografică și în număr de F(N - 1) putem deduce că:
K <= F(N - 1) <=> secvența începe cu 0 K > F(N - 1) <=> secvența începe cu 10
În continuare, va trebui să reducem problema la un caz mai simplu (secvențe de lungimi mai mici) și să determinăm restul secvenței după aceeași regulă până la final.
Binary Apple Tree
Cerință
Dându-se un arbore binar ponderat (cu costuri pe muchii), orientat (cu rădăcină fixată) cu N noduri, să se taie Q muchii ale sale, astfel încât suma muchiilor rămase să fie maximă (rădăcina nu poate fi tăiată).
Rezolvare
Problema se rezolvă prin programare dinamică (compunând soluțiile unor subprobleme ale problemei inițiale putem obține rezultatul acesteia).
Vom defini funcțiile:
cost(nod, fiu) = ponderea muchiei care unește nodurile nod și fiu
Muchii(nod) = numărul de muchii din subarborele definit de nodul nod
OptimFF(nod, taiat) = suma maximă posibilă a muchiilor din subarborele definit
de nodul nod, dacă din acesta se taie taiat muchii
și ambii săi subarbori complet
OptimTF(nod, taiat) = suma maximă posibilă a muchiilor din subarborele definit
de nodul nod, dacă din acesta se taie taiat muchii
și subarborele său drept complet
OptimFT(nod, taiat) = suma maximă posibilă a muchiilor din subarborele definit
de nodul nod, dacă din acesta se taie taiat muchii
și subarborele său stâng complet
OptimTT(nod, taiat) = suma maximă posibilă a muchiilor din subarborele definit
de nodul nod, dacă din acesta se taie taiat muchii
și niciunul din subarborii săi complet
Optim(nod, taiat) = suma maximă posibilă a muchiilor din subarborele definit
de nodul nod, dacă din acesta se taie taiat muchii
Acestea se vor calcula după următoarele formule:
Muchii(nod) = 0 , dacă nod nu are fii (este frunză)
= 2 + Muchii(fiuStang) + Muchii(fiuDrept), dacă nod are 2 fii
OptimFF(nod, taiat) = 0, taiat = Muchii(nod)
OptimFT(nod, taiat) = Optim(fiuDrept, taiatDreapta) + cost(nod, fiuDrept),
taiat = taiatDreapta + Muchii(fiuStanga) + 1
OptimTF(nod, taiat) = Optim(fiuStang, taiatStanga) + cost(nod, fiuStang),
taiat = taiatStanga + Muchii(fiuDreapta) + 1
OptimTT(nod, taiat) = min(Optim(fiuStang, taiatStanga) + cost(nod, fiuStang)
+ Optim(fiuDrept, taiatDreapta) + cost(nod, fiuDrept),
taiat = taiatStanga + 1 + taiatDreapta + 1)
Optim(nod, taiat) = min(OptimFF(nod, taiat), OptimFT(nod, taiat),
OptimTF(nod, taiat), OptimTT(nod, taiat))
Soluția problemei este:
Raspuns = Optim(radacina, Q), radacina = 1
Complexitate
Pentru a putea calcula răspunsul problemei, va trebui să calculăm funcția Optim pentru toate nodurile și toate numele de muchii tăiate între 0 și Q, așadar:
Complexitate spațiu: O(N * Q).
Pentru a putea calcula valoarea acestei funcții pentru o pereche de parametri avem nevoie de Q operații, așadar:
Complexitate timp: O(N * Q * Q).
