1. Ce afiseaza urmatoarea secventa?
int v[]={1,2,4,8,16,32,64,128,256},w[1000] , n=9,s;
void bk(int n, int s)
{
if(n==0) w[s]=1;
else {bk(n-1,s); bk(n-1,s+v[n-1]);}
}
int main(){
bk(n,0);
for(int i=0;i<1000;i++) s+=w[i];
cout<<s;
}
R: 512
Algoritmul backtracking de mai sus genereaza toate submiltimile lui v si calculeaza pentru fiecare din acestea suma elementelor (inclusiv multimea vida). Deoarece elementele lui V sunt puteri distincte ale lui 2 toate sumele sunt diferite. Mai exact 512 sume , egal cu numarul de frunze ale arborelui binar asociat apelului bk(n,0)
2. Cate grafuri orientate cu 6 noduri au toate nodurile cu gradul exterior egal cu 3?
R:1000000
Se rezolva prin construirea matricei de adiacenta pentru un astfel de graf. Se observa ca pe fiecare linie din matrice trebuie sa punem trei valori de 1 pe cate 5 pozitii (nu avem voie sa punem pe diagonala principala) ===> C(5,3)...
3. Care este numarul maxim de muchii intr-un graf neorientat cu 10 de varfuri care NU este conex si nici un nod nu are grad impar si nici nu exista noduri izolate.
R:24
4. Un elev scrie pe o foaie toate numerele formate din exact 5 cifre. Cate dintre aceste numere au suma cifrelor egala cu 9?
R: 495
5. Ce afiseaza urmatoarea secventa?
char s[]="AdmitereLZR", *p, t[]="minister";
p=strstr(s,strchr(t,s[strlen(t+5)])+4);
cout<<p+4;
R: LZR
6. Ce afiseaza urmatoarea secventa?
int x=0;
for(int i=1; i<=1023; i++){
int ci=i;
while(ci){ x+= ci%2;
ci=ci>>1;
}
}
cout<<x;
R:1024
7. Fie un arbore cu 127 de noduri cu proprietatea ca orice nod care nu este frunza are un numar de descendenti directi egal cu o putere a lui 2 mai mare strict ca 1 (2, 4, 8 , 16 etc). Care este numarul maxim de frunze?
R: 124
8. Care dintre expresiile de mai jos are valoarea 1 indiferent de valorile variabilelor naturale NENULE x si y?
a) x>y || y>x
b) x*y>y
c) y-y%x == x-x%y
d) x*x+y*y >= x*y
R:d
9. Gigel are 10 cartonase numerotate de la 1 la 10. El trebuie le imparta in doua stive A si B a cate cinci cartonase fiecare in felul urmator:
ia prima carte (numerotata cu 1) si o aseaza in una din stive A sau B (care initial sunt vide) , ia urmatoarea carte (numerotata cu 2) si o aseaza in varful uneia dintre cele doua stive, samd.
La final obtine doua stive A si B a cate cinci cartonase fiecare. Gigel vrea sa stie in cate din incercarile efectuate el obtine in A un sir de cartonase care sunt pe fiecare nivel mai mici decat cartonasele din stiva B situate pe nivel corespunzator.
Ex A:(1 3 4 5 9) B:(2 6 7 8 10) pe primul nivel in stiva A avem 1 iar in stiva B avem 2; pe al doilea nivel in A avem 3 iar in B avem 6, etc.
R: 42 vezi(https://www.pbinfo.ro/articole/18941/elemente-de-combinatorica)