Teste de informatică pentru liceu, articole C#, C/C++, PHP
Notă: Se acordă 1 punct din oficiu. Veţi rezolva fie subiectele 1, 2 (pentru nota 9), fie subiectele 1, 3 (pentru nota 10)
Rândul 1
1. (4 puncte) Scrieţi un program care generează aleator n numere întregi şi ordonează crescător cele n numere utilizând Quicksort (sortarea rapidă).
2. (4 puncte) Se citesc un număr natural S şi un şir de n numere naturale a = a1, a2, ..., an. Să se genereze toate posibilităţile de a-l scrie pe S ca sumă de numere din şir. Fiecare număr va intra o singură dată în sumă.
Exemplu:
S = 10, n = 5 şi a = 5, 7, 3, 2, 1
Două soluţii sunt: 5 + 3 + 2 şi 7 + 3
3. (5 puncte) Se consideră două cuvinte a şi b şi o listă având n cuvinte. Se doreşte transformarea cuvântului a în b, trecând prin cuvinte intermediare, existente în lista dată. Trecerea dintr-un cuvânt în altul se poate face folosind următoarele operaţii: schimbarea, adăugarea sau ştergerea unui singur caracter. Găsiţi cea mai scurtă secvenţă de operaţii care transformă primul cuvânt în cel de-al doilea folosind operaţiile permise. Cuvintele sunt formate numai din litere mici.
Exemplu:
a = “car” , b = “mare”, lista L = (cer, cerc, mar, rosu, inrosit, mere, cart, cere)
Cea mai scurtă soluţie: car, mar, mare
Rândul 2
1. (4 puncte) Scrieţi un program care generează aleator n numere întregi şi ordonează crescător cele n numere utilizând Mergesort (sortarea prin interclasare).
2. (4 puncte) Se citeşte un număr natural n. Să se genereze toate submulţimile mulţimii {1,2,...,n}. De exemplu, pentru n=3, se va afişa (nu neapărat în această ordine): {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
3. (5 puncte) Se consideră două cuvinte a şi b şi o listă având n cuvinte. Se doreşte transformarea cuvântului a în b, trecând prin cuvinte intermediare, existente în lista dată. Trecerea dintr-un cuvânt în altul se poate face folosind următoarele operaţii: schimbarea, adăugarea sau ştergerea unui singur caracter. Găsiţi cea mai scurtă secvenţă de operaţii care transformă primul cuvânt în cel de-al doilea folosind operaţiile permise. Cuvintele sunt formate numai din litere mici.
Exemplu:
a = “car” , b = “mare”, lista L = (cer, cerc, mar, rosu, inrosit, mere, cart, cere)
Cea mai scurtă soluţie: car, mar, mare
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ă