Pagina informaticii

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

Teză clasa a XI-a – Tehnici de programare

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 cu­vântului a în b, trecând prin cuvinte in­ter­me­diare, 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 cu­vântului a în b, trecând prin cuvinte in­ter­me­diare, 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

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 =