Cmmdc

Se dau 2 nr. naturale a si b. Se cere sa se calculeze cmmdc-ul lor.

a) Algorituml prin scadere repetata

Ex:

a       90   48     6      6      6     6      6    6

b       42   42   36   30   24   18   12    6

Algorituml este urmatorul: Citim a si b; cat timp a este diferit de b, scadem numarul mai mic din numarul mai mare; afisam unul din numere

pseudocodul: start

citeste a, b

cat timp a!=b executa

daca a>b atunci a=a-b

altfel b=b-a

scrie a

stop

Observatii: Aceasta metoda este lenta din punct de vedere al timpului;

In urma calcularii cmmdc, numerele se modifica. Daca dorim sa folosim numerele, trebuies sa realizam o copie a lor inainte de calculul cmmmd.

b) Algoritmul lui Euclid

a       b        r

125    25    20

35     20    15

20    15      5

15      5      0

Algoritmul este urmatorul: citim a si b; calcula restul: a%b; cat timp restul este diferit de 0, executam a=b, b=r, r=a%b; scrie b

pseudocodul:  start

citeste a, b

r=a%b

cat timp r!=0 executa

a=b

b=r

r=a%b

scrie b

stop

Observatii: Algoritmul lui Euclid este mai rapid decat „scaderi repetate”

Numerele se modifica; Trebuie facuta o copie inainte de calculul cmmdc daca se doreste ca numerele sa fie folosite ulterior.