Informatică

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.

 

 

 

 

 

 

 

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

Math Legion pe Facebook

Login

S5 Tab Show