Care este șirul de caractere conținut în variabila result după execuția secvenței de cod de mai jos?
char input[15] = "Ana are 4 mere";
char result[15];
int i, j = 0, dif = 'a'-'A';
for(i = 0; i<strlen(input); i++)
if(input[i]>='a' && input[i]<='z')
result[j++] = input[i] - dif;
else if(input[i]>='A' && input[i]<='Z')
result[j++] = input[i];
result[j]='\0';
ANAAREMEREana are 4 mereanaaremereANA ARE MEREANAARE4MEREANA ARE 4 MERE
Bucla parcurge input: o literă mică este transformată în majusculă (se scade 'a'-'A'), o majusculă este copiată ca atare, iar celelalte caractere (spațiile și cifra 4) nu sunt copiate deloc, pentru că nu intră pe nicio ramură.Din Ana are 4 mere rămân doar literele, toate majuscule: ANAAREMERE.Un muzician generează toate secvențele de trei note muzicale din mulțimea {DO, RE, MI, FA, SOL, LA, SI}. Într-o secvență notele muzicale se pot repeta.Fie n numărul total de secvențe obținute și m numărul de secvențe obținute care conțin cel puțin o notă care se repetă. Care sunt valorile pentru n și m?
- n=2187, m=133
- n=2187, m=1977
- n=343, m=308
- n=210, m=35
- n=343, m=133
- n=245, m=35
Fiecare dintre cele 3 poziții poate primi oricare dintre cele 7 note: n=73=343.Secvențele fără nicio repetare sunt aranjamentele A73=7⋅6⋅5=210, deci m=343−210=133.Se consideră funcția recursivă.Dacă apelul S(10, a, b) are ca rezultat 2045, iar apelul S(5, a, b) are ca rezultat 560, atunci:
int S(int n, int a, int b)
{
if(n==0) return 0;
else return a*n + b + S(n-1,a,b);
}
- a=1, b=2
- a=10, b=5
- a=1, b=37
- a=37, b=1
- a=37, b=38
- a=5, b=10
Desfăcând recursivitatea, S(n,a,b)=a(1+2+…+n)+nb=a2n(n+1)+nb.Rezultă sistemul 55a+10b=2045 și 15a+5b=560. Din a doua ecuație b=112−3a; înlocuind, 55a+1120−30a=2045, deci 25a=925, a=37 și b=1.Se dă problema: calculați suma primelor n elemente din șirul lui Fibonacci. Care sunt complexitățile timp, respectiv, spațiu minime pentru a obține soluția pentru această problemă?
- O(2n) și O(1)
- O(n2) și O(n)
- O(n2) și O(1)
- O(n) și O(1)
- O(n) și O(n)
- O(2n) și O(n)
Termenii se pot genera pe rând, păstrând doar ultimii doi termeni și suma parțială: n pași, cu un număr constant de variabile.Dintre variantele propuse, cea mai bună este deci timp O(n) și spațiu O(1). Timpul exponențial corespunde recursivității naive, iar spațiul O(n) apare doar dacă se memorează inutil tot șirul.Fie un graf neorientat oarecare și o submulțime de k noduri (k≥1) ale acesteia. Nodurile acestei submulțimi au gradele 20,21,…,2k−1.Toate celelalte noduri din graf sunt legate la cel puțin un nod din această submulțime. Care este numărul minim, respectiv maxim, de noduri pe care le poate avea graful, în funcție de k.
- min=2k−1+1, max=2k+k−1
- min=k, max=2k−1
- min=k+1, max=2k+k−1
- min=2k−1+1, max=2k−1+1
- min=2k−1, max=2k+k
- min=k+2, max=2k+1
Minim: nodul de grad 2k−1 are 2k−1 vecini distincți, deci graful are cel puțin 2k−1+1 noduri. Valoarea se atinge: legăm acest nod de toate celelalte, iar fiecare nod de grad 2i (i<k−1) primește restul de 2i−1 vecini printre nodurile din afara submulțimii (sunt destule).Maxim: suma gradelor din submulțime este 20+21+…+2k−1=2k−1, deci din submulțime pleacă cel mult 2k−1 muchii spre alte noduri. Fiecare nod din afara submulțimii are nevoie de cel puțin una, așa că sunt cel mult 2k−1 astfel de noduri, atinse când fiecare muchie duce la un nod nou. Total maxim: 2k−1+k.