Test de evaluare grupele B

• admincopii 25/11/2018

În prima săptămână cei de la grupele B au primit următorul test inițial. Le recomand și celor din celelalte grupe să încerce să-l rezolve.

PROGRAMARE CU RĂBDARE

Test grupa B – Proiecte

Trebuie să rezolvați cel puțin câte o problemă din fiecare categorie.

Categoria 1:

1. Anii bisecți sunt divizibili cu patru, dar nedivizibili cu 100, cu excepția anilor divizibili prin 400. Astfel, anii 1900 și 2019 nu sunt bisecți, dar anii 2000 și 2016 sunt bisecți.Care dintre următoarele expresii C/C++ testează dacă valoarea variabilei n desemnează un an bisect?
   • (n%400<1)||(n%4==0)&&(n%100!=0)
   • (n%100!=0)&&(n%400==0)||(n%4==0)
   • (n%100!=0)&&(n%4==0)
   • (n%4==0)&&(n%100!=0)&&(n%400==0)

2. Variabilele u, v, z, t memorează valori întregi astfel încât u < v și z < t. Precizează care dintre expresiile C/C++ de mai jos, atunci când este adevărată, implică faptul că intersecția intervalelor [u, v) și (z, t] este nevidă.
   • (u > t) && (v > z)
   • !((u > t) || (v > z))
   • (u <= t) && (v == z)
   • !((u > t) || (t > u))

Categoria 2:

3. Fie x o variabilă întreagă care conține cel mai mic număr natural nenul, multiplu de 36, divizibil cu toate numerele prime mai mici decât 10. Precizați care dintre expresiile C/C++ de mai jos este adevărată.
   • (x<1000) && (x % 27 == 0)
   •  (x>1000) && ((x*x*x) % 1000 == 0)
   • ((x*x) / 16) % 2 == 0
   • (x % 100 == 0) || (x / 100 == 0)

4. Pentru a reprezenta în limbajul C/C++ relațiile de prietenie dintr-un grup de oameni se folosesc următoarele definiții de date:

struct gr {
    int nrPers;
    int priet[50][50]; 
} om;

cu semnificația că în câmpul nrPers stocăm numărul de persoane din grup, iar priet[i][j] poate avea valoarea 1 (semnificând că omul cu numărul i este prieten cu omul cu numărul j), respectiv 0 (în caz contrar). Relația de prietenie se consideră reciprocă.

Cerințe:

a) Care din următoarele secvențe de atribuiri descrie în C/C++ faptul că oamenii cu numerele de ordine 3 și 5 devin prieteni.

a) om.priet[3][5]=1;
om.priet[5][3]=1;

b) gr.priet[3][5]=1;
gr.priet[5][3]=1;

c) priet.om[3][5]=1;
priet.om[5][3]=1;

d) priet.gr[3][5]=1;
priet.gr[5][3]=1;

b) Scrieți o secvență de cod C/C++ prin care puteți atribui variabilei întregi numarMaxim numărul maxim de relații de prietenie care pot exista în grupul definit mai sus.

Categoria 3:

5. O tablă albă are p simboluri “A” și m simboluri “B” scrise pe ea. Poți alege oricare două simboluri pentru a le șterge și înlocui cu altul, în conformitate cu următoarele reguli

• AA ⇒ B
• AB sau BA ⇒ A
• BB ⇒ B

Dacă vei continua să aplici aceste reguli de înlocuire cât mai mult timp posibil, ce valori ar trebui să aibă p și m ca la final să rămână un singur “A”?

6. Un robot este poziționat în locul marcat cu o săgeată în harta de mai jos, având orientarea către susul paginii. Robotul poate să interpreteze următoarele comenzi:

nI = mergi n pătrățele înainte

S/D = rotește-te cu 90 de grade la stânga/dreapta

n(commenzi) = execută comenzile dintre paranteze de n ori

O secvență de comenzi care va deplasa robotul din locația săgeții cu în fața stației C este:

• 2I + 2(8I + D) + D + 2(4I + S)
• 6I + 2(4I + S) + 5I + D + 3I + S
• 6I + 2(4I + S) + 5I + 2(D) + 2I + D
• 2I + 2(8I + D) + D + 2I + 4I + S

 Categoria 4:

7. Considerăm un alfabet A format dintr-o mulțime finită de caractere. Un cuvânt este o secvență nevidă de caractere distincte din A. Lungimea unui cuvânt este numărul de caractere din care acesta este format. Un p-sistem (p ≥ 1) este definit ca o mulțime S de cuvinte, toate de lungime p, având proprietățile:

(P1) oricare două cuvinte din S au exact un caracter comun

și

(P2) orice caracter din alfabetul A apare în cel puțin un cuvânt din S.

Exemplu: Pentru A = {’a’, ’b’, ’c’}, mulțimea S = {”ab”, ”ac”} este un 2-sistem.

Scrie un 3-sistem peste alfabetul A = {’a’, ’b’, ’c’, ’d’, ’e’, ’f’}.

8. O matrice cu 8 linii, formată doar din 0 și 1, are următoarele trei proprietăți:

(i) prima linie conține un singur element cu valoarea 1,

(ii) linia j conține de două ori mai multe elemente nenule decât linia j −1, pentru orice
j ∈{2,3, . . . , 8},

(iii) ultima linie conține un singur element cu valoarea 0.

Care este numărul total de elemente cu valoarea 0 din matrice?

1. 777
2. 769
3. 528
4. nu există o astfel de matrice.

Categoria 5:

9. O rețea de comparatori de tip n (n ≥ 2) și de dimensiune m (m ≥ 1) este o secvență (c₁, c₂, . . . , c_m) în care fiecare element c_m, numit comparator, este o pereche de numere întregi (j, k) cu proprietatea 1 ≤ j < k ≤ n.

Exemplu: Rețeaua R = ((1, 2),(2, 3)) are tipul 3 și dimensiunea 2.

Daca a este un vector de n numere întregi și R este o rețea, notăm cu R(a) vectorul obținut aplicând următoarele transformări lui a:

pentru fiecare comparator c_i = (j, k), 1 ≤ i ≤ m din R, în ordinea în care aceștia apar în rețea, dacă a[j] > a[k] atunci în vectorul a interschimbăm valorile de la pozițiile j și k.

Exemplu: Pentru R = ((1, 2),(2, 3)) și a = (30, 20, 10) avem R(a) = (20, 10, 30).

Cerințe:

a) Fie R = ((2, 4),(1, 2),(3, 4),(2, 3)) și a = (40, 30, 20, 10). Calculați R(a) și scrieți valorile intermediare ale vectorului a corespunzătoare transformărilor efectuate.

b) Dați exemplu de o rețea R de tip 4 cu proprietatea că pentru orice vector a format din 4 numere întregi distincte, R(a) va avea elementele ordonate crescător. Justificare.

10. Se consideră algoritmul de mai jos. S-a notat cu x%y restul împărţirii numărului întreg x la numărul întreg nenul y şi cu [a] partea întreagă a numărului real a.
11. a) Scrieți ce se va afișa dacă se citește 18?
12. b) Dați exemplu de un număr natural n<100, astfel încât algoritmul să afișeze 6.
13. c) Scrieți algoritmul sub forma unei funcții recursive echivalente (în pseudocod sau în C/C++)

citește n
p¬0
┌cât timp n>0 execută
│   ┌dacă n%3 = 0 atunci
│   │     n¬ [n/3]
│   │altfel
│   │    ┌dacă n%2 = 1 atunci
│   │    │     n¬ [n/2]
│   │    │altfel
│   │    │     n¬n-1
│   │    └■
│   └■
│    p¬p+1
└■
scrie p