Teza nr 8

  • Timp de lucru 2 ore.
  • Toate subiectele sunt obligatorii și se acordă un 10 puncte din oficiu.

30 p Partea I

4p 1.Precizaţi care vor fi elementele matricii a după execuţia secvenţei de mai jos, pentru x=1, m=4, n=3 si a={{1,2,3}, {4,5,6}, {7,8,9}, {10,11,12}} ?

for (i=x+1; i<=m-1; i++)

for (j=0; j<=n-1; j++)

a {i-1}{j} = a [i][j];

4p 2.Precizaţi care va fi matricea a în urma execuţiei secvenţei de program:

n=3;

for (i=0; i<n; i++)           a [i][i]=0;

for(i=0; i<n; i++)

for (j=i+1; j<n; j++)

{ a [i][j]=1; a[j][i]= -1;}

4p 3.Se considera cele 2 secvente de program urmatoare, în care a este o matrice cu m linii * n coloane, iar x este o variabila de tip întreg. Precizati ce valori va avea matricea a pentru x=1, m=3, n=4, a[][]={{1,2,3,4}, {5,6,7,8}, {9,10,11,12}} în cele 2 variante:

//secventa S1                                          // secventa S2

for (j=x+1; j<=n-1; j++)                            for (j=n-1; j>=x+1; j–)

for (i=0; i<=m-1; i++)                                 for (i=m-1; i>=0; i–)

a [i][j-1] = a [i][j];                                         a [i][j-1] = a [i][j];

4p 4.Transformaţi din zecimal în binar numarul 158 şi prezentaţi modul de verificare a calculului .

4p 5.Scrieţi un program care să determine valoarea lui x din cadrul funcţiei:

f(x) =       3x+5 daca x Î (-∞,3)

x       daca x Î [3,6]

x2 – 3 daca x Î(6, +∞)

4p 6.Cunoscând laturile a,b,c ale unui triunghi ABC, să se afişeze S -aria sa.

4p 7.Fie ABC un triunghi cu unghiul a de 900 . Daca se cunoaste AB si BC, să se afişeze înălţimea şi aria sa.

2p 8. În secvenţa de instrucţiuni de mai jos, variabila s memorează un şir de caractere format doar din litere ale alfabetului englez, iar variabilele i şi n sunt de tip int. Ştiind că în urma executării secvenţei s-a afişat succesiunea de caractere eied*eael* scrieţi care este şirul de caractere memorat de variabila s.

n=strlen(s);

for(i=0;i<n;i++)

if (s[i]==’e’) cout<<’*’;

else cout<<‘e'<<s[i];

 

30p   Partea a II – a

4p 1.Utilizând metoda backtracking pentru afişarea tuturor modalităţilor de descompunere a unui număr natural ca o sumă de numere naturale nenule, pentru n=3 se obţin, în ordine, soluţiile: 1+1+1; 1+2; 2+1; 3. Ordinea de scriere a termenilor dintr- descompunere este semnificativă. Folosind aceeaşi metodă pentru n=10, care este soluţia generată imediat după 1+1+3+5 ?

a) 1 + 1 + 4 + 1 + 1 + 1 + 1

b)   1 + 1 + 7+1

c)   1 + 2+7

d)   1+1+1+4

4p 2.Trei băieţi A, B şi C, şi trei fete D, E şi F, trebuie sa formeze o echipă de trei copii, care să participe la un concurs. Echipa trebuie să fie mixtă (adică să conţină cel puţin o fată şi cel puţin un băiat). Ordinea copiilor în echipă este importantă deoarece aceasta va fi ordinea de intrare a copiilor în concurs (de exemplu echipa A, B, D este diferită de echipa B, A, D) . În câte dintre echipele formate se găsesc atât băiatul A cât şi băiatul B ?

 

3p 3.Se generează, utilizând metoda Backtracking, toate sirurile de trei note muzicale din multimea {DO, RE, MI, FA, SOL, LA, SI}. Orice notă poate să nu apară sau se poate repeta în cadrul unui şir.

Fie şirurile: 1) DO DO SI; 2) DO RE SOL; 3) DO RE RE; 4) DO RE Mi; 5) DO RE FA; 6) DO RE DO. Care este perechea de şiruri care trebuie schimbate între ele pentru ca succesiunea să fie corectă?

a) 1 şi 6

b) 2 şi 6

c) 2 şi 3

d) 5 şi 6

 

4p 4.La un concurs sunt prezentate cinci melodii notate A, B, C, D si E. Utilizand metoda Backtracking, se genereaza toate posibilitatile de a le prezenta, stiind ca melodia B va fi interpretata înaintea melodiei A.

Algoritmul utilizat este asemănator algoritmului de generare a:

a) aranjamentelor

b) submulțimilor

c) produsului cartezian

d) combinarilor

 

4p 5.Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca sumă a cel puţin două numere naturale nenule. Termenii fiecărei sume sunt în ordine crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+4, 1+5, 2+2 + 2,2 + 4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea lui 9. Câte soluţii de forma 2+ .. . vor fi generate ?

a) două

b) trei

c) patru

d) cinci

4p 6.Folosind modelul combinărilor, se generează numerele naturale cu câte trei cifre distincte din mulţimea {1,2,3,4}, numere cu cifrele în ordine strict crescătoare, obţinându-se, în ordine: 123, 124, 134, 234. Dacă se utilizează exact aceeaşi tehnică pentru a genera numerele naturale cu câte patru cifre distincte din mulţimea {1,2,3,4,5}, câte dintre numerele generate au prima cifră 1 şi ultima cifră 5 ?

3p 7.Problema generării tuturor numerelor de n cifre, folosind doar cifrele 1, 5 şi 7, este echivalentă cu problema:

a)generării produsului cartezian a 3 mulţimi cu câte n elemente fiecare;

b)generării aranjamentelor de n elemente luate cate 3;

c)generării produsului cartezian a n mulţimi cu câte 3 elemente fiecare;

d)generării combinărilor de n elemente luate câte 3.

 

4p 8.Există pânză de şase culori: alb, galben, roşu, verde, albastru și negru. Sunt afișate toate drapelele tricolore care pot fi confecţionate, ştiind că s-au respectat regulile:

– orice drapel are culoarea din mijloc galben sau verde;

– culorile de pe un drapel sunt distincte.

Care este drapelul următor tricolorului: albastru verde negru?

a) albastru verde negru;

b) albastru galben alb;

c) negru verde alb;

d) negru galben alb

 

30p Partea a III- a

5p 1.Scrieţă un program C++ complet care rezolvă următoarea problemă: Fiind dată o matrice A (n x n) cu elemente numere naturale citită de la tastatură, se cere să se determine cea mai mare sumă a n valori, luate din linii şi coloane diferite. Dimensiunile matricei şi elementele acesteia vor fi citite de la tastatură.

Exemplu.  Pentru n=3 şi matricea  A

1   3   4

9   12   5

6   1   17                 suma maximă este 29(=3+9+17).

 

5p 2.Prezentaţi pe scurt soluţia de backtracking în plan a problemei umplerii tablei de şah de dimensiuni n x n cu pasul calului(deplasarea se face în cele 8 poziţii vecine conform deplasării calului pe tabla de şah).

Descrierea va respecta următoarele cerinţe:

a)Precizaţi: codificarea datelor, condiţii interne, condiţia de terminare

b) Scrieţi implementarea completă a procedurii Back_plan şi descrieţi elementele componente în termeni de backtracking.

 

5p 3.Scrieţă un program C++ complet care rezolvă următoarea problemă: Să se genereze toate matricile binare (valorile din matrice sunt elemente de 0 şi 1) de ordinul n cu proprietatea că există o singură valoare de 1 în fiecare linie şi coloană a matricei. Dimensiunea matricei este citită de la tastatură.

Exemplu: pentru n=3 se vor afişa                 1 0 0       1 0 0       0 1 0       0 1 0       0 0 1       0 0 1

0 1 0       0 0 1       1 0 0       0 0 1       1 0 0       0 1 0

0 0 1       0 1 0       0 0 1       1 0 0       0 1 0       1 0 0

 

5p 4.Prezentaţi pe scurt soluţia de backtracking în plan a problemei ieşirii dintr-un labirint codificat printr-o matrice de 0 şi 1, în care 0 este zid, iar 1 zonă de trecere. Deplasarea în labirint se face ortogonal.

Descrierea va respecta următoarele cerinţe:

a) Precizaţi: codificarea datelor, condiţii interne, condiţia de terminare

b) Scrieţi implementarea completă a procedurii Back_plan şi descrieţi elementele componente în termeni de backtracking.

12+10=22p

4p 5.Scrieţă un program Pascal complet care rezolvă următoarea problemă: Să se afişeze toate modalităţile de aşezarea a n regine pe o tablă de şah de dimensiuni n x n astfel încât să nu se atace între ele. Două regine se atacă între ele dacă sunt plasate pe aceeaşi linie, coloană sau diagonală a tablei. Dimensiunea tablei este citită de la tastatură. Soluţia va fi afişată bidimensional, cu R pentru o poziţie în care este plasată o regină şi # pentru toate celelalte poziţii.

Exemplu: pentru n=4 o soluţie(nu singura) este:              #R##

###R

R###

R#

4p 6.Prezentaţi pe scurt soluţia de backtracking în plan a problemei numărării obiectelor dintr-o fotografie codificată printr-o matrice de 0 şi 1(1 este un punct aparţinând unui obiect, iar 0 codifică spaţiul dintre obiecte. Două elemente 1 fac parte din acelaşi obiect dacă se învecinează pe linie coloană sau diagonală).

Descrierea va respecta următoarele cerinţe:

a)Precizaţi: codificarea datelor, condiţii interne, condiţia de terminare

b) Scrieţi implementarea completă a procedurii Back_plan şi descrieţi elementele componente în termeni de backtracking.

3p 7.Scrieti functii corespunzatoare urmatoarelor cerinte:

a) eliminarea cifrelor nule ale unui nr. natural cu max. 9 cifre

b) afisati cifrele comune a 2 nr. naturale

c) afisarea unui cuvant in limbaj pasaresc

d) numararea cuvintelor dintr-un text care incep si se termina cu aceeasi vocala

3p 8.Scrieti functii corespunzatoare urmatoarelor cerinte:

a) verificati daca un nr. contine numai cifre pare.

b) inlocuiti literele mari cu litere mici si invers intr-un cuvant dat

c) numararea literelor distincte dintr-un cuvant

d) afisarea cuvintelor de pe pozitii impare dintr-un text

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s