-
I. 1.
D. !( (u > t) || (t > u) )
I. 2.
a) 260
b) 11
c)
CAT TIMP x > 0 EXECUTA
x <- x - 2
cnt <- cnt + 1
x <- cnt
d)
#include <iostream>
using namespace std;
int F(int x, int y){
int acc = 0;
while(x != 0){
if(x % 2 == 1)
acc = acc + y;
x = x / 2;
y = y * 2;
}
return acc;
}
II. 1)
B. 1024
II. 2)
A. 45
3)
a) 66 - 60 - 58 - 56 - 57 - 56 - 57 - 56 - 57 -
56
b)
int find(int A[105][105], int n, int m, int L, int C){
int di[] = {-1 ,0, 1, 0};
int dj[] = {0, 1, 0, -1};
int a[105][105], M = -1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = 0;
struct P
{
int lin, col;
} q[n * m + 5];
int st = 1, dr = 1;
q[st].lin = L, q[st].col = C;
while(st <= dr){
int x = q[st].lin, y = q[st].col;
st++;
int diff_min = -1, diff, l, c, mi;
a[x][y]++;
if(a[x][y] == 2 && ( M == -1 || M > A[x][y] ) )
M = A[x][y];
for(int k = 0; k < 4; k++){
int iv = x + di[k], jv = y + dj[k];
if(iv >= 1 && iv <= n && jv >= 1 && jv <= m){
diff = abs(A[x][y] - A[iv][jv]);
if(diff_min == -1 || diff_min > diff)
mi = A[iv][jv], diff_min = diff, l = iv, c = jv;
else
if(diff_min == diff && mi > A[iv][jv])
mi = A[iv][jv], l = iv, c = jv;
}
}
if(a[l][c] != 2)
q[++dr].lin = l, q[dr].col = c;
}
return M;
}
II. 4)
a)
unsigned long long int value(char s[105]){
unsigned long long int v = 0;
for(int i = 0; i < strlen(s); i++){
int k = (int)(s[i]) - (int)('a');
if(v < 9)
v = v * 10 + k;
else
v = v * 100 + k;
}
return v;
}
b)
Functia value creeaza un numar format din toate cifrele de ordine ale caracterelor
ce formeaza cuvantul transmis ca parametru, urmat de numarul de caractere ale cuvantului
In acest mod ne putem asigura de faptul ca functia va returna un nr. unic pentru fiecare cuvant.
III. 1)
C. 12600
III. 2)
F(53) = 6
III. 3)
a)
int check(int n, int a[105][105]){
for(int p = 2; p <= n; p++){
int cnt = 0;
for(int i = 0; i <= p - 1; i++)
for(int j = 0; j < p - 1; j++)
if(a[i][j] == 1)
cnt++;
if(cnt != (2 * p - 2))
return 0;
}
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(a[i][j] == 0 && a[j][i] != 0)
return 0;
else
if(a[i][j] > 0 && a[j][i] != (a[i][j] + 1))
return 0;
for(int i = 0; i < n; i++){
int el = -1;
for(int j = 0; j < n; j++)
if(a[i][j]){
if(el == -1)
el = a[i][j];
else
if(el != a[i][j])
return 0;
}
}
return 1;
}
b)
Deoarece bool(a[i][j]) == bool(a[j][i]) putem
considera matricea data drept matricea unui graf
neorientat
Deoarece suma tuturor elementelor din matrice
este egala cu 2n - 2, o putem considera ca fiind
suma gradelor tuturor nodurilor ,
astfel avem n - 1 muchii, de aici deducem faptul
ca matricea data este matricea de adiacenta a
unui arbore
Daca arborele are minim 2 frunze, atunci acestea
vor reprezenta cele 2 linii cu un singur element
nenul.
Altfel matricea va fi practic o lista simplu
inlantuita, caz in care radacina si ultima
frunza vor reprezenta ce 2 linii
cu un singur element nenul.
c)
int sol[105], sz_s;
void dfs(int k, int st[105], int sz_st, int a[105][105], int n, int c[105]){
c[k] = 1;
if(sz_st > sz_s){
sz_s = sz_st;
for(int i = 1; i <= sz_st; i++)
sol[i] = st[i];
}
for(int x = 1; x <= n; x++)
if(a[k][x] > 0 && c[x] == 0){
st[++sz_st] = x;
dfs(x, st, sz_st, a, n, c);
sz_st--;
}
}
void find(int n, int a[105][105]){
int c[105], st[105], sz_st = 1;
for(int i = 1; i <= n; i++)
c[i] = 0;
st[sz_st] = 1;
dfs(1 ,st, sz_st, a, n, c);
cout<<'(';
for(int i = sz_s; i >= 1; i--){
cout<<sol[i];
if(i > 1)
cout<<',';
}
cout<<')';
}