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