Indicați ce valoare afișează următorul pseudocod (unde mod reprezintă restul împărțirii întregi)?
n ← 20
┌pentru i ← 0, n execută
│ s[0][i] ← 0
│ s[i][0] ← 0
└■
┌pentru i ← 1, n execută
│ ┌pentru j ← 1, n execută
│ │ a[i][j] ← (i + j) mod 2
│ └■
└■
┌pentru i ← 1, n execută
│ ┌pentru j ← 1, n execută
│ │ s[i][j] ← a[i][j] + s[i-1][j] + s[i][j-1]
│ │ s[i][j] ← s[i][j] - s[i-1][j-1]
│ └■
└■
ans ← 0
┌pentru i ← 1, n execută
│ ans ← ans + s[i][i]
└■
scrie ans
- 2020
- 2026
- 1620
- 716
- 1430
- 2860
Matricea s este matricea sumelor parțiale ale lui a: s[i][j] este numărul de poziții (p,q) cu p≤i, q≤j și p+q impar. Pe diagonală, s[i][i] este 2i2 pentru i par și 2i2−1 pentru i impar, deci ans=21(i=1∑20i2−10)=22870−10=1430Pentru un arbore cu 10 noduri, numerotate de la 1 la 10, se dă vectorul de tați t=(0,1,1,2,2,3,3,x,y,z), unde t[i] reprezintă tatăl nodului i, iar valoarea 0 identifică nodul care este rădăcina arborelui.Care este valoarea maximă a sumei x+y+z pentru care vectorul de tați este valid și arborele are exact 5 frunze?
- 30
- 24
- 26
- 23
- 27
- 21
Nodurile x,y,z sunt tații nodurilor 8,9,10 și nu pot fi 0 (rădăcina este 1) sau chiar nodul însuși. Alegând x=y=10, nodul 10 devine tatăl lui 8 și 9, iar tatăl lui 10 nu poate fi 8 sau 9 (ar apărea un ciclu): cea mai mare valoare posibilă este z=7. Frunzele sunt atunci 4,5,6,8,9, adică exact 5, iar suma maximă este 10+10+7=27 (variante precum 9+10+7=26 dau mai puțin).Se consideră matricea M cu elemente numere întregi, cu n linii și n coloane, n≥2. Elementele lui M sunt generate cu următoarea formulă: Mi,j=i+j−n, cu 1≤i,j≤n.Care este suma elementelor de pe diagonala principală, Sp, respectiv suma elementelor de pe diagonala secundară, Ss?
- Sp=n, Ss=n
- Sp=0, Ss=n
- Sp=1, Ss=1
- Sp=n, Ss=0
- Sp=n2, Ss=0
- Sp=0, Ss=n2
Pe diagonala principală j=i, deci Mi,i=2i−n și Sp=2⋅2n(n+1)−n⋅n=n. Pe diagonala secundară j=n+1−i, deci Mi,n+1−i=i+(n+1−i)−n=1 pentru fiecare dintre cele n elemente și Ss=n.Fie grafurile neorientate: G1 cu 5 noduri și mulțimea muchiilor {(1,2),(2,3),(3,4),(4,5)} și G2 cu 6 noduri și mulțimea muchiilor {(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)}.Notăm cu M1 și M2 numărul maxim de muchii care pot fi adăugate în grafurile G1, respectiv G2, fără a elimina muchii, astfel încât grafurile rezultate să fie euleriene.Care este valoarea expresiei M1−M2?
- −2
- 0
- −1
- 1
- 2
- −3
Un graf este eulerian dacă este conex și toate gradele sunt pare. K5 are toate gradele egale cu 4, deci G1 se completează până la K5: M1=10−4=6. În G2 fiecare nod are gradul 2, iar muchiile adăugate trebuie să dea fiecărui nod un grad adăugat par, adică 0 sau 2 (în K6 gradul 5 ar fi impar): se pot adăuga cel mult 6⋅2/2=6 muchii, de exemplu cele două triunghiuri (1,3,5) și (2,4,6), deci M2=6 și M1−M2=0.Funcția recursivă f, dată în pseudocodul de mai jos, este apelată cu valorile n=9 și k=5. Câte apeluri se realizează în total luând în calcul și apelul inițial?
┌întreg f(întreg n, întreg k)
│ ┌dacă k < 0 sau k > n atunci
│ │ returnează 0
│ └■
│ ┌dacă k == 0 sau k == n atunci
│ │ returnează 1
│ └■
│ returnează f(n-1, k-1) + f(n-1, k)
└■
- 251
- 512
- 256
- 1023
- 126
- 521
Funcția calculează Cnk: se oprește cu valoarea 1 pentru k=0 sau k=n și altfel se desparte în două apeluri. Arborele apelurilor este deci binar plin, iar frunzele lui sunt toate apeluri care întorc 1, așa că sunt C95=126. Un arbore binar plin cu 126 de frunze are 2⋅126−1=251 de noduri, deci 251 de apeluri.