Atestat: programare

Exemplu

4
7 6
1 3
1 4
2 5

43 20

7/6 + 1/3 + 1/4 + 2/5 = 43/20.

Cum se rezolvă

Suma se reține ca fracție a/b. Inițial, a/b este prima fracție citită. Pentru fiecare fracție x/y citită după ea:

• se adună fracțiile: a/b + x/y = (a·y + x·b) / (b·y);
• se calculează cel mai mare divizor comun al numărătorului și numitorului, cu algoritmul lui Euclid;
• numărătorul și numitorul se împart la acest divizor.

Prin simplificarea după fiecare adunare, valorile rămân cât mai mici. După ultima adunare, fracția este ireductibilă.

Numerele se rețin în tipul long long, pentru că produsele a * y și b * y pot depăși limita tipului int.

Exemplu

1971

9

1971 → 18 → 9.

Cum se rezolvă

Cât timp numărul n are mai mult de o cifră (n > 9), el se înlocuiește cu suma cifrelor lui.

Suma cifrelor se obține prin împărțiri repetate la 10:

• restul împărțirii la 10 este ultima cifră, care se adună la sumă;
• câtul împărțirii la 10 este numărul fără ultima cifră;
• împărțirile se opresc când numărul devine 0.

Exemplu

5 23 5

21739

5/23 = 0.21739…

Cum se rezolvă

Tipul double reține numai aproximativ 15 cifre semnificative, deci zecimalele nu se pot lua din rezultatul împărțirii a / b. Ele se obțin pe rând, prin algoritmul împărțirii:

• r este restul curent; la început, r = a % b;
• la fiecare pas, restul se înmulțește cu 10;
• câtul r / b este zecimala următoare și se scrie în fișier;
• restul r % b se folosește la pasul următor.

Exemplu

• paginile 1–9 folosesc câte o cifră, adică 9 cifre;
• paginile 10–99 folosesc câte două cifre, adică 90 · 2 = 180 de cifre;
• pagina 100 folosește 3 cifre.

În total, 9 + 180 + 3 = 192 de cifre.

Cum se rezolvă

Se parcurg numerele paginilor, de la 1 la n. Pentru fiecare pagină p, cifrele se numără prin împărțiri repetate la 10, într-o copie x a lui p: la fiecare împărțire contorul cifre crește cu 1, până când x devine 0.

Exemplu

Cum se rezolvă

Termenii șirului se generează pe rând, cu două variabile:

• x este termenul curent, iar y este termenul următor; la început, x = 1 și y = 1;
• la fiecare pas, perechea (x, y) se compară cu (a, b) și cu (b, a), pentru că numerele pot fi date în orice ordine, ca în al doilea exemplu;
• se trece la perechea următoare: noul x este y, iar noul y este x + y.

Generarea se oprește când s-a găsit perechea sau când termenul curent depășește 1000000000. Termenii se rețin în tipul long long, pentru că suma x + y poate depăși limita tipului int.

Exemplu

Cum se rezolvă

Suma a k numere consecutive care încep cu a este:

a + (a + 1) + … + (a + k − 1) = k · a + k · (k − 1) / 2.

Pentru un număr de termeni k dat, reprezentarea există dacă din n = k · a + k · (k − 1) / 2 se obține un a natural nenul, adică dacă:

• r = n − k · (k − 1) / 2 este pozitiv;
• r este divizibil cu k; atunci a = r / k.

Numărul de termeni este cel puțin 2. Cel mai mare k posibil este cel pentru care k · (k − 1) / 2 < n; pentru n ≤ 1000000000 acesta este mai mic decât 44722. Se încearcă deci valorile lui k, nu toate valorile posibile ale primului termen, care ar fi prea multe pentru un n de ordinul miliardelor.

Exemplu

Cum se rezolvă

Subprogramul prim(x) verifică dacă x este prim, căutând un divizor de la 2 până la √x.

Se încearcă distanțele d = 0, 1, 2, … față de n. Pentru fiecare distanță se verifică întâi n + d, apoi n − d. Primul număr prim găsit este cel mai apropiat de n. Când n + d și n − d sunt amândouă prime, se afișează n + d, ca în al treilea exemplu.

Numărul n − d se verifică numai dacă este cel puțin 2, pentru că numerele 0 și 1 nu sunt prime.

Exemplu

Cum se rezolvă

Din fiecare valoare se păstrează prima apariție, în același vector:

• m este numărul de elemente păstrate până la un moment dat; ele ocupă pozițiile 1, …, m;
• elementul v[i] se caută printre v[1], …, v[m];
• dacă nu se găsește, el se copiază pe poziția m + 1, iar m crește cu 1.

Numărul m este mai mic decât i, deci copierea nu suprascrie un element care nu a fost încă verificat. Dacă vectorul este deja o mulțime, fiecare element se copiază pe propria poziție, iar vectorul rămâne neschimbat.

Exemplu

3

1 1 2
3 5 8
13 21 34

Primii 9 termeni ai șirului lui Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13, 21 și 34.

Cum se rezolvă

Termenii șirului se generează în timpul parcurgerii matricei, fără un vector în care să fie păstrați:

• x este termenul curent, iar y este termenul următor; la început, x = 1 și y = 1;
• elementul a[i][j] primește valoarea lui x;
• noul x este y, iar noul y este suma lor.

Liniile se parcurg de sus în jos, iar pe fiecare linie coloanele se parcurg de la stânga la dreapta.

Termenii se rețin în tipul long long. Al 93-lea termen al șirului depășește însă și limita acestui tip, deci programul scrie valori corecte numai pentru n ≤ 9, când matricea are cel mult 81 de elemente.

Exemplu

5
45 2 63 8 10
3 5 1 0 9
1 11 12 15 7
13 8 -1 41 19
-2 23 18 3 4

64

Elementele impare din zona de nord a matricei sunt 63 și 1.

Cum se rezolvă

Cu liniile și coloanele numerotate de la 1, elementul a[i][j] se află în zona de nord dacă:

• este deasupra diagonalei principale: i < j;
• este deasupra diagonalei secundare: i + j < n + 1.

Inegalitățile sunt stricte, deci elementele de pe diagonale nu intră în sumă.

Un număr este impar dacă a[i][j] % 2 != 0. Condiția a[i][j] % 2 == 1 nu este corectă aici: în C++, restul împărțirii unui număr negativ impar la 2 este -1.

Exemplu

48

factorul 2 la puterea 4
factorul 3 la puterea 1

48 = 2⁴ · 3.

Cum se rezolvă

Subprogramul descompunere(n) încearcă divizorii d în ordine crescătoare, începând cu 2:

• cât timp n se divide cu d, se împarte la d, iar exponentul p crește cu 1;
• dacă p > 0, d este factor prim și se scrie împreună cu puterea lui.

Un divizor neprim nu poate împărți numărul rămas, deoarece factorii lui primi au fost eliminați înainte.

Dacă d · d > n și n > 1, atunci n nu mai are divizori până la √n, deci este prim; în acest caz d primește direct valoarea n. Pentru un număr prim de 9 cifre, divizorii se încearcă numai până la aproximativ 31623, nu până la numărul însuși.

Exemplu

5

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

Cum se rezolvă

Ambele structuri repetitive, cea pentru linii și cea pentru numerele de pe o linie, se înlocuiesc cu câte un subprogram recursiv:

• linie(k) scrie numerele de la 1 la k: pentru k > 1 se apelează întâi linie(k - 1), apoi se scriu un spațiu și numărul k; pentru k = 1 se scrie numai 1;
• triunghi(n) scrie primele n linii: se apelează întâi triunghi(n - 1), apoi linie(n) și se trece la rând nou; pentru n = 0 nu se scrie nimic.

Exemplu

Cum se rezolvă

Vectorul este ordonat crescător, deci se folosește căutarea binară. Căutarea se face în secvența v[st..dr], inițial tot vectorul:

• se compară x cu elementul din mijloc, v[mij], unde mij = (st + dr) / 2;
• dacă sunt egale, poziția căutată este mij;
• dacă v[mij] < x, căutarea continuă în jumătatea din dreapta: st = mij + 1;
• altfel, căutarea continuă în jumătatea din stânga: dr = mij − 1.

Căutarea se oprește când s-a găsit poziția sau când secvența nu mai are elemente (st > dr). La fiecare pas, secvența se reduce la jumătate, deci pentru 50 de elemente se fac cel mult 6 comparații.

Exemplu

Cum se rezolvă

a. Pentru ca cifrele lui b să fie scrise după cele ale lui a, numărul a se înmulțește cu 10 la puterea numărului de cifre ale lui b:

• p este cea mai mică putere a lui 10 mai mare decât b; pentru b = 45, p = 100;
• rezultatul este a · p + b; pentru a = 154 și b = 45, 154 · 100 + 45 = 15445.

Pornind de la p = 10, cazul b = 0 se tratează corect: 154 concatenat cu 0 este 1540.

b. Numerele nu se memorează într-un vector. Se păstrează numai numărul citit anterior, x:

• se citește numărul următor, y;
• se calculează Concatenare(x, y) și Concatenare(y, x) și se scrie cel mai mare;
• y devine numărul anterior pentru pasul următor.

Exemplu

Cum se rezolvă

a. Cifrele lui n se obțin prin împărțiri repetate la 10, iar cea mai mare se reține în c.

b. Numerele nu se memorează. Pentru fiecare număr citit se apelează CifraMax, iar frecventa[c] numără numerele care au cifra maximă c. Vectorul de frecvență are numai 10 elemente, oricâte numere ar conține fișierul, iar fiecare număr se prelucrează o singură dată.

La final:

• se determină cea mai mare valoare din vectorul frecventa;
• se scriu cifrele cu această frecvență; parcurgerea de la 0 la 9 le dă în ordine crescătoare.

Exemplu

Cum se rezolvă

Pozițiile se numără de la 1, ca în exemplele din enunț.

a. Inversez interschimbă v[p] cu v[q], apoi apropie cele două poziții (p crește, q scade), cât timp p < q.

b. Stergp mută cu o poziție la stânga elementele de după poziția p, apoi micșorează n. Parametrul n se transmite prin referință (int &n), ca modificarea să ajungă în programul principal.

c. Pentru exemplu:

• șirul are 7 elemente, deci elementul din mijloc este pe poziția 7 / 2 + 1 = 4; după ștergerea lui 8.1 rămâne 4.1 8.2 4.3 2.1 3.1 7.9;
• se inversează pozițiile 1–3 și 4–6: 4.3 8.2 4.1 7.9 3.1 2.1.

Un tablou transmis ca parametru se modifică direct în programul apelant, deci subprogramele nu au nevoie de valoare returnată.

Exemplu

Cum se rezolvă

a. Cifrele lui n se iau de la ultima spre prima. Fiecare cifră pară c se pune în fața cifrelor deja alese: nr = nr + c * p, apoi p se înmulțește cu 10. Puterea p crește numai la cifrele pare, deci între cifrele alese nu rămân zerouri. Pentru 12245 se obțin pe rând 4, 24 și 224.

b. Cifrele se parcurg tot de la ultima spre prima. Ordinea este crescătoare dacă fiecare cifră este cel mult egală cu cifra din dreapta ei; la prima cifră mai mare, subprogramul returnează 0. Exemplul 12245 arată că cifrele egale sunt permise.

c. Numerele se citesc până la sfârșitul fișierului, fără să fie memorate. Suma poate depăși limita tipului int, deci se reține în tipul long long.

Exemplu

Cum se rezolvă

a. Cel mai mare divizor comun se calculează cu algoritmul lui Euclid prin împărțiri: cât timp b ≠ 0, perechea (a, b) se înlocuiește cu (b, a % b); rezultatul este a.

b. Cel mai mic multiplu comun se obține din relația cmmdc(a, b) · cmmmc(a, b) = a · b. În program se împarte întâi a la cmmdc și abia apoi se înmulțește cu b, ca produsul intermediar să rămână mai mic.

c. Cmmdc și cmmmc pentru mai multe numere se calculează din aproape în aproape:

• cmmdc(x₁, x₂, x₃) = cmmdc(cmmdc(x₁, x₂), x₃);
• cmmmc(x₁, x₂, x₃) = cmmmc(cmmmc(x₁, x₂), x₃).

Variabilele d și m primesc primul număr, apoi se actualizează la fiecare număr citit. Cel mai mic multiplu comun crește repede, deci se reține în tipul long long.

Exemplu

Cum se rezolvă

a. Elementele de pe pozițiile p, …, n se mută cu o poziție la dreapta, începând cu ultimul, ca niciun element să nu fie suprascris înainte de a fi mutat. Pe poziția p se pune val, iar n crește cu 1. Parametrul n se transmite prin referință.

b. Suma cifrelor se calculează prin împărțiri repetate la 10.

c. După fiecare inserare, elementul următor din vectorul inițial ajunge cu două poziții mai la dreapta. De aceea indicele i crește din 2 în 2:

• elementul inițial de pe poziția i este urmat de suma lui de cifre, inserată pe poziția i + 1;
• pasul următor tratează poziția i + 2.

Vectorul final are 2n elemente, deci se declară cu cel puțin 200 de poziții.

Exemplu

Cum se rezolvă

a. Subprogramul numără aparițiile fiecărei cifre într-un vector de 10 elemente. La prima cifră care apare a doua oară, returnează 0; dacă toate cifrele au fost parcurse, returnează 1.

b. Numerele se citesc până la sfârșitul fișierului și se memorează într-un vector, pentru că fiecare linie din date.out începe cu numerele și se termină cu numărul lor. La citire se numără numerele din fiecare categorie. Apoi:

• pe prima linie se scriu numerele cu cifre distincte și numărul lor, sau mesajul, dacă nu există;
• pe a doua linie se scriu celelalte numere și numărul lor, sau mesajul.

Mesajul se scrie cu diacritice, ca în exemplu.

Exemplu

Cum se rezolvă

Pozițiile se numără de la 1, ca în exemplul de la punctul a.

a. Parametrii prim și ultim se transmit prin referință (int &prim, int &ultim), ca valorile lor să ajungă în programul principal. La parcurgerea vectorului, prim primește poziția primului element par găsit (când încă este 0), iar ultim primește poziția fiecărui element par, deci la final rămâne cu poziția ultimului.

b. Secvența v[p..q] se ordonează prin metoda selecției: fiecare element v[i] se compară cu elementele de după el din secvență și se interschimbă cu cele mai mici.

c. În exemplu, primul număr par este 52, pe poziția 2, iar ultimul este 10, pe poziția 6. Se ordonează secvența 52 13 6 91 10 și se obține 6 10 13 52 91.

Exemplu

examen

examen xamen amen men en n
6

Din definiție (na ≤ nb), cuvântul însuși este sufix al lui.

Cum se rezolvă

Sufixul care începe pe poziția i are lungimea n − i, deci sufixele se scriu în ordinea descrescătoare a lungimii dacă i crește de la 0 la n − 1.

În C++, S + i este adresa caracterului de pe poziția i, iar fout << S + i scrie caracterele de la poziția i până la sfârșitul șirului, adică exact sufixul. Un cuvânt de lungime n are n sufixe.

Exemplu

informatica

6
informatica nformatic formati ormat rma m

Cum se rezolvă

Ca în exemplu, primul subșir centru este cuvântul întreg (x = 0). Prin eliminarea a câte x litere de la fiecare capăt rămân literele de pe pozițiile x, …, n − x − 1, adică n − 2x litere. Se scriu subșirurile pentru x = 0, 1, 2, … cât timp n − 2x > 0.

Numărul lor este (n + 1) / 2, cu împărțire întreagă:

• pentru „informatica”, n = 11 și se obțin 6 subșiruri, ultimul de o literă;
• pentru un cuvânt cu n = 4 se obțin 2 subșiruri, de 4 și de 2 litere.

Exemplu

Cum se rezolvă

În cuvântul „matematica”, vocalele sunt pe pozițiile 2, 4, 6, 8 și 10. Poziției 10 îi corespunde cifra 10 − 10 = 0, deci numărul vocal este 24680.

Caracterele se parcurg de la stânga la dreapta:

• un caracter este vocală dacă se găsește în șirul "aeiou"; funcția strchr returnează NULL dacă nu îl găsește;
• poziția numerotată de la 1 este i + 1; dacă trece de 9, din ea se scade 10;
• cifra se adaugă la sfârșitul numărului: x = x * 10 + c.

Un cuvânt de cel mult 17 caractere dă un număr de cel mult 17 cifre, care încape în tipul long long.

Exemplu

Cum se rezolvă

În cuvântul „matematica”, consoanele sunt pe pozițiile 1, 3, 5, 7 și 9, deci numărul cons este 13579.

Caracterele se parcurg de la stânga la dreapta:

• textul are numai litere mici, deci un caracter este consoană dacă nu se găsește în șirul "aeiou", adică dacă strchr returnează NULL;
• poziția numerotată de la 1 este i + 1; dacă trece de 9, din ea se scade 10;
• cifra se adaugă la sfârșitul numărului: x = x * 10 + c.

Un cuvânt de cel mult 17 caractere dă un număr de cel mult 17 cifre, care încape în tipul long long.

Exemplu

Cum se rezolvă

• După citirea lui x, fin.get() consumă caracterul de sfârșit de linie, iar fin.getline citește textul de pe linia a doua.
• Funcția strtok împarte textul în cuvinte, după spații.
• Pentru fiecare cuvânt se numără literele o; dacă numărul lor este între 1 și x, cuvântul se reține.

Numărul de cuvinte se scrie înaintea cuvintelor, deci cuvintele se rețin până la sfârșitul parcurgerii. Funcția strtok pune sfârșitul de șir după fiecare cuvânt chiar în t, de aceea este suficient să se rețină adresa de început a fiecărui cuvânt, în vectorul de pointeri cuvinte.

Exemplu

Cum se rezolvă

Rezultatul se scrie în fișierul atestat.out, cum precizează datele de ieșire.

Textul se modifică în același șir t, care se declară cu 202 poziții: dacă toate cele 100 de caractere sunt egale cu c, textul ajunge la 200 de caractere, plus caracterul de sfârșit de șir.

La fiecare poziție i pe care se află litera c:

• caracterele de la poziția i + 1 până la sfârșitul șirului, inclusiv caracterul de sfârșit, se mută cu o poziție la dreapta, începând cu ultimul;
• pe poziția i + 1 se pune litera c;
• lungimea n și numărul de modificări cresc cu 1;
• i crește cu încă 1, ca litera adăugată să nu fie dublată și ea.

Exemplu

Cum se rezolvă

Textul se împarte în cuvinte cu strtok. Pentru fiecare cuvânt:

• se numără vocalele;
• dacă sunt cel puțin x, cuvântul se parcurge de la stânga la dreapta și se șterg primele x vocale întâlnite;
• cuvântul se scrie în fișier, cu un spațiu înaintea lui, cu excepția primului cuvânt.

Ștergerea caracterului de pe poziția i se face prin copierea restului cuvântului cu o poziție mai la stânga. Funcția strcpy nu admite ca sursa și destinația să se suprapună, de aceea restul cuvântului se copiază întâi în șirul aux. După ștergere, pe poziția i se află alt caracter, deci i scade cu 1, ca acel caracter să fie verificat și el.

Exemplu

Cum se rezolvă

Textul se împarte în cuvinte cu strtok. Pentru fiecare cuvânt:

• se numără consoanele, adică literele care nu se găsesc în șirul "aeiou";
• dacă sunt cel puțin x, cuvântul se parcurge de la sfârșit spre început și se șterg primele x consoane întâlnite, care sunt ultimele x consoane ale cuvântului;
• cuvântul se scrie în fișier, cu un spațiu înaintea lui, cu excepția primului cuvânt.

Ștergerea caracterului de pe poziția i se face prin copierea restului cuvântului cu o poziție mai la stânga, prin intermediul șirului aux, pentru că strcpy nu admite ca sursa și destinația să se suprapună. Parcurgerea se face spre stânga, deci caracterele mutate au fost deja verificate.

Exemplu

Cum se rezolvă

Literele mici au coduri ASCII consecutive, deci literele care urmează după vocala t[i] sunt t[i] + 1 și t[i] + 2. De exemplu, după o urmează p și q. Vocalele sunt a, e, i, o, u, deci literele următoare există întotdeauna în alfabet.

La fiecare vocală de pe poziția i:

• caracterele de la poziția i + 1 până la caracterul de sfârșit de șir se mută cu două poziții la dreapta, începând cu ultimul;
• pe pozițiile i + 1 și i + 2 se pun cele două litere;
• lungimea n crește cu 2, iar i sare peste literele inserate.

Șirul are cel mult 50 de caractere, iar după inserări poate ajunge la 150, deci se declară cu 151 de poziții.

Exemplu

Cum se rezolvă

Rezultatul se scrie în fișierul atestat.out, cum precizează datele de ieșire.

Textul se parcurge de la stânga la dreapta. La fiecare vocală de pe poziția i se șterg caracterele de pe pozițiile i + 1 și i + 2: restul textului, de la poziția i + 3, se copiază începând cu poziția i + 1.

Literele inserate după o vocală nu sunt niciodată vocale, deci după ștergere parcurgerea poate continua cu poziția i + 1. Funcția strcpy nu admite ca sursa și destinația să se suprapună, de aceea restul textului se copiază întâi în șirul aux.

Exemplu

Cum se rezolvă

a. Subprogramul adună elementele x[p][1], …, x[p][n].

b. Subprogramul se apelează o singură dată pentru fiecare linie, iar sumele se rețin în vectorul s. Apoi:

• se determină cea mai mare valoare din s;
• se scriu indicii liniilor a căror sumă este egală cu această valoare.

Exemplu

Cum se rezolvă

Elementele sunt cifre binare, deci numărul elementelor nenule de pe o coloană este numărul de valori 1 de pe acea coloană.

Numerele trebuie luate din tabloul inițial. După înlocuirea liniei 3, coloanele ar conține alte valori, iar linia 5 ar primi alte numere. De aceea:

• întâi se calculează, cu numarare, numărul de valori 1 de pe fiecare coloană și se reține în vectorul c;
• apoi fiecare linie pentru care toateNule returnează 1 primește valorile din c.

Tabloul se declară cu 101 × 101 elemente, după limita de la punctul b.

Exemplu

Cum se rezolvă

a. Coloanele k1 și k2 se parcurg linie cu linie. La prima linie pe care elementele lor sunt egale, subprogramul returnează 0. Dacă toate perechile sunt diferite, returnează 1.

b. Subprogramul se apelează pentru prima coloană și fiecare dintre coloanele 2, …, m, iar apelurile care returnează 1 se numără.

Tabloul de 200 × 200 de elemente se declară global, nu în funcția main.

Exemplu

Cum se rezolvă

a. Pentru fiecare linie i, elementele a[i][k1] și a[i][k2] se interschimbă prin intermediul variabilei aux.

b. Tabloul se parcurge linie cu linie, de la stânga la dreapta. Coloana minimului (cmin) și coloana maximului (cmax) se schimbă numai la o valoare strict mai mică, respectiv strict mai mare, deci rămân coloanele pe care valorile apar prima dată. Când minimul și maximul apar pe aceeași coloană, interschimbarea nu ar schimba nimic, deci subprogramul se apelează numai dacă cmin ≠ cmax.

Exemplu

Cum se rezolvă

Rezultatul se scrie în fișierul matrice.out, cum cere punctul b.

a. Pentru fiecare linie i se verifică elementul de pe diagonala principală, a[i][i], și cel de pe diagonala secundară, a[i][n + 1 − i]. Maximul pornește de la −1, deci rămâne −1 dacă nu se găsește nicio valoare pară.

b. Un element a[i][j] se află în afara diagonalelor dacă i ≠ j și i + j ≠ n + 1. Elementele impare care îndeplinesc această condiție primesc valoarea returnată de maxim_d. Subprogramul se apelează o singură dată, înaintea modificărilor.

Exemplu

Cum se rezolvă

Tipul produs grupează cele trei date ale unui produs: cantitatea, prețul de achiziție și adaosul. Produsele se citesc într-un vector de elemente de acest tip.

La parcurgerea vectorului, pentru fiecare produs:

• se calculează prețul de vânzare, pv = pret + pret · adaos / 100;
• la valoarea totală se adaugă cantitate · pv;
• poziția poz a celui mai vândut produs se schimbă dacă produsul curent are o cantitate mai mare sau, la cantitate egală, un adaos mai mare.

În exemplu, produsele 2 și 4 au cantitatea maximă, 5, iar produsul 4 are adaosul mai mare (3 față de 2). Valoarea totală se afișează cu două zecimale, cu fixed și setprecision(2).

Exemplu

5
Avram Teodor 20 15
Barbu Anda 45 20
Flore Marius 30 15
Marcu Alin 10 10
Valea Sebastian 25 16

Avram Teodor 10
Marcu Alin 10
Valea Sebastian 10
Flore Marius 9
Barbu Anda 8

Cum se rezolvă

Tipul elev grupează numele, prenumele, numărul total de absențe, numărul de absențe motivate și nota. La citirea fiecărui elev se calculează nota:

• absențele nemotivate sunt diferența dintre total și cele motivate;
• dacă sunt mai mult de 50, nota este 4;
• altfel, nota este 10 − nemotivate / 10, cu împărțire întreagă; de exemplu, Barbu Anda are 25 de absențe nemotivate și primește nota 8.

Lista se ordonează descrescător după notă prin metoda bulelor. Două înregistrări se interschimbă numai dacă nota primei este strict mai mică, deci elevii cu aceeași notă rămân în ordinea din fișier, ca în exemplu. O înregistrare se copiază întreagă printr-o singură atribuire, aux = e[i].

Exemplu

4
2504 135 8 0

3 1
0 3
1 0
1 0

Pe fiecare rând, primul număr este numărul cifrelor pare, iar al doilea este numărul cifrelor impare. Numărul 2504 are cifrele pare 2, 0, 4 și cifra impară 5.

Cum se rezolvă

• se citește n, apoi numerele, unul câte unul;
• pentru fiecare număr, contoarele pare și impare pornesc de la 0;
• ultima cifră se obține cu x % 10 și se elimină cu x = x / 10;
• după paritatea cifrei se mărește unul dintre contoare.

Structura repetitivă do ... while execută cel puțin o dată corpul, deci și numărul 0 este tratat corect: are o cifră, iar aceasta este pară.

Exemplu

0 2 3 4 5 7 9

Cum se rezolvă

Cifrele se numără într-un vector de frecvență fr, cu 10 elemente: fr[c] reține de câte ori apare cifra c în număr.

• se extrag cifrele numărului cu x % 10 și x / 10, iar pentru fiecare cifră c se mărește fr[c];
• se parcurge vectorul de la cifra 0 la cifra 9;
• fiecare cifră c se afișează de fr[c] ori.

Cifrele care apar de mai multe ori se afișează de tot atâtea ori.

Exemplu

Numarul 1021 poate fi scris in baza 3

Numarul 1024 nu poate fi scris in baza 3

În baza 3 se folosesc numai cifrele 0, 1 și 2, iar numărul 1024 conține cifra 4.

Cum se rezolvă

În baza b se folosesc cifrele de la 0 la b - 1. Un număr poate fi scris în baza b dacă toate cifrele lui sunt mai mici decât b.

• se citesc numărul x și baza b;
• variabila ok pornește cu valoarea true;
• se parcurg cifrele numărului, iar la prima cifră mai mare sau egală cu b, ok devine false;
• după valoarea lui ok se afișează mesajul.

Exemplu

4*322=1288

Cum se rezolvă

Dacă p este 10, 100, 1000, …, atunci n / p este numărul din stânga semnului, iar n % p este numărul format din ultimele cifre ale lui n, cele din dreapta semnului. Pentru n = 4322:

• p = 10: 432 și 2, cu produsul 864;
• p = 100: 43 și 22, cu produsul 946;
• p = 1000: 4 și 322, cu produsul 1288.

Puterea p se înmulțește cu 10 cât timp n / p mai are cel puțin o cifră. Pentru fiecare împărțire se calculează produsul, iar cel mai mare se reține împreună cu cele două numere.

Exemplu

3
3829 105 0

9
5
0

Cum se rezolvă

• se citește n, apoi numerele, unul câte unul;
• pentru fiecare număr, variabila maxim pornește de la 0, cea mai mică cifră;
• se extrag cifrele cu x % 10 și x / 10, iar fiecare cifră mai mare decât maxim devine noul maxim;
• după prelucrarea tuturor cifrelor se afișează maxim.

Exemplu

5
123 99 1000 45 207

Suma cifrelor maxima: 99
Suma cifrelor minima: 1000

Sumele cifrelor sunt 6, 18, 1, 9 și 9.

Cum se rezolvă

Suma cifrelor se calculează cu subprogramul sumaCifrelor. În programul principal:

• sMax pornește de la -1, iar sMin de la 100, o valoare mai mare decât orice sumă a cifrelor unui număr cu cel mult 9 cifre (cel mult 81);
• pentru fiecare număr citit se calculează suma cifrelor s;
• dacă s > sMax, se rețin noua sumă maximă și numărul;
• dacă s < sMin, se rețin noua sumă minimă și numărul.

Comparațiile sunt stricte, deci dacă mai multe numere au aceeași sumă maximă sau minimă, se afișează primul dintre ele.

Exemplu

3
3829 505 7

9 2
5 0
7 7

Pe fiecare rând se afișează întâi cifra maximă, apoi cifra minimă.

Cum se rezolvă

• pentru fiecare număr citit, cMax pornește de la 0, cea mai mică cifră, iar cMin de la 9, cea mai mare cifră;
• se extrag cifrele cu x % 10 și x / 10;
• fiecare cifră se compară cu cMax și cu cMin, care se actualizează.

Numărul 7 are o singură cifră, deci aceasta este în același timp cifra maximă și cifra minimă.

Exemplu

Pentru n = 54321 se afișează DA.

Pentru n = 543234 se afișează NU.

Cum se rezolvă

Cifrele ordonate strict descrescător de la stânga la dreapta sunt ordonate strict crescător de la dreapta la stânga. Cifrele se extrag de la cifra unităților spre stânga, deci fiecare cifră trebuie să fie strict mai mare decât cifra extrasă înaintea ei.

• ultima reține cifra extrasă anterior;
• la fiecare pas se compară cifra curentă n % 10 cu ultima;
• dacă cifra curentă este mai mică sau egală cu ultima, condiția nu este îndeplinită, iar ok devine false.

Exemplu

2

Ultima cifră este 2 și apare de două ori în număr.

Cum se rezolvă

• ultima cifră se reține în variabila u = n % 10;
• se parcurg toate cifrele numărului, inclusiv ultima;
• contorul nr se mărește la fiecare cifră egală cu u.

Ultima cifră este numărată și ea, deci rezultatul este cel puțin 1.

Exemplu

9 3

Cea mai mare cifră este 9 și apare de trei ori.

Cum se rezolvă

Maximul și numărul lui de apariții se determină la o singură parcurgere a cifrelor. Pentru fiecare cifră c:

• dacă c este mai mare decât maximul cMax, ea devine noul maxim, iar contorul nr primește valoarea 1;
• dacă c este egală cu cMax, contorul nr crește cu 1.

cMax pornește de la -1, deci prima cifră extrasă devine maxim, chiar dacă este 0.

Exemplu

220

Numarul nu are cifre pare

Cum se rezolvă

Numărul nou se construiește din cifrele pare ale lui n, de la cifra unităților spre stânga.

• rezultat pornește de la 0, iar p de la 1;
• fiecare cifră pară se adaugă la rezultat înmulțită cu p, adică pe poziția unităților, a zecilor, a sutelor ș.a.m.d.;
• după fiecare cifră pară adăugată, p se înmulțește cu 10;
• cifrele impare nu se adaugă.

Pentru 532997201, cifrele pare sunt, de la dreapta la stânga, 0, 2, 2, iar numărul obținut este 0 · 1 + 2 · 10 + 2 · 100 = 220.

Exemplu

7
7177 205 77 0

3
0
2

Prima valoare citită este cifra c = 7. Urmează numerele, până la 0.

Cum se rezolvă

• se citește întâi cifra c;
• se citește primul număr, apoi, cât timp numărul citit este diferit de 0, se numără aparițiile cifrei c în el, se afișează rezultatul și se citește numărul următor;
• valoarea 0 oprește citirea și nu se prelucrează.

Exemplu

Numarul 123321 este palindrom

Numarul 12322 nu este palindrom

Cum se rezolvă

Un număr este palindrom dacă este egal cu oglinditul lui, adică cu numărul format din aceleași cifre, scrise în ordine inversă.

• oglinditul se construiește dintr-o copie x a numărului: la fiecare pas, oglindit = oglindit * 10 + x % 10, apoi x = x / 10;
• la final, oglinditul se compară cu n.

Pentru 12322 se obține oglinditul 22321, diferit de număr.

Exemplu

3
1234 1200 5

4321
21
5

Oglinditul lui 1200 este 0021, adică numărul 21.

Cum se rezolvă

Subprogramul oglindit primește un număr și returnează oglinditul lui:

• og pornește de la 0;
• la fiecare pas, ultima cifră a lui x se adaugă la dreapta lui og, prin og = og * 10 + x % 10, apoi se elimină din x, prin x = x / 10.

Programul principal citește n și, pentru fiecare număr citit, afișează valoarea returnată de subprogram.

Exemplu

12 345

1234 5678

Cum se rezolvă

Din exemplu se vede că, la un număr cu un număr impar de cifre, al doilea număr primește cifra din mijloc: 12345 are 5 cifre, iar al doilea număr are 3.

• se numără cifrele lui n în variabila nrCifre;
• al doilea număr are k = (nrCifre + 1) / 2 cifre;
• se calculează p = 10 la puterea k;
• primul număr este n / p, iar al doilea este n % p.

Exemplu

2 3 4 5

Cum se rezolvă

Se folosește un vector apare cu 10 elemente de tip bool, câte unul pentru fiecare cifră: apare[c] are valoarea true dacă cifra c se găsește în număr.

• inițial, toate elementele vectorului au valoarea false;
• pentru fiecare cifră c a numărului, apare[c] primește valoarea true;
• se parcurg cifrele de la 0 la 9 și se afișează cele pentru care apare[c] este true.

Exemplu

6
5 8 2 1 7 9

2 5 8 9 7 1

Cum se rezolvă

Elementele se rețin în vectorul a, pe pozițiile de la 1 la n. Prima jumătate ocupă pozițiile de la 1 la m = n / 2, iar a doua jumătate pozițiile de la m + 1 la n.

Fiecare jumătate se ordonează separat, prin metoda interschimbării: fiecare element se compară cu toate elementele aflate după el în aceeași jumătate, iar cele două se interschimbă dacă nu sunt în ordinea cerută.

• în prima jumătate se interschimbă când a[i] > a[j], pentru ordinea crescătoare;
• în a doua jumătate se interschimbă când a[i] < a[j], pentru ordinea descrescătoare.

Exemplu

153 370 371 407

De exemplu, 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.

Cum se rezolvă

Se parcurg toate numerele de la 100 la 999. Pentru fiecare număr x se calculează cifrele:

• a = x / 100, cifra sutelor;
• b = x / 10 % 10, cifra zecilor;
• c = x % 10, cifra unităților.

Numărul se afișează dacă a * a * a + b * b * b + c * c * c este egal cu x.

Exemplu

11 22 33 44 55 66 77 88 99 111

Cum se rezolvă

Enunțul nu dă numele fișierului; programul scrie în fișierul cifre.txt.

Subprogramul cifreIdentice verifică dacă toate cifrele unui număr sunt egale cu ultima lui cifră și returnează true sau false.

În programul principal:

• se citesc a și b; dacă a > b, cele două valori se interschimbă, pentru ca intervalul să fie parcurs de la capătul mai mic;
• se parcurg numerele din intervalul [a, b];
• numerele pentru care subprogramul returnează true se scriu în fișier.

Exemplu

Pentru n = 100 se afișează:

1 2 3 4 5 6 7 8 9 10 12 18 20 21 24 27 30 36 40 42 45 48 50 54 60 63 70 72 80 81 84 90 100

De exemplu, 84 are suma cifrelor 12, iar 84 = 12 · 7.

Cum se rezolvă

• subprogramul sumaCifrelor returnează suma cifrelor unui număr;
• în programul principal se parcurg numerele de la 1 la n;
• se afișează numerele x pentru care x % sumaCifrelor(x) este 0.

Numărul 0 nu se verifică: suma cifrelor lui este 0, iar împărțirea la 0 nu este definită.

Exemplu

4 13 22 31 40 103 112 121 130 202

Fiecare dintre aceste numere are suma cifrelor 4.

Cum se rezolvă

• subprogramul sumaCifrelor returnează suma cifrelor unui număr;
• în programul principal se cercetează numerele 1, 2, 3, … în ordine;
• fiecare număr cu suma cifrelor egală cu m se afișează, iar contorul gasite crește cu 1;
• căutarea se oprește când gasite ajunge la n.

Exemplu

6 28 496

De exemplu, divizorii lui 28 mai mici decât el sunt 1, 2, 4, 7, 14, iar suma lor este 28.

Cum se rezolvă

Un număr natural este perfect dacă este egal cu suma divizorilor săi mai mici decât el.

Subprogramul perfect calculează suma acestor divizori:

• suma pornește de la 1, divizorul oricărui număr mai mare decât 1;
• divizorii d se caută numai până la rădăcina pătrată a numărului (d * d <= x); pentru fiecare divizor d găsit, se adaugă și perechea lui, x / d, dacă este diferită de d;
• subprogramul returnează true dacă suma este egală cu numărul.

Exemplu

5
12 7 30 16 9

30

Numerele au, în ordine, 6, 2, 8, 5 și 3 divizori.

Cum se rezolvă

Subprogramul nrDivizori numără divizorii unui număr x:

• divizorii d se caută până la rădăcina pătrată a lui x (d * d <= x);
• fiecare divizor d găsit are perechea x / d, care se numără și ea, dacă este diferită de d.

În programul principal, pentru fiecare număr citit se calculează numărul de divizori și se compară cu maximul nrMax. Când se găsește un număr de divizori mai mare, se rețin noul maxim și numărul. Comparația este strictă, deci se afișează primul dintre numerele cu număr maxim de divizori.

Exemplu

1 2 3 6

Cum se rezolvă

Un divizor comun al lui a și b nu poate depăși cel mai mic dintre cele două numere.

• se parcurg valorile d de la 1 până la minimul dintre a și b;
• se afișează valorile d care divid ambele numere, adică cele pentru care a % d == 0 și b % d == 0.

Divizorii comuni ai lui a și b sunt divizorii celui mai mare divizor comun al lor: pentru 12 și 18, cel mai mare divizor comun este 6, cu divizorii 1, 2, 3, 6.

Exemplu

Cum se rezolvă

Cel mai mic divizor d al lui n, mai mare decât 1, este un număr prim. Numărul n este un produs de două numere prime dacă:

• are un divizor d cu d * d <= n, deci nu este prim;
• câtul n / d este și el un număr prim.

Primalitatea câtului se verifică cu subprogramul prim, care caută divizori de la 2 până la rădăcina pătrată a numărului.

Exemplu

60

Cum se rezolvă

Cel mai mic multiplu comun a două numere se obține din cel mai mare divizor comun al lor:

cmmmc(a, b) = a · b / cmmdc(a, b)

Pentru trei numere, cel mai mic multiplu comun se calculează în doi pași: cmmmc(a, b, c) = cmmmc(cmmmc(a, b), c).

• subprogramul cmmdc aplică algoritmul lui Euclid prin împărțiri repetate;
• subprogramul cmmmc folosește formula de mai sus;
• programul principal apelează cmmmc de două ori.

Pentru 4, 6 și 10: cmmmc(4, 6) = 12, iar cmmmc(12, 10) = 60.

Exemplu

4
12 18 24 30

6

Cum se rezolvă

Cel mai mare divizor comun a mai multor numere se calculează din aproape în aproape: cmmdc(a₁, a₂, …, aₙ) = cmmdc(cmmdc(a₁, …, aₙ₋₁), aₙ).

• variabila d primește valoarea primului număr citit;
• fiecare număr următor x se citește, iar d devine cmmdc(d, x);
• după citirea tuturor numerelor, d este rezultatul.

Subprogramul cmmdc aplică algoritmul lui Euclid prin împărțiri repetate.

Exemplu

Cum se rezolvă

O fracție se simplifică prin cel mai mare divizor comun al numărătorului și numitorului. Fracția obținută este ireductibilă.

• dacă numitorul este 0, fracția nu există și se afișează un mesaj;
• dacă numitorul este negativ, numărătorul și numitorul își schimbă semnul, pentru ca semnul fracției să rămână la numărător;
• se calculează d, cel mai mare divizor comun al lui |a| și b;
• se afișează a / d și b / d, despărțite prin /.

Pentru a = 0, cel mai mare divizor comun este b, iar fracția devine 0/1.

Exemplu

3 27
5 12
8 13
2 46
13 17
0 0

(5 12) (8 13) (13 17)
3 perechi

Cum se rezolvă

Două numere sunt prime între ele dacă cel mai mare divizor comun al lor este 1.

• se citește prima pereche a, b;
• cât timp niciunul dintre numere nu este 0, se calculează cmmdc(a, b); dacă rezultatul este 1, perechea se afișează, iar contorul nr crește cu 1; apoi se citește perechea următoare;
• după oprirea citirii se afișează nr.

Perechea care conține 0 oprește citirea și nu se prelucrează.

Exemplu

13 este prim
31 este prim

23 este prim
32 nu este prim

Cum se rezolvă

Programul folosește două subprograme:

• oglindit returnează numărul format din cifrele lui x în ordine inversă;
• prim returnează true dacă x este prim; numerele 0 și 1 nu sunt prime, iar pentru celelalte se caută un divizor de la 2 până la rădăcina pătrată a lui x (d * d <= x).

În programul principal se calculează oglinditul, apoi se verifică fiecare dintre cele două numere și se afișează câte un mesaj.

Exemplu

2 3 5 7 11 13 17 19

Cum se rezolvă

• subprogramul prim returnează true dacă numărul primit este prim: numerele 0 și 1 nu sunt prime, iar pentru celelalte se caută un divizor de la 2 până la rădăcina pătrată a numărului;
• în programul principal se parcurg numerele de la 2 la n și se afișează cele pentru care subprogramul returnează true.

Exemplu

Programul nu are date de intrare. Se afișează 143 de numere, de la 101 la 997:

101 103 107 109 113 127 131 137 139 149 ... 953 967 971 977 983 991 997

Cum se rezolvă

Numerele de trei cifre sunt cele de la 100 la 999. Fiecare dintre ele se verifică cu subprogramul prim, care caută un divizor de la 2 până la rădăcina pătrată a numărului; numerele fără niciun astfel de divizor se afișează.

Exemplu

10 = 3 + 7
10 = 5 + 5

20 = 3 + 17
20 = 7 + 13

Cum se rezolvă

Orice scriere are forma n = p + (n − p). Pentru ca o scriere să nu apară de două ori (3 + 7 și 7 + 3), primul termen p ia valori numai până la n / 2.

• se parcurg valorile p de la 2 la n / 2;
• se afișează scrierea dacă atât p, cât și n - p sunt prime.

Primalitatea se verifică cu subprogramul prim.

Exemplu

15 7 2 9 13 1 0

7 2 13

Cum se rezolvă

• variabila k reține numărul de elemente ale vectorului v și pornește de la 0;
• se citește un număr, apoi, cât timp numărul citit este diferit de 0, se verifică dacă este prim;
• un număr prim se adaugă în vector: k crește cu 1, iar numărul se memorează în v[k];
• la final se afișează cele k elemente ale vectorului.

Primalitatea se verifică cu subprogramul prim.

Exemplu

4 9 11 1 23 25 2

11 23 2

Cum se rezolvă

Numărul de valori din fișier nu este dat, de aceea citirea se face cât timp mai există numere în fișier: expresia f >> x are valoarea false după ultimul număr.

• fiecare număr citit se verifică cu subprogramul prim;
• numerele prime se scriu în fișierul sir.out, despărțite prin spații.

Exemplu

3
1 2 3
6 5 4
12 496 7

2

Sub diagonala principală se află elementele 6, 12 și 496. Numerele 6 și 496 sunt perfecte, iar 12 nu este: 1 + 2 + 3 + 4 + 6 = 16.

Cum se rezolvă

Cu liniile și coloanele numerotate de la 1, elementul a[i][j] se află sub diagonala principală dacă i > j.

• subprogramul perfect adună divizorii lui x de la 1 la x / 2 și compară suma cu x;
• pentru fiecare linie i, de la 2 la n, coloana j ia valori de la 1 la i - 1;
• contorul nr crește pentru fiecare element perfect.

Un divizor al lui x, diferit de x, nu depășește x / 2, de aceea căutarea se oprește la x / 2.

Exemplu

3
11 12 13
24 25 26
37 38 39

2

Deasupra diagonalei secundare se află elementele 11, 12 și 24, cu sumele cifrelor 2, 3 și 6. Două dintre sume sunt pare.

Cum se rezolvă

Cu liniile și coloanele numerotate de la 1, elementul a[i][j] se află pe diagonala secundară dacă i + j = n + 1 și deasupra ei dacă i + j < n + 1, adică j <= n - i.

• subprogramul sumaCifrelor returnează suma cifrelor unui număr;
• pentru fiecare linie i, de la 1 la n - 1, coloana j ia valori de la 1 la n - i;
• contorul nr crește pentru fiecare element cu suma cifrelor pară.

Exemplu

3
11 12 13
24 25 15
37 38 39

2

Sub diagonala secundară se află elementele 15, 38 și 39. Numerele 15 și 39 sunt formate numai din cifre impare.

Cum se rezolvă

Cu liniile și coloanele numerotate de la 1, elementul a[i][j] se află sub diagonala secundară dacă i + j > n + 1, adică j >= n - i + 2.

• subprogramul cifreImpare returnează false la prima cifră pară găsită și true dacă toate cifrele sunt impare;
• pentru fiecare linie i, de la 2 la n, coloana j ia valori de la n - i + 2 la n;
• contorul nr crește pentru fiecare element format numai din cifre impare.

Exemplu

11125 11133 11147 11152 11169 11174 11196 11215 11222 11226 ...

Printre ele se află 12345: 120 = 15 · 8. Pentru 11125, suma cifrelor este 10, iar produsul este 10.

Cum se rezolvă

Se parcurg numerele de la 10000 la 99999. Pentru fiecare număr se calculează, la aceeași parcurgere a cifrelor:

• suma cifrelor s, care pornește de la 0;
• produsul cifrelor p, care pornește de la 1.

Numărul se afișează dacă p % s == 0.

Exemplu

37

Numerele prime mai mari decât 20 sunt 23, 29, 31, 37, …; al patrulea este 37.

Cum se rezolvă

• variabila x pornește de la n, iar contorul gasite de la 0;
• cât timp gasite < p, x crește cu 1, iar dacă noul x este prim, gasite crește cu 1;
• structura repetitivă se oprește chiar la al p-lea număr prim, care se afișează.

Primalitatea se verifică cu subprogramul prim.

Exemplu

Cum se rezolvă

Descompunerea în factori primi se face prin împărțiri repetate, cu divizorul d pornind de la 2:

• cât timp x se împarte exact la d, se împarte și se numără împărțirile în variabila putere;
• dacă putere este mai mare decât putereMax, se rețin noua putere maximă și factorul d;
• d crește cu 1, iar procedeul se reia până când x devine 1.

Exemplu

360 = 2^3 * 3^2 * 5^1

Cum se rezolvă

Divizorul d pornește de la 2. Cât timp x este mai mare decât 1:

• se numără în variabila putere de câte ori se împarte exact x la d, iar x se împarte de tot atâtea ori;
• dacă putere este mai mare decât 0, d este factor prim al numărului și se afișează sub forma d^putere;
• d crește cu 1.

Divizorii d care nu sunt primi nu îl mai divid pe x, deoarece factorii lor primi au fost deja eliminați. Variabila primul permite afișarea semnului * numai între factori.

Exemplu

6
12 60 48 24 72 96

12

Cum se rezolvă

• Cel mai mare divizor comun a două numere se calculează cu algoritmul lui Euclid, prin împărțiri repetate, într-un subprogram cmmdc.
• Primul număr din fișier se păstrează în variabila d.
• Pentru fiecare dintre următoarele numere, d devine cel mai mare divizor comun dintre d și numărul citit.
• La final, d este cel mai mare divizor comun al tuturor celor n numere.

Exemplu

5 -2 4
9 12 7

Elementul egal cu 6 nu este nici mai mic, nici mai mare decât x, deci nu intră în niciun subșir.

Cum se rezolvă

• Se citesc n, cele n elemente ale vectorului v și valoarea x.
• Vectorul se parcurge o singură dată:
  • un element mai mic decât x se adaugă la sfârșitul vectorului a;
  • un element mai mare decât x se adaugă la sfârșitul vectorului b.
• Variabilele na și nb rețin câte elemente are fiecare subșir.
• Se afișează vectorul a pe un rând și vectorul b pe rândul următor.

Exemplu

15 se gaseste pe pozitia 5

Pentru x = 9 se afișează 9 nu se gaseste in vector.

Cum se rezolvă

Vectorul este ordonat crescător, deci se poate folosi căutarea binară:

• căutarea se face în secvența dintre pozițiile st și dr, inițial 1 și n;
• se compară x cu elementul din mijlocul secvenței, de pe poziția m = (st + dr) / 2;
• dacă v[m] == x, valoarea a fost găsită;
• dacă v[m] < x, căutarea continuă în jumătatea din dreapta (st = m + 1);
• dacă v[m] > x, căutarea continuă în jumătatea din stânga (dr = m - 1);
• căutarea se oprește când valoarea a fost găsită sau când secvența a rămas fără elemente (st > dr).

Exemplu

6.2
4 6 8 0

Elementele pozitive sunt 4, 6, 3, 8 și 10, cu suma 31, deci media este 31 / 5 = 6.2. Pe pozițiile impare 1, 3, 5 și 7 se află 4, 6, 8 și 0, toate pare.

Cum se rezolvă

• Elementele sunt naturale, deci un element este pozitiv când este diferit de 0.
• Se calculează suma s și numărul k al elementelor pozitive, iar media este s / k. Suma se transformă în double înainte de împărțire, ca rezultatul să păstreze zecimalele.
• Dacă nu există elemente pozitive, media nu se poate calcula și se afișează un mesaj.
• Pozițiile impare se parcurg cu pasul 2, pornind de la 1, și se afișează elementele pare găsite pe ele.

Exemplu

1 3 3
4 5 8
8 9

Cum se rezolvă

Numerele au cel mult 3 cifre, deci iau valori de la 0 la 999. De aceea ordonarea se face cu un vector de frecvență:

• f[x] reține de câte ori apare numărul x în fișier;
• numerele se citesc din fișier până la sfârșitul lui, fără să conteze cum sunt așezate pe rânduri;
• valorile x se parcurg de la 0 la 999, iar fiecare se scrie de f[x] ori, deci numerele ies în ordine crescătoare;
• variabila k numără câte numere s-au scris pe linia curentă; când ajunge la n, se trece pe linia următoare.

Exemplu

45 3

Cum se rezolvă

Maximul și numărul lui de apariții se determină în aceeași parcurgere, pe măsură ce se citesc numerele:

• primul număr devine maximul, cu o apariție;
• un număr mai mare decât maximul devine noul maxim, iar numărul de apariții redevine 1;
• un număr egal cu maximul crește numărul de apariții cu 1.

Exemplu

2

Elementul minim este -1.5 și apare de două ori.

Cum se rezolvă

• Numerele se citesc într-un vector v de tip double.
• La o primă parcurgere se determină elementul minim.
• La a doua parcurgere se numără elementele egale cu minimul.

Compararea cu == este corectă aici, pentru că minimul nu este calculat, ci este chiar una dintre valorile citite.

Exemplu

11

Cum se rezolvă

• Textul poate conține spații, deci se citește cu cin.getline, care citește tot rândul.
• Se parcurge textul caracter cu caracter, până la caracterul nul de la sfârșitul șirului.
• Un caracter este vocală dacă apare în șirul "aeiouAEIOU"; verificarea se face cu funcția strchr, care întoarce NULL când caracterul nu se găsește în șir.

Exemplu

7

Cum se rezolvă

• Textul se citește cu cin.getline, ca să fie citite și spațiile.
• Se parcurge textul caracter cu caracter.
• Un caracter este cifră dacă se află între '0' și '9', pentru că în codul ASCII cifrele au coduri consecutive.

Exemplu

tATA eSTE LA
pIATa?

Litera T de la începutul primului rând este mare, deci devine t.

Cum se rezolvă

• Fișierul se citește linie cu linie, cu fin.getline, până la sfârșitul lui.
• Fiecare caracter al liniei se verifică:
  • o literă mică se transformă în literă mare cu toupper;
  • o literă mare se transformă în literă mică cu tolower;
  • celelalte caractere (spații, semne de punctuație, cifre) rămân neschimbate.
• Linia transformată se scrie în BAC.OUT, urmată de trecerea la linia următoare.

Cum se rezolvă

Termenii șirului se calculează pe rând, fără vector, cu trei variabile:

• a și b sunt ultimii doi termeni calculați, inițial f₁ = 1 și f₂ = 1;
• termenul următor este c = a + b, după care a primește valoarea lui b, iar b valoarea lui c.

Primii doi termeni sunt egali cu 1, deci produsul lor este 1, iar pentru n = 1 sau n = 2 rezultatul este 1. Produsul p pornește de la 1 și se înmulțește, pe rând, cu termenii f₃, ..., fₙ. Pentru n = 6 termenii sunt 1, 1, 2, 3, 5, 8, iar produsul lor este 240.

Exemplu

DA

Pentru numerele 21 și 55 se afișează NU: între ele se află termenul 34.

Cum se rezolvă

• Numerele se citesc în variabilele x și y; dacă x > y, se interschimbă, ca x să fie cel mai mic.
• Se generează perechile de termeni consecutivi ai șirului (a, b), pornind de la (1, 1); la fiecare pas, perechea devine (b, a + b).
• Generarea continuă cât timp a < x, adică până când primul termen al perechii ajunge la x sau îl depășește.
• Numerele sunt termeni consecutivi numai dacă perechea la care s-a oprit generarea este chiar (x, y).
• Șirul începe cu doi termeni egali cu 1, deci perechea (1, 2) se verifică separat: pentru x = 1 generarea se oprește la perechea (1, 1).

Cum se rezolvă

Suma se păstrează ca fracție p / q, cu numărătorul și numitorul în variabile întregi. Inițial suma este 0 / 1.

• La fiecare pas k, de la 2 la n, se adună fracția 1 / k: p / q + 1 / k = (p * k + q) / (q * k).
• După fiecare adunare, fracția se simplifică prin cel mai mare divizor comun al numărătorului și al numitorului, calculat cu algoritmul lui Euclid. Astfel, numerele rămân cât mai mici, iar la final fracția este ireductibilă.

Pentru n = 5: 1/2 + 1/3 + 1/4 + 1/5 = (30 + 20 + 15 + 12) / 60 = 77/60.

Exemplu

62

Suma este 2 + 4 + 8 + 16 + 32 = 62. Pentru x = -3 și n = 3 se afișează -21, adică -3 + 9 - 27.

Cum se rezolvă

• Variabila p reține puterea curentă a lui x; inițial p = 1.
• La fiecare pas i, de la 1 la n, p se înmulțește cu x, deci devine x la puterea i, și se adună la sumă.
• Pentru x = 99 și n = 9, puterea are 18 cifre, deci p și suma se declară de tip long long.

Exemplu

33

Expresia este 1 + 2 + 6 + 24 = 33.

Cum se rezolvă

• Termenul de rang i al sumei este 1 * 2 * ... * i, adică i!.
• Fiecare termen se obține din cel dinaintea lui printr-o singură înmulțire: i! = (i - 1)! * i.
• Variabila p reține termenul curent, iar E suma termenilor de până acum.
• Factorialele cresc foarte repede, deci p și E se declară de tip long long; așa rezultatul este corect până la n = 20.

Exemplu

180

Expresia este 1 * 3 * 6 * 10 = 180.

Cum se rezolvă

• Factorul de rang i este suma 1 + 2 + ... + i.
• Fiecare factor se obține din cel dinaintea lui printr-o singură adunare: suma s crește cu i.
• La fiecare pas, produsul E se înmulțește cu suma s.
• Pentru n = 9 produsul depășește valoarea maximă a tipului int, deci E se declară de tip long long.

Exemplu

-22

Expresia este 3 - 10 + 21 - 36 = -22.

Cum se rezolvă

• Termenul de rang i este i * (2 * i + 1).
• Termenii de rang impar se adună, iar cei de rang par se scad.
• Variabila semn are valoarea 1 la primul termen și își schimbă semnul la fiecare pas.

Exemplu

Produsul: 21
Catul: 2
Restul: 1

Cum se rezolvă

Programul lucrează cu numere naturale.

Produsul a * b se obține adunând numărul a de b ori:

• p pornește de la 0;
• o structură repetitivă cu b pași adună la fiecare pas valoarea lui a.

Câtul și restul împărțirii lui a la b se obțin scăzând b din a cât timp se poate:

• r pornește de la a, iar câtul c de la 0;
• cât timp r >= b, din r se scade b, iar c crește cu 1;
• când r < b, scăderile se opresc: c este câtul, iar r este restul.

Exemplu

1 2 3
4 5 6
7 8 9

432

Sub diagonala secundară se află elementele 6, 8 și 9, iar 6 * 8 * 9 = 432.

Cum se rezolvă

• Pe diagonala secundară a unei matrice de ordin n se află elementele a[i][j] cu i + j == n + 1.
• Sub diagonala secundară se află elementele cu i + j > n + 1.
• Produsul p pornește de la 1 și se înmulțește cu fiecare element care îndeplinește condiția.
• Produsul poate avea multe cifre, deci p se declară de tip long long.

Exemplu

1 2 3
4 5 6
7 8 9

7

Deasupra diagonalei secundare se află elementele 1, 2 și 4.

Cum se rezolvă

• Pe diagonala secundară a unei matrice de ordin n se află elementele a[i][j] cu i + j == n + 1.
• Deasupra diagonalei secundare se află elementele cu i + j < n + 1.
• Pe linia i, aceste elemente sunt pe coloanele de la 1 la n - i, deci se parcurg numai ele.

Exemplu

10 15 21 23 8 4 7

10
8
4
4

Numerele impare din fișier sunt 15, 21, 23 și 7, deci pe ultimul rând se scrie 4.

Cum se rezolvă

• Numerele se citesc din fișier unul câte unul, până la sfârșitul fișierului.
• Un număr par se scrie în PARE.TXT, urmat de trecerea la linia următoare.
• Pentru un număr impar se mărește contorul imp.
• După citirea tuturor numerelor, valoarea lui imp se scrie pe ultimul rând al fișierului PARE.TXT.

Exemplu

8 12 0 6

Cum se rezolvă

• Valorile se citesc una câte una, fără să fie memorate toate.
• O valoare pară se adaugă la sfârșitul vectorului v: numărul de elemente k crește cu 1, iar valoarea se pune pe poziția k.
• La final se afișează cele k elemente ale vectorului construit.
• Dacă nicio valoare nu este pară, vectorul rămâne fără elemente și se afișează un mesaj.

Exemplu

4

Perechile de elemente consecutive egale sunt pe pozițiile (1, 2), (3, 4), (4, 5) și (7, 8).

Cum se rezolvă

• Elementele consecutive sunt perechile v[i] și v[i + 1], cu i de la 1 la n - 1.
• Pentru fiecare pereche cu elemente egale, contorul nr crește cu 1.

Exemplu

3 7 1 5 9 4 6

Media aritmetică este 30 / 6 = 5, iar vectorul obținut are 7 elemente, cu media pe poziția 4.

Cum se rezolvă

• Media aritmetică poate avea zecimale, deci vectorul se declară de tip double.
• Se calculează suma elementelor și media ma = s / n.
• Poziția de inserare este p = n / 2 + 1, adică imediat după primele n / 2 elemente. Pentru n impar, înaintea mediei rămân n / 2 elemente, iar după ea cu un element mai mult.
• Elementele de pe pozițiile n, n - 1, ..., p se deplasează cu o poziție spre dreapta, începând cu ultimul, ca să nu se piardă niciun element.
• Pe poziția p, rămasă liberă, se pune media, iar numărul de elemente devine n + 1.

Exemplu

4 6 10
3

Pe pozițiile impare 1, 3, 5 și 7 se află 4, 6, 7 și 10, dintre care pare sunt 4, 6 și 10.

Cum se rezolvă

• Pozițiile se numerotează de la 1, deci pozițiile impare sunt 1, 3, 5, …; ele se parcurg cu pasul 2.
• Un element este par când restul împărțirii lui la 2 este 0; condiția este corectă și pentru numerele negative.
• Fiecare element par găsit se afișează, iar contorul nr crește cu 1.
• Pe rândul următor se afișează valoarea lui nr.

Exemplu

4 9 7 5 1

Cum se rezolvă

• Elementele de pe pozițiile p + 1, ..., n se deplasează cu o poziție spre stânga: v[i] primește valoarea lui v[i + 1], pentru i de la p la n - 1.
• Astfel, valoarea de pe poziția p este înlocuită de elementul următor.
• Numărul de elemente scade cu 1, apoi se afișează vectorul.

Exemplu

10 50 30 40 20

Cum se rezolvă

• Valorile v[p] și v[q] se interschimbă printr-o variabilă auxiliară aux:
  • aux primește valoarea lui v[p];
  • v[p] primește valoarea lui v[q];
  • v[q] primește valoarea păstrată în aux.
• Vectorul se afișează după interschimbare.

Exemplu

Vectorul este ordonat crescator

Pentru n = 4 și elementele 2 5 4 9 se afișează Vectorul nu este ordonat crescator.

Cum se rezolvă

• Vectorul este ordonat crescător când fiecare element este mai mic sau egal cu elementul următor: v[i] <= v[i + 1], pentru i de la 1 la n - 1.
• Variabila ordonat pornește cu valoarea true.
• Vectorul se parcurge cât timp nu s-a găsit o pereche v[i] > v[i + 1]; la prima astfel de pereche, ordonat devine false, iar parcurgerea se oprește.

Exemplu

4 5
3 4
1 1
-2 3.5
6 0

4 5
3 4
1 1
-2 3.5
6 0
2

Punctele (1, 1) și (-2, 3.5) se află în interiorul cercului. Punctul (3, 4) se află pe cerc, iar punctul (6, 0) se află în exteriorul lui.

Cum se rezolvă

• un punct de coordonate (x, y) se află în interiorul cercului dacă distanța de la el la O este mai mică decât r, adică x² + y² < r²;
• comparația se face între pătrate, deci nu este necesară funcția sqrt;
• punctele de pe cerc, pentru care x² + y² = r², nu se numără.

Exemplu

5
4 1 5 2 3

5
4 1 5 2 3
2 4 5 1 3

Valoarea 1 se află pe poziția 2, valoarea 2 pe poziția 4, valoarea 3 pe poziția 5, valoarea 4 pe poziția 1, iar valoarea 5 pe poziția 3.

Cum se rezolvă

• elementele tabloului sunt n numere distincte din mulțimea {1, 2, …, n}, deci fiecare valoare de la 1 la n apare o singură dată;
• la citirea elementului de pe poziția i, cu valoarea x, se memorează poz[x] = i;
• vectorul poz se afișează de la poz[1] la poz[n], deci indicii apar în ordinea crescătoare a valorilor, fără să fie necesară o ordonare.

Exemplu

1234

2341
3412
4123

O nouă mutare a primei cifre ar da din nou numărul 1234.

Cum se rezolvă

• se determină numărul de cifre k al lui n și puterea p = 10^(k-1);
• pentru un număr x de k cifre:
  • prima cifră este x / p;
  • numărul fără prima cifră este x % p;
  • numărul obținut prin mutarea primei cifre pe ultima poziție este x % p * 10 + x / p;
• operația se repetă de k - 1 ori, deoarece a k-a mutare dă din nou numărul n;
• dacă numărul obținut începe cu cifra 0, el are mai puțin de k cifre, dar p rămâne același, deci cifra 0 trece corect pe ultima poziție la mutarea următoare (de exemplu 1203, 2031, 312, 3120).

Exemplu

101101

101101
45

101101₂ = 1 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 1 · 2² + 0 · 2¹ + 1 · 2⁰ = 32 + 8 + 4 + 1 = 45.

Cum se rezolvă

• numărul se citește ca șir de caractere, deoarece un număr scris în baza 2 are multe cifre;
• cifrele se parcurg de la stânga la dreapta, iar valoarea se calculează cu relația v = v * 2 + cifra, unde cifra este s[i] - '0'.

Exemplu

7
2 5 8 12 16 23 38

7
2 5 8 12 16 23 38
Numarul 16 se afla in sir pe pozitia 5

Pentru x = 10, ultimul rând afișat este Numarul 10 nu se afla in sir.

Cum se rezolvă

Șirul este ordonat crescător, deci căutarea optimă este căutarea binară:

• secvența în care se caută este cuprinsă între pozițiile st și dr, inițial 1 și n;
• se compară x cu elementul din mijloc, a[mij], unde mij = (st + dr) / 2:
  • dacă sunt egale, numărul a fost găsit pe poziția mij;
  • dacă a[mij] < x, căutarea continuă în jumătatea din dreapta, cu st = mij + 1;
  • dacă a[mij] > x, căutarea continuă în jumătatea din stânga, cu dr = mij - 1;
• căutarea se oprește când numărul a fost găsit sau când st > dr.

La fiecare pas, lungimea secvenței se înjumătățește, deci numărul de comparații este de ordinul log₂ n.

Exemplu

6.3333333333

S = 1 + 2/1 + 4/2 + 8/6 = 1 + 2 + 2 + 1.3333… = 6.3333…

Cum se rezolvă

• termenul t al sumei pornește de la 1, primul termen;
• termenul de rang i se obține din cel de rang i - 1: xⁱ/i! = xⁱ⁻¹/(i-1)! · x/i, deci t = t * x / i;
• astfel nu se calculează separat puterea și factorialul la fiecare pas;
• suma se memorează într-o variabilă de tip double, tipul real cu dublă precizie, și se scrie cu 10 zecimale.

Exemplu

4 -9 7 0 16 -5 25 3

4 -9 7 0 16 -5 25 3
36

Modulele 4, 9, 0, 16 și 25 sunt pătrate perfecte, iar 4 + (-9) + 0 + 16 + 25 = 36.

Cum se rezolvă

• numerele se citesc din fișier unul câte unul și se afișează;
• subprogramul patratPerfect caută cel mai mic r cu r * r >= x; numărul x este pătrat perfect dacă r * r == x;
• subprogramul se apelează pentru abs(x), iar la sumă se adaugă numărul x, cu semnul lui.