Informatică

User Rating: 5 / 5

Star ActiveStar ActiveStar ActiveStar ActiveStar Active
 

Algoritmul lui Euclid de aflare a cmmdc a 2 numere.

Acest algoritm se poate aplica utilizând operația de scădere .

Algoritmul lui Euclid prin scădere - are la bază teoria conform căreia cel mai mare divizor a două numere divide și diferența acestora. Pașii algoritmului sunt următorii:

a) Atât timp cât  numerele sunt diferite, se scade numărul mai mic din numărul mai mare;

b) Dacă numerele devin egale, atunci valoare găsită este cel mai mare divizor comun al celor 2 numere date.

Să-l scriem:

var a,b, cmmdc: byte;

START

afișează ( 'Introduceți cele două numere a și b:');

citește (a,b);

cât timp a≠b execută

               dacă a>b execută a=a-b

               altfel execută b=b-a;

cmmdc=a; {sau cmmdc=b; nu contează, deoarece la final a și b sunt egale }

afișează (cmmdc);

STOP.

Exemple:

A) a=18, b=10

P1:  a=18,b=10

a>b (18>10) deci a=a-b=18-10=8

P2:  a=8, b=10

Acum b>a deci b=b-a=10-8=2

P3:  a=8, b=2

a>b deci a=a-b=8-2=6

P4:  a=6, b=2

a>b deci a=a-b=6-2=4

P5:  a=4, b=2

a>b deci a=a-b=4-2=2

P6:  a=b=2, algoritmul se termină și cmmdc (a,b)=2

B) a=7, b=4

P1:  a=7,b=4

a>b (7>4) deci a=a-b=7-4=3

P2:  a=3, b=4

Acum b>a deci b=b-a=4-3=1

P3:  a=3, b=1

a>b deci a=a-b=3-1=2

P4:  a=2, b=1

a>b deci a=a-b=2-1=1

P5:  a=b=1, algoritmul se termină și cmmdc (a,b)=1, deci numerele a și b sunt prime între ele.

 

 

 

 

 

 

 

Share

Comments powered by CComment

Cauchy
Mulțumesc pentru că vizitați blogul meu! Reveniți pentru și mai multe noutăți interesante!
 
 

DESPRE SITE
Blog - MateCuprinde articole despre anumite capitole sau subiecte din matematică tratate punctual.
CategoriiToate materialele le găsiți sortate în funcție de categoria în care doriți să le căutați.
MediaMuzica, video și altele...
 
Euler
MATH LEGION
Salut! Am creat acest site pentru a împărtăși cu voi ideile în stilul meu personal.

Ultimele articole

Abonează-te

Guests Online

We have 85 guests and no members online

Login