Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Metoda Greedy

Test de progres – metoda Greedy

Se acordă 1 punct din oficiu

1. (3 puncte) Se consideră un vector a de n numere întregi şi o valoare întreagă x. Să se scrie o secvenţă optimă care elimină din vector toate valorile egale cu x. Se va afişa apoi vectorul rezultat. Menţionaţi idea de rezolvare şi complexitatea algoritmului utilizat.

2. (3 puncte) Se consideră un şir de n (n <= 1000) valori naturale. Utilizând un algoritm de tip Greedy, partiţionaţi şirul în două submulţimi care au proprietatea că diferenţa absolută a sumelor elementelor lor este minimă. Pentru şirul n=4 şi valorile 3, 19, 17, 1, se va afişa 3, 17 şi 1, 19. Precizaţi ideea de rezolvare şi complexitatea algoritmului. Conduce algoritmul Greedy la soluţia optimă? Dacă nu, menţionaţi o modalitate de rezolvare corectă.

3. (3 puncte) Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă. Să se determine o submulţime cu număr maxim de noduri cu proprietatea că oricare două noduri nu sunt adiacente. Precizaţi ideea de rezolvare şi complexitatea algoritmului. Conduce algoritmul Greedy la soluţia optimă? Dacă nu, menţionaţi o modalitate de rezolvare corectă.

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =