I. 1.
b. (n % 2 == 0) && ( (n % 100 != 0) || (n % 400
== 0) )
I. 2.
a. F(42, 35) = 7
b. u = 10, v = 5
c. v = 91
d.
int F(int u, int v){
if(u == v || u == 0 || v == 0){
return max(u, v);
}
else
if(u % 2 == 0){
if(v % 2 == 0){
return 2 * F(u / 2, v / 2);
}
else
return F(u / 2, v);
}
else{
if(v % 2 == 0){
return F(u, v / 2);
}
else{
if(u < v){
return F(u, (v - u) / 2);
}
else
return F((u - v) / 2, v);
}
}
}
II. 1.
b. 4
II. 2.
d. nu exista un astfel de graf
II. 3.
aab -> aaa
^
|
[->aba
| ^
| |
| abb
| ^
| |
| baa<-]
| |
[--bab<-| -]
| |
bba--] |
|
bbb-----]
Putem reprezenta regulile din multimea R,
drept un graf orientat.
Putem observa faptul ca toate subsirurile de 3
caractere duc in final catre aaa.
Asadar daca vom aplica regulile de transformare
de un numar finit de ori, pe un sir de cel
putin 3 caractere, vom ajunge inevitabil la
un sir format doar din caracterul a.
b.
#include <iostream>
#include <cstring>
using namespace std;
char s[105];
bool g = false;
int main(){
cin>>s;
for(int i = 0; i < strlen(s); i ++)
if(s[i] != 'a' && s[i] != 'b')
g = true;
if(g == true){
cout<<"Date invalide";
}
else{
int n = strlen(s), cnt = 0;
for(int i = 0; i <= n - 3; i ++){
bool f = false;
while(f == false){
if(s[i] == 'a' && s[i + 1] == 'a' && s[i + 2] == 'a')
f = true;
if(f == false){
if(s[i] == 'a' && s[i + 1] == 'a' && s[i + 2] == 'b')
s[i + 2] = 'a';
else
if(s[i] == 'a' && s[i + 1] == 'b' && s[i + 2] == 'a')
s[i + 1] = 'a';
else
if(s[i] == 'a' && s[i + 1] == 'b' && s[i + 2] == 'b')
s[i + 2] = 'a';
else
if(s[i] == 'b' && s[i + 1] == 'a' && s[i + 2] == 'a')
s[i] = 'a', s[i + 1] = 'b', s[i + 2] = 'b';
else
if(s[i] == 'b' && s[i + 1] == 'a' && s[i + 2] == 'b')
s[i] = 'a', s[i + 1] = 'b', s[i + 2] = 'a';
else
if(s[i] == 'b' && s[i + 1] == 'b' && s[i + 2] == 'a')
s[i + 1] = 'a';
else
if(s[i] == 'b' && s[i + 1] == 'b' && s[i + 2] == 'b')
s[i + 1] = 'a';
cnt ++;
}
}
}
cout<<cnt<<"\n";
bool ok = true;
for(int i = 0; i < n; i ++)
if(s[i] != 'a')
ok = false;
if(ok == true){
cout<<"Sirul s contine doar caracterul a";
}
else{
cout<<"Sirul s nu contine doar caracterul a";
}
}
return 0;
}
II. 4.
a.
[ (a, 0) (b, 1) (c, 2) (d, 3) (e, 4) ]
| (e, 1) (a, 2) (b, 3) (c, 4) (d, 0) |
| (d, 2) (e, 3) (a, 4) (b, 0) (c, 1) |
| (c, 3) (d, 4) (e, 0) (a, 1) (b, 2) |
[ (b, 4) (c, 0) (d, 1) (e, 2) (a, 3) ]
b.
void B(int n, char S[105], char T[105]){
struct e{
char s;
char t;
}a[105][105];
for(int j = 0; j < n; j ++)
a[0][j].s = S[j], a[0][j].t = T[j];
for(int i = 1; i < n; i ++){
a[i][0].s = a[i - 1][n - 1].s;
for(int j = 1; j < n; j ++)
a[i][j].s = a[i - 1][j - 1].s;
for(int j = 0; j < (n - 1); j ++)
a[i][j].t = a[i - 1][j + 1].t;
a[i][n - 1].t = a[i - 1][0].t;
}
}
c.
Functia definita la punctul b construieste patratul (S, T) in modul urmator
- Pe prima linie sunt amplasate toate elementele din S si T in ordine
- Pe urmatoarele linii vor aparea elementele din S mutate cu o pozitie spre dreapta
si elementele din T , mutate cu o pozitie spre stanga fata de linia precedenta
- Astfel, fiecare element al matricii va contine un element din S si un element din T (C1)
- Nu va exista un s = s' sau un t = t' aflate pe aceeasi linie sau pe aceeasi coloana
datorita circularii elementelor (C2)
- Nu va exista o pereche (s, t) = (s', t') in matrice, deoarece n este impar.
III. 1.
a. 10
III. 2.
F91(91) = 91
III. 3.
a.
Cea mai lunga secventa progresiva de lungime 4 din matricea data este :
(7, 1), (5, 2), (3, 3), (1, 4) cu valorile (3, 5, 7, 9)
b.
int B(int N, int M, int A[105][105], int i1, int j1, int i2, int j2){
int cnt = 2;
int r1 = i2 - i1;
int r2 = j2 - j1;
int r3 = A[i2][j2] - A[i1][j1];
int x = i2 + r1, y = j2 + r2;
if(x >= 1 && x <= N && y >= 1 && y <= M){
while((A[x][y] - A[i2][j2]) == r3){
cnt ++;
i2 = x, j2 = y;
x = r1 + i2, y = r2 + j2;
if(x >= 1 && x <= N && y >= 1 && y <= M){
continue;
}
else
break;
}
}
return cnt;
}
c.
int C(int N, int M, int A[105][105]){
int cnt_max = -1;
for(int i = 1; i <= N; i ++)
for(int j = 1; j <= M; j ++)
for(int x = 1; x <= N; x ++)
for(int y = 1; y <= M; y ++)
if(i == x && j == y)
continue;
else
if( (A[x][y] - A[i][j]) > 0 ) {
int cnt = B(N, M, A, i, j, x, y);
if(cnt_max == -1 || cnt_max < cnt)
cnt_max = cnt;
}
return cnt_max;
}