Candale Silviu (silviu) Varianta originală a acestui material este disponibilă aici: http://www.cs.ubbcluj.ro/wp-content/uploads/Model-Informatica-Concurs-Mate-Info-UBB-2019-RO.pdf.
În atenția concurenților:
- Se consideră că indexarea șirurilor începe de la 1.
- Problemele tip grilă (Partea A) pot avea unul sau mai multe răspunsuri corecte. Răspunsurile trebuie scrise de candidat pe foaia de concurs (nu pe foaia cu enunțuri). Obținerea punctajului aferent problemei este condiționată de identificarea tuturor variantelor de răspuns corecte și numai a acestora.
- Pentru problemele din Partea B se cer rezolvări complete pe foaia de concurs.
- Rezolvările se vor scrie în pseudocod sau într-un limbaj de programare (Pascal/C/C++).
- Primul criteriu în evaluarea rezolvărilor va fi corectitudinea algoritmului, iar apoi performanța din punct de vedere al timpului de executare și al spațiului de memorie utilizat.
- Este obligatorie descrierea și justificarea (sub) algoritmilor înaintea rezolvărilor. Se vor scrie, de asemenea, comentarii pentru a ușura înțelegerea detaliilor tehnice ale soluției date, a semnificației identificatorilor, a structurilor de date folosite etc. Neîndeplinirea acestor cerințe duce la pierderea a 10% din punctajul aferent subiectului.
- Nu se vor folosi funcții sau biblioteci predefinite (de exemplu: STL, funcții predefinite pe șiruri de caractere).
Partea A (60 puncte)
A.1. Oare ce face? (6 puncte)
Se consideră subalgoritmul alg(x, b) cu parametrii de intrare două numere naturale x și b (1 ≤ x ≤ 1000, 1 < b ≤ 10).
Subalgoritm alg(x, b):
s ← 0
CâtTimp x > 0 execută
s ← s + x MOD b
x ← x DIV b
SfCâtTimp
returnează s MOD (b - 1) = 0
SfSubalgoritm
Precizați efectul acestui subalgoritm.
A. calculează suma cifrelor reprezentării în baza b a numărului natural x
B. verifică dacă suma cifrelor reprezentării în baza b - 1 a numărului x este divizibilă cu b - 1
C. verifică dacă numărul natural x este divizibil cu b - 1
D. verifică dacă suma cifrelor reprezentării în baza b a numărului x este divizibilă cu b - 1
A.2. Ce se afișează? (6 puncte)
Se consideră următorul program:
int sum(int n, int a[], int s){
s = 0;
int i = 1;
while(i <= n){
if(a[i] != 0) s += a[i];
++i;
}
return s;
}
int main(){
int n = 3, p = 0, a[10];
a[1] = -1; a[2] = 0; a[3] = 3;
int s = sum(n, a, p);
cout << s << ”;“ << p; // printf("%d;%d", s, p);
return 0;
}
Care este rezultatul afișat în urma execuției programului?
A. 0;0
B. 2;0
C. 2;2
D. Niciun rezultat nu este corect
A.3. Expresie logică (6 puncte)
Se consideră următoarea expresie logică (X OR Z) AND (NOT X OR Y). Alegeți valorile pentru X , Y , Z astfel încât
evaluarea expresiei să dea rezultatul TRUE:
A. X ← FALSE; Y ← FALSE; Z ← TRUE;
B. X ← TRUE; Y ← FALSE; Z ← FALSE;
C. X ← FALSE; Y ← TRUE; Z ← FALSE;
D. X ← TRUE; Y ← TRUE; Z ← TRUE;
A.4. Calcul (6 puncte)
Fie subalgoritmul calcul(a, b) cu parametrii de intrare a și b numere naturale, 1 ≤ a ≤ 1000, 1 ≤ b ≤ 1000.
1. Subalgoritm calcul(a, b): 2. Dacă a ≠ 0 atunci 3. returnează calcul(a DIV 2, b + b) + b * (a MOD 2) 4. SfDacă 5. returnează 0 6. SfSubalgoritm
Care din afirmațiile de mai jos sunt false?
A. dacă a și b sunt egale, subalgoritmul returnează valoarea lui a
B. dacă a = 1000 și b = 2, subalgoritmul se autoapelează de 10 ori
C. valoarea calculată și returnată de subalgoritm este a / 2 + 2 * b
D. instrucțiunea de pe linia 5 nu se execută niciodată
A.5. Identificare element (6 puncte)
Se consideră șirul (1, 2, 3, 2, 5, 2, 3, 7, 2, 4, 3, 2, 5, 11, ...) format astfel: plecând de la șirul numerelor naturale, se
înlocuiesc numerele care nu sunt prime cu divizorii lor proprii, fiecare divizor d fiind considerat o singură dată pentru
fiecare număr. Care dintre subalgoritmi determină al n-lea element al acestui șir (n – număr natural, 1 ≤ n ≤ 1000)?
A.
Subalgoritm identificare(n):
a ← 1, b ← 1, c ← 1
CâtTimp c < n execută
a ← a + 1, b ← a, c ← c + 1, d ← 2
f ← false
CâtTimp c ≤ n și d ≤ a DIV 2 execută
Dacă a MOD d = 0 atunci
c ← c + 1, b ← d, f ← true
SfDacă
d ← d + 1
SfCâtTimp
Dacă f atunci
c ← c - 1
SfDacă
SfCâtTimp
returnează b
SfSubalgoritm
B.
Subalgoritm identificare(n):
a ← 1, b ← 1, c ← 1
CâtTimp c < n execută
c ← c + 1, d ← 2
CâtTimp c ≤ n și d ≤ a DIV 2 execută
Dacă a MOD d = 0 atunci
c ← c + 1, b ← d
SfDacă
d ← d + 1
SfCâtTimp
a ← a + 1, b ← a
SfCâtTimp
returnează b
SfSubalgoritm
C.
Subalgoritm identificare(n):
a ← 1, b ← 1, c ← 1
CâtTimp c < n execută
a ← a + 1, d ← 2
CâtTimp c < n și d ≤ a execută
Dacă a MOD d = 0 atunci
c ← c + 1, b ← d
SfDacă
d ← d + 1
SfCâtTimp
SfCâtTimp
returnează b
SfSubalgoritm
D.
Subalgoritm identificare(n):
a ← 1, b ← 1, c ← 1
CâtTimp c < n execută
b ← a, a ← a + 1, c ← c + 1, d ← 2
CâtTimp c ≤ n și d ≤ a DIV 2 execută
Dacă a MOD d = 0 atunci
c ← c + 1, b ← d
SfDacă
d ← d + 1
SfCâtTimp
SfCâtTimp
returnează b
SfSubalgoritm
A.6. Factori primi (6 puncte)
Fie subalgoritmul factoriPrimi(n, d, k, x) care determină cei k factori primi ai unui număr natural n, începând căutarea factorilor primi de la valoarea d. Parametrii de intrare sunt numerele naturale n, d și k, iar parametrii de ieșire sunt șirul x cu cei k factori primi (1 ≤ n ≤ 10000, 2 ≤ d ≤ 10000, 0 ≤ k ≤ 10000).
Subalgoritm factoriPrimi(n, d, k, x):
Dacă n MOD d = 0 atunci
k ← k + 1
x[k] ← d
SfDacă
CâtTimp n MOD d = 0 execută
n ← n DIV d
SfCâtTimp
Dacă n > 1 atunci
factoriPrimi(n, d + 1, k, x)
SfDacă
SfSubalgoritm
Stabiliți de câte ori se autoapelează subalgoritmul factoriPrimi(n, d, k, x) prin execuția următoarei secvențe de instrucțiuni:
n ← 120 d ← 2 k ← 0 factoriPrimi(n, d, k, x)
A. de 3 ori
B. de 5 ori
C. de 9 ori
D. de același număr de ori ca și în cadrul secvenței de instrucțiuni:
n ← 750 d ← 2 k ← 0 factoriPrimi(n, d, k, x)
A.7. Oare ce face? (6 puncte)
Se consideră subalgoritmul expresie(n) , unde n este un număr natural (1 ≤ n ≤ 10000).
Subalgoritm expresie(n):
Dacă n > 0 atunci
Dacă n MOD 2 = 0 atunci
returnează -n * (n + 1) + expresie(n - 1)
altfel
returnează n * (n + 1) + expresie(n - 1)
SfDacă
altfel
returnează 0
SfDacă
SfSubalgoritm
Precizați forma matematică a expresiei \( E(n) \) calculată de acest subalgoritm:
A. \( E(n) = 1 \cdot 2 – 2 \cdot 3 + 3 \cdot 4 + … + (-1)^{n+1} \cdot n \cdot (n + 1) \)
B. \( E(n) = 1 \cdot 2 – 2 \cdot 3 + 3 \cdot 4 + … + (-1)^{n} \cdot n \cdot (n + 1) \)
C. \( E(n) = 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + … + (-1)^{n+1} \cdot n \cdot (n + 1) \)
D. \( E(n) = 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + … + (-1)^{n} \cdot n \cdot (n + 1) \)
A.8. Expresie logică (6 puncte)
Se consideră următoarea expresie logică: (NOT Y OR Z) OR (X AND Y). Alegeți valorile pentru X , Y , Z astfel încât rezultatul evaluării expresiei să fie adevărat:
A. X ← FALSE; Y ← FALSE; Z ← FALSE;
B. X ← FALSE; Y ← FALSE; Z ← TRUE;
C. X ← FALSE; Y ← TRUE; Z ← FALSE;
D. X ← TRUE; Y ← FALSE; Z ← TRUE;
A.9. Valori ale parametrului de intrare (6 puncte)
Se consideră următorul subalgoritm:
Subalgoritm SA9(a):
Dacă a < 50 atunci
Dacă a MOD 3 = 0 atunci
returnează SA9(2 * a - 3)
altfel
returnează SA9(2 * a - 1)
SfDacă
altfel
returnează a
SfDacă
SfSubalgoritm
Pentru care dintre valorile parametrului de intrare a subalgoritmul va returna valoarea 61?
A. 16
B. 61
C. 4
D. 31
A.10. Instrucțiuni lipsă (6 puncte)
Se dă următorul subalgoritm:
1: Subalgoritm cautare(x, n, val): 2: Dacă n = 1 atunci 3: returnează (x[1] = val) 4: altfel 5: returnează cautare(x, n - 1, val) 6: SfDacă 7: SfSubalgoritm
Ce instrucțiune sau instrucțiuni trebuie adăugate și unde astfel încât în urma apelului, subalgoritmul cautare(x, n, val) să determine dacă elementul val face sau nu parte din șirul x cu n elemente (n număr natural strict mai mare ca zero)?
A. Linia 5 trebuie modificată în: returnează ((x[n] = val) și cautare(x - 1, n, val))
B. Linia 5 trebuie modificată în: returnează ((x[n] = val) sau cautare(x, n - 1, val))
C. Linia 5 trebuie modificată în: dacă (x[n] = val) atunci returnează true altfel returnează cautare(x, n - 1, val)
D. nu trebuie modificată nici o instrucțiune
Partea B (30 puncte)
1. Prefix (15 puncte)
Cifra de control a unui număr natural se determină calculând suma cifrelor numărului, apoi suma cifrelor sumei și așa
mai departe până când suma obținută reprezintă un număr cu o singură cifră. De exemplu, cifra de control a numărului
182 este 2 (1 + 8 + 2 = 11, 1 + 1 = 2).
Un număr p format din exact k cifre este prefix al unui număr q cu cel puțin k cifre dacă numărul format din primele k
cifre ale numărului q (parcurse de la stânga la dreapta) este egal cu p. De exemplu, 17 este prefix al lui 174, iar 1713
este prefix al lui 1713242.
Se consideră un număr nr natural (0 < nr ≤ 30000) și o matrice (un tablou bidimensional) A cu m linii și n coloane (0 <
m ≤ 100, 0 < n ≤ 100), având ca elemente numere naturale mai mici decât 30000. Se consideră și subalgoritmul cifrăControl(x) pentru determinarea cifrei de control asociată numărului x:
Subalgoritm cifraControl(x):
s ← 0
CâtTimp x > 0 execută
s ← s + x MOD 10
x ← x DIV 10
Dacă x = 0 atunci
Dacă s < 10 atunci
Returnează s
altfel
x ← s
s ← 0
SfDacă
SfDacă
SfCâtTimp
returnează s
SfSubalgoritm
Cerințe:
a. Scrieți o variantă recursivă (fără structuri repetitive) a subalgoritmului cifrăControl(x) care are același antet și același efect cu acesta. (5 puncte)
b. Scrieți modelul matematic al variantei recursive a subalgoritmului cifrăControl(x) (dezvoltat la punctul a). (3 puncte)
c. Scrieți un subalgoritm care, folosind subalgoritmul cifrăControl(x), determină cel mai lung prefix (notat prefix) al numărului nr care se poate construi folosind cifrele de control corespunzătoare elementelor din matricea dată. O astfel de cifră de control poate fi folosită de oricâte ori în construirea prefixului. Dacă nu se poate construi un prefix, prefix va fi -1. Parametrii de intrare ai subalgoritmului sunt numerele nr, m, n, matricea A, iar parametrul de ieșire este prefix. (7 puncte)
Exemplu: dacă avem nr = 12319, m = 3 și n = 4 și matricea \( A = \begin{bmatrix}182 & 12 & 274 & 22 \\ 22 & 1 & 98 & 56 \\ 5 & 301 & 51 & 94 \end{bmatrix} \), cel mai lung prefix este prefix = 1231, cifrele de control fiind:
| Element din matrice | 182 | 12 | 274 | 22 | 1 | 98 | 56 | 5 | 301 | 51 | 94 |
| Cifră control | 2 | 3 | 4 | 4 | 1 | 8 | 2 | 5 | 4 | 6 | 4 |
2. Robi-grădina (15 puncte)
Un grădinar pasionat de tehnologie decide să folosească o „armată” de roboți pentru a uda straturile din grădina sa. El dorește să folosească apă de la izvorul situat la capătul cărării principale care străbate grădina. Fiecărui strat îi este asociat un robot și fiecare robot are de udat un singur strat. Toți roboții pornesc de la izvor în misiunea de udare a straturilor la aceeași oră a dimineții (spre exemplu 5:00:00) și lucrează în paralel și neîncetat un același interval de timp. Ei parcurg cărarea principală până la stratul lor, pe care îl udă și revin la izvor pentru a-și reumple rezervorul de apă. La finalul intervalului de timp aferent activității, toți roboții se opresc simultan, indiferent de starea lor curentă. Inițial, la izvor este amplasat un singur robinet. Grădinarul constată însă că apar întârzieri în programul de udare a plantelor deoarece roboții trebuie să aștepte la rând pentru reumplerea rezervoarelor cu apă, astfel încât consideră că cea mai bună soluție este să instaleze mai multe robinete pentru alimentarea roboților. Roboții pornesc dimineața cu rezervoarele umplute. Doi roboți nu își pot umple rezervorul în același moment de la același robinet.
Se cunosc: intervalul de timp t cât cei n roboți lucrează (exprimat în secunde), numărul de secunde di necesare pentru a parcurge distanța de la izvor la stratul asociat, numărul de secunde ui necesar pentru udarea acestui strat și faptul că umplerea rezervorului propriu cu apă durează exact o secundă pentru fiecare robot (t, n, di , ui – numere naturale, 1 ≤ t ≤ 20000, 1 ≤ n ≤ 100, 1 ≤ di ≤ 1000, 1 ≤ ui ≤ 1000, i = 1, 2, ..., n).
Cerințe:
a. Enumerați roboții care se întâlnesc la izvor la un anumit moment de timp mt (1 ≤ mt ≤ t). Justificați răspunsul.
Notă: roboții se identifică prin numărul lor de ordine. (3 puncte)
b. Care este numărul minim de robinete suplimentare minRobineteSuplim pe care trebuie să le instaleze grădinarul astfel încât roboții să nu aștepte deloc unul după altul pentru reumplerea rezervorului? Justificați răspunsul. (2 puncte)
c. Scrieți un subalgoritm care determină numărul minim de robinete suplimentare minRobineteSuplim. Parametrii de intrare sunt numerele n și t, șirurile d și u cu câte n elemente fiecare, iar parametrul de ieșire este minRobineteSuplim. (10 puncte)
Exemplu 1: dacă t = 32, n = 5, d = (1, 2, 1, 2, 1), u = (1, 3, 2, 1, 3) atunci minRobineteSuplim = 3. Explicație: robotul care se ocupă de stratul 1 are nevoie de o secundă pentru a ajunge la strat, o secundă pentru a uda stratul și de încă o secundă pentru a se întoarce la izvor; el se întoarce la izvor pentru a-și reumple rezervorul după 1 + 1 + 1 = 3 secunde de la ora de plecare (5:00:00), deci la ora 5:00:03; el își reumple rezervorul într-o secundă și pornește înapoi spre strat la ora 5:00:04; revine la ora 5:00:07 pentru a-și reumple rezervorul, continuând ritmul de udare a straturilor, ș.a.m.d.; deci, primul, al doilea, al patrulea și al cincilea robot se întâlnesc la izvor la ora 05:00:23; în consecință, este nevoie de 3 robinete suplimentare.
Exemplu 2: dacă t = 37, n = 3, d = (1, 2, 1), u = (1, 3, 2), atunci minRobineteSuplim = 1.
Citește mai departe