Pagina informaticii

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

Teză semestrul II – Tehnici de programare

Rândul 1

1. (2 puncte) Utilizând metoda backtracking se generează lexicografic anagramele cuvântului caine. Ce anagrame trebuie eliminate din secvenţa de mai jos astfel încât cele rămase să reprezinte o succesiune corectă:
            1. ecian            2. ecina            3. ecain            4. ecani            5. ecnai            6. ecnia

a. 2
b. 2 şi 3
c. 5 şi 6
d. 3 şi 4

2. (3 puncte) Se consideră un şir de n numere naturale mai mici decât 30000. Folosind metoda backtracking, să se genereze toate subşirurile strict crescătoare de k numere care se pot forma începând cu primul element din şir. Fiecare subşir se va afişa pe câte o linie din fişierul subsiruri.txt.
De exemplu, pentru n=6, k=3 şi numerele 3, 10, 5, 6, 4, 9 se va afişa:
3 5 6
3 5 9
3 6 9
3 4 9
Se va scrie programul complet. Datele de intrare se citesc dintr-un fişier text. La începutul programului se vor preciza: lungimea stivei, valorile care se depun pe stivă, criteriul de validare.

3. (3 puncte) Se consideră o matrice având n linii şi n coloane (n <= 1000) care memorează numere naturale. Utilizând eventual tehnica pivotului pentru fiecare linie de sus în jos, să se scrie un program afişează ordinea lexicografică a coloanelor matricei.
De exemplu, pentru matricea
4  2  4  5  4
1  7  5  0  5
9  9  6  0  2
3  3  6  0  10
1  1  4  2  22
Se va afişa: 2, 1, 5, 3, 4, deoarece coloana minimă lexicografică este a doua, urmează prima etc.
Precizaţi complexitatea algoritmului utilizat. Atenţie, nu este neapărat necesar să efectuaţi interschimbări de coloane, acest lucru poate mări complexitatea.

Rândul 2

1. (2 puncte) Care este cea mai mică permutare din punct de vedere lexicografic a mulţimii {1,2,3,4,5,6,7} care are patru inversiuni:
a. {1, 2, 5, 3, 7, 6, 4}
b. {1, 2, 3, 5, 7, 6, 4}
c. {1, 2, 3, 5, 6, 7, 4}
d. {1, 2, 3, 5, 7, 4, 6}

2. (3 puncte) Se consideră un şir de n numere naturale a1, a2, ..., an şi un număr natural S. Folosind metoda backtracking, să se genereze toate posibilităţile de a-l scrie pe S ca sumă de termeni din şir ştiind că fiecare termen din şir poate să apară o singură dată în sumă. De exemplu, pentru S=10 şi şirul 3, 6, 7, 1, 10 se va afişa în fişierul sir.txt:
3 7
3 6 1
10
Se va scrie programul complet. Datele de intrare se citesc dintr-un fişier text. La începutul programului se vor preciza: lungimea stivei, valorile care se depun pe stivă, criteriul de validare.

3. (3 puncte) Se consideră o matrice având n linii şi n coloane (n <= 1000) care memorează numere naturale. Utilizând eventual tehnica pivotului pentru fiecare linie de sus în jos, să se scrie un program afişează ordinea lexicografică a coloanelor matricei.
De exemplu, pentru matricea
4  2  4  5  4
1  7  5  0  5
9  9  6  0  2
3  3  6  0  10
1  1  4  2  22
Se va afişa: 2, 1, 5, 3, 4, deoarece coloana minimă lexicografică este a doua, urmează prima etc.
Precizaţi complexitatea algoritmului utilizat. Atenţie, nu este neapărat necesar să efectuaţi interschimbări de coloane, acest lucru poate mări complexitatea.

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 =