Structuri repetitive
Ideile de bază pe scurt și, unde există, exercițiile din subiectele de BAC care le verifică. Lecția completă, animată, cu grile și exerciții corectate, e în aplicația Tomomi.
Pe scurt
Sintaxă: bucla pentru (for)
Bucla cu contor, folosită când știi dinainte numărul de repetări:
pentru i ← 1, n execută
...
■for (int i = 1; i <= n; i++) {
...
}Capcana: i < n față de i <= n
for (int i = 0; i < n; i++) face n iterații (0 .. n-1). for (int i = 1; i <= n; i++) face tot n iterații (1 .. n). Greșeala clasică este să numeri o iterație în plus sau în minus: verifică mereu capetele.
Șablon: tăierea cifrelor (împărțirea la 10)
Când nu știi câți pași sunt, bucla cât timp taie câte o cifră până rămâne 0:
cât timp n > 0 execută
c ← n%10
n ← [n/10]
■while (n > 0) {
c = n % 10;
n = n / 10;
}Idee: acumulatorul și inițializarea lui
Un acumulator este o variabilă care strânge un rezultat parțial în buclă. Regula de inițializare: 0 pentru sumă, 1 pentru produs. Un produs pornit de la 0 rămâne 0; o sumă pornită de la 1 iese cu 1 în plus.
Sintaxă: repetă … până când (do-while)
Bucla cu condiția la sfârșit - corpul se execută cel puțin o dată:
repetă
...
până când condițiedo {
...
} while (!conditie);Capcana: condiția se inversează
În pseudocod, repetă ... până când C se oprește când C devine adevărat. În C++, do { ... } while (C) continuă cât timp C este adevărat. La traducere, condiția se inversează: până când x = 0 devine while (x != 0).
Fișă de sintaxă: notația pseudocod de la BAC
Notația folosită la Subiectul II, într-un singur loc.
citește a, b- citirea datelor;scrie x- afișarea. Elementele se despart prin virgulă, iar'\n'trece pe linie nouă.x ← e- atribuire. Comparația de egalitate este=, cu un singur semn.■- închide fiecare bloc:dacă,pentru,cât timp, subprogram. Se poate scrie șisfârșit.≤ ≥ ≠- comparațiile;și,sau,nu- operatorii logici, scriși în cuvinte.a%b- restul împărțirii întregi,[x]- partea întreagă ([a/b]este câtul).a[i],a[i][j]- elementul unui tablou, respectiv al unei matrice.
Cele patru structuri, cu antetul lor exact:
dacă c atunci
...
altfel
...
■
pentru i ← a, b, pas execută
...
■
cât timp c execută
...
■
repetă
...
până când cÎn subiecte, aceleași structuri apar încadrate de paranteza din stânga, care marchează corpul; o structură imbricată are paranteza ei:
┌pentru i←1,n execută
│┌dacă i%2=0 atunci
││ scrie i
│└■
└■
┌repetă
│ ...
└până când cLa pentru, pasul este opțional: lipsa lui înseamnă , iar un pas negativ face contorul să coboare.
Capcana: semnele care seamănă între ele
← atribuie, = compară. În pseudocod nu există ==, deci dacă x = 5 atunci este o comparație perfect corectă - greșeala ar fi să scrii acolo ←.
[x] nu este indexare de tablou: parantezele drepte în jurul unei expresii înseamnă partea întreagă, iar în jurul unui indice, după numele unui tablou, înseamnă un element. [n / 2] este o jumătate rotunjită în jos; a[i] este al i-lea element.
Fiecare bloc deschis are exact un ■. Un ■ lipsă sau în plus este cea mai frecventă greșeală de scriere la Subiectul II, iar la trasare schimbă complet ce se execută în interiorul buclei.
Șablon: algoritm echivalent (II.1.d)
- pentru ⇒ cât timp:
i←aînainte, condițiai≤b,i←i+1la finalul corpului. - cât timp c ⇒ repetă:
dacă c atunci repetă S până când nu c ■. - repetă S până când c ⇒ cât timp:
S, apoicât timp nu c execută S ■.
Barem: 2p structura cerută, 3p aspectele specifice (pentru ⇒ cât timp: inițializare, condiție, actualizare; cât timp ⇒ test final: condiția de oprire și cazul fără nicio iterație), 1p corectitudinea globală.
Din subiectele de BAC
Exerciții reale din subiectele anilor trecuți. Încearcă-le singur înainte să deschizi rezolvarea.
Algoritmul următor este reprezentat în pseudocod.
citește m,n (numere naturale nenule, m ≤ n)
nr ← 0; i ← m
repetă
x ← 1
cât timp x*x < i execută
x ← x+1
dacă x*x = i atunci
nr ← i
altfel
i ← i+1
până când i > n sau nr ≠ 0
scrie nrScrieți ce se afișează în urma executării algoritmului dacă se citesc, în această ordine, numerele 7 și 17.
Vezi rezolvarea
Algoritmul caută primul pătrat perfect din intervalul : pentru fiecare determină cel mai mic cu și verifică dacă .
| i | cel mai mic x cu x·x ≥ i | x·x | x·x = i? |
|---|---|---|---|
| 7 | 3 | 9 | nu → i ← 8 |
| 8 | 3 | 9 | nu → i ← 9 |
| 9 | 3 | 9 | da → nr ← 9 |
Ciclul se oprește pentru că , deci se afișează 9.
Algoritmul următor este reprezentat în pseudocod. S-a notat cu [c] partea întreagă a numărului real c.
citește n (număr natural nenul)
p ← 1
pentru i ← 1,n execută
citește x (număr natural)
repetă
x ← [x/3]
până când x ≤ 3
dacă x ≠ 0 atunci
p ← p*x
scrie pScrieți valoarea afișată dacă se citesc, în această ordine, numerele 5, 15, 27, 10, 1, 17.
Vezi rezolvarea
Primul număr citit este , iar următoarele cinci sunt valorile lui x.
| x citit | reduceri x ← [x/3] | x final | efect asupra p |
|---|---|---|---|
| 15 | 15 → 5 → 1 | 1 | p = 1·1 = 1 |
| 27 | 27 → 9 → 3 | 3 | p = 1·3 = 3 |
| 10 | 10 → 3 | 3 | p = 3·3 = 9 |
| 1 | 1 → 0 | 0 | x = 0, p rămâne 9 |
| 17 | 17 → 5 → 1 | 1 | p = 9·1 = 9 |
Se afișează valoarea 9.
Algoritmul următor este reprezentat în pseudocod. S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b, și cu [c] partea întreagă a numărului real c.
citește x (număr natural)
p ← 1; m ← -1
┌cât timp p≤x execută
│ c ← [x/p]%10
│┌dacă c>m atunci
││ m ← c; p ← p*10
││altfel
││ x ← [x/(p*10)]*p+x%p
│└■
└■
┌dacă m≥0 atunci scrie x
│ altfel scrie "nul"
└■Scrieți programul C/C++ corespunzător algoritmului dat.
Vezi rezolvarea
#include <iostream>
using namespace std;
int main() {
long long x, p, m, c;
cin >> x;
p = 1;
m = -1;
while (p <= x) {
c = (x / p) % 10;
if (c > m) {
m = c;
p = p * 10;
} else {
x = x / (p * 10) * p + x % p;
}
}
if (m >= 0)
cout << x;
else
cout << "nul";
return 0;
}Împărțirea întreagă din C/C++ realizează direct [x/p], iar cele două structuri de decizie și bucla while urmează fidel pseudocodul.