Pagina informaticii

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

Test la metoda Greedy

Rândul 1

1. Se citesc două numere naturale n şi m (n >= m), apoi se citeşte un şir de n numere întregi. Să se determine o submulţime de m elemente din şir cu proprietatea că suma elementelor din mulţime este maxim. De exemplu, pentru n = 6, m = 3 şi şirul de numere 5, –3, 12, 8, 1, 2, soluţia este mulţimea {5, 12, 8}.

2. Se citesc n intervale de forma [ai, bi], i = 1..n, unde capetele intervalelor sunt numere naturale. Considerăm că putem elimina un interval dacă este inclus într-un alt interval. Să se elimine un număr maxim de intervale. De exemplu, pentru n=5 şi intervalele [2, 10], [3, 7], [8, 10], [11, 20], [14, 17], putem elimina intervalele [3, 7], [8, 10], [14, 17].

Rândul 2

1. Se citeşte un şir de n numere întregi. Să se aleagă din şir un număr maxim de elemente astfel încât produsul lor să fie maxim. De exemplu, pentru n = 5 şi şirul 3, –4, 2, –5, –8 se vor alege 3, 2, –5, –8.

2. Se citesc n intervale de forma [ai, bi), i = 1..n, unde capetele intervalelor sunt numere naturale. Să se aleagă un număr maxim de intervale astfel încât oricare două intervale alese să nu se intersecteze. De exemplu, pentru n=6 şi intervalele [8, 10), [2, 20), [4, 8), [12, 16), [3, 18), [17, 18) se aleg intervalele [4, 8), [8, 10), [12, 16), [17, 18)

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 =