Clasa a IX-a
Ştiinţele naturii
Ce sunt aceştia ?
Algoritmii elementari oferă metode de rezolvare pentru probleme clasice
ing.Lungu Iudit 2
1. Algoritmi pentru interschimbare
Varianta 1 – cu variabilă intermediară
real a, b, x;
început
citeşte a, b;
xa;
ab;
bx;
scrie a, b;
sfârşit
ing.Lungu Iudit 3
Varianta 2 – fără variabilă intermediară
real a, b;
început
citeşte a, b;
aa-b;
ba+b;
ab-a;
scrie a, b;
sfârşit
ing.Lungu Iudit 4
2. Algoritm pentru determinarea maximului (minimului)
Algoritmul determină valoarea maximă (minimă) dintr-un şir de numere introduse de la tastatură.
Modalitate de lucru:
Se atribuie primului element valoarea max (min)
Apoi se compară acesta cu fiecare element din şir
ing.Lungu Iudit 5
Varianta 1 – se ştie n
întreg a, max, n, i;
început
citeşte n, a;
max a ;
pentru i 2, n execută;
citeşte a;
dacă a max
atunci maxa;
sfîrşit_dacă;
sfârşit_pentru;
scrie max;
sfârşiting.Lungu Iudit 6
Varianta 2 – până la introducerea lui 0
întreg a, max;
început
citeşte a;
max a ;
cât timp a0 execută;
dacă a max
atunci maxa;
sfîrşit_dacă;
sfârşit_cât_timp;
scrie max;
sfârşit
ing.Lungu Iudit 7
3. Algoritmi pentru prelucrarea cifrelor unui număr
a) Algoritm pentru extragerea cifrelor unui număr
b) Algoritm pentru compunerea unui număr din cifrele sale
c) Algoritm pentru determinarea inversului unui număr
ing.Lungu Iudit 8
a) Algoritm pentru extragerea cifrelor unui număr
Se determină cifrele unui număr prin extragerea pe rând a ultimei cifre a numărului prin n mod 10 şi eliminarea din număr a cifrei extrase prin n div 10 până la epuizarea tuturor cifrelor
întreg n, c;
început
citeşte n;
cât timp n0 execută;
cn mod 10;
scrie c;
nn div 10;
sfârşit_cât_timp;
sfârşit
ing.Lungu Iudit 9
b) Algoritm pentru compunerea unui număr din cifrele sale
Se determină numărul format din cifrele introduse de la tastatură, primul număr devenind cifra cea mai semnificativă.
Algoritmul utilizează reprezentarea unui număr în baza 10
ing.Lungu Iudit 10
c) Algoritm pentru determinarea inversului unui număr
Algoritmul determină inversul unui număr prin extragerea pe rând a fiecărei cifre a unui număr (începând cu cifra unităţilor) şi compunerea unui nou număr în care aceasta devine cifra cea mai semnificativă
întreg n, inv;
început
citeşte n;
cât timp n0 execută;
invinv*10 + n mod 10;
nn div 10;
sfârşit_cât_timp;
scrie inv;
sfârşit
ing.Lungu Iudit 11
4. Algoritmi pentru determinarea cmmdc
Varianta 1 – Algoritmul lui Euclid, care atribuie lui b, restul împărţirii lui a la b, iar lui a vechea valoare a lui b (b0)
întreg a, b, r;
început
citeşte a, b;
cât timp b0 execută;
ra mod b;
a b;
br;
sfârşit_cât_timp;
Scrie “cmmdc=“, a;
Sfârşit
ing.Lungu Iudit 12
Sapt.28
Varianta 2 – algoritmul de scădere repetată
întreg a, b;
început
citeşte a, b;
cât timp ab execută;
dacă a>b
atunci a a - b;
altfel b b - a;
sfârsit_dacă;
sfârşit_cât_timp;
Scrie “cmmdc=“ , a;
sfârşit
ing.Lungu Iudit 13
5. ALGORITMI PENTRU TESTAREA UNUI NR. PRIM
Constă în generarea tuturor numerelor naturale >=2 şi <=sqrt(n) şi verificarea dacă acestea îl divid pe n.
Dacă cel puţin unul dintre ele îl divid pe n nr nu este prim.
ing.Lungu Iudit 14
întreg n,i;
logic x;
inceput
citeste n;
xT; i 2;
cat timp i<=sqrt(n) and x executa
daca n mod i =0
atunci x F;
altfel i i+1;
sfarsit_daca;
sfarsit_cat_timp;
daca x
atunci scrie “numarul este prim”;
altfel scrie “numarul nu este prim”;
sfarsit_daca;
sfarsit
ing.Lungu Iudit 15
Ciurul lui Eratostene
ing.Lungu Iudit 16
6. ALGORITMI PT. PRELUCRAREA DIVIZORILOR UNUI NUMAR
Algoritmul de generarea a divizorilor proprii ai unui număr n constă în împărţirea numărului la un şir de numere i, i[2,n/2].
Dacă numărul n se împarte la numărul generat, atunci acesta este divizor al lui n.
ing.Lungu Iudit 17
Varianta 1
întreg n,i;
început
citeşte n;
scrie 1,n;
pentru i2, n div 2 execută
dacă n mod i = 0
atunci scrie i;
sfârşit_dacă;
sfârşit_pentru;
sfârşit;
ing.Lungu Iudit 18
Se verifică dacă n este divizibil cu i, dacă da se scrie i.
Se repeta acţiunea de la i=2 la i=n div 2
Varianta 2
întreg n,i;
început
citeşte n;
scrie 1,n;
pentru i2, sqrt(n) execută
dacă n mod i = 0
atunci scrie i, n div i;
sfârşit_dacă;
sfârşit_pentru;
sfârşit;
ing.Lungu Iudit 19
Se verifică dacă n este divizibil cu i, dacă da se scrie i. Se afişează şi n div i care este
divizor al lui n
Se repeta acţiunea de la i=2 la i=n div 2
7. ALGORITMI PT. CONVERSII INTRE SISTEME DE NUMERATIE
Algoritm pentru conversia din baza 10 în baza q
Conversia unui număr n din baza 10 în baza q se face prin împărţirea întreagă a numărului la q până când restul obţinut este mai mic decât q.
Resturile obţinute reprezintă cifrele numărului n scris în baza q, primul rest reprezentând cifra cea mai puţin semnificativă, iar ultimul rest cifra cea mai semnificativă.
ing.Lungu Iudit 20
Algoritm în pseudocod(din baza 10 în baza q)
întreg nz,nq,p,q;
început
citeşte nz, q;
nq 0; p 1;
cât timp nz<>0 execută
nq nq + p*(nz mod q);
nz nz div q;
p p*10;
sfârşit_cât_timp;
scrie nq;
sfârşit
ing.Lungu Iudit 21
Algoritm pentru conversia din baza 10 în baza q
Conversia unui număr nq, din baza q(2 q9), într-un număr nz reprezentat în baza 10, se face folosind descompunerea numărului după puterile bazei
nq=an*qn+an-1*qn-1+…………+a1*q+a0*q0
nz=(an*q+an-1)*q+an-2)*q+……+a1)*q+a0
ing.Lungu Iudit 22
Algoritm în pseudocod(din baza q în baza 10)
întreg c,nz,q;
început
citeşte q;
nz 0;
citeste c;
cât_timp c>=0 and c<q execută
nz nz *q+c;
citeste c;
sfârşit_cât_timp;
scrie nz;
sfârşit
ing.Lungu Iudit 23
ing.Lungu Iudit 24
8. ALGORITMI PT. GENERAREA SIRURILOR RECURENTE
13.06
ing.Lungu Iudit 25