Clasa VII/VIII lecția 10 - 25 nov 2014

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

Probleme cu analiză amortizată

Problema unific

Problema unific a fost dată la OJI 2013 clasa a 7-a. Problema definește o procedură prin care două numere pot fi unificate, dacă au măcar o cifră în comun. Apoi cere să se aplice pe un vector unificări de elemente adiacente pînă ce nu se mai poate unifica nimic. Întotdeauna se va face prima unificare posibilă de la începutul vectorului.

O idee simplă este să parcurgem vectorul de numere și pentru fiecare număr nou să îl unificăm cu el din-nainte, apoi rezultatul cu cel din-nainte și tot așa pînă ce nu mai putem unifica. Apoi citim următorul număr. Ce complexitate are această soluție? La prima vedere un număr nou poate fi unificat de cel mult n ori, ceea ce duce la o complexitate pătratică. Desigur că nu e așa. Deoarece fiecare număr poate fi adăugat o singură dată și scos o singură dată (prin unificare) rezultă că numărul de operații este maxim 2n. Analiza amortizată ne spune că soluția este liniară.

O parte grea este unificarea propriu zisă. Deși algoritmul este clar, implementarea dă suficiente bătăi de cap, așa încît mulți elevi au greșit-o.

Problema skyline

Problema skyline este o problemă clasică. Cere să se găsească dreptunghiul de arie maximă într-un skyline, unde un skyline este linia lăsata de zgîrie-nori. Cu alte cuvinte o secvență de dreptunghiuri aliniate cu axa Ox.

Rezolvarea folosește o stivă, similar cu problema Clădiri. Vom memora o stivă de dreptunghiuri de înălțimi din ce în ce mai mari. Cînd adăugăm un dreptunghi de înălțime h vom închide toate dreptunghiurile de înălțime mai mare de pe stivă, avînd grijă să le înlocuim cu un dreptunghi egal cu suma lungimilor lor și de înălțime egală cu h.

Complexitatea este O(n) prin analiză amortizată și O(n) memorie.

Temă

Clasa a 7-a

Clasa a 8-a

Tema 10 clasa a 8a

Rezolvări aici [2]