Clasa a IX-a lecția 9

From Algopedia
Jump to navigationJump to search

Algoritmul lui Euclid - cmmdc / cmmmc

Algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a inventat. Un avantaj important al algoritmului lui Euclid este că el poate găsi CMMDC eficient fără să trebuiască să calculeze factorii primi ai numerelor.

Euclid a observat că CMMDC al două numere a și b rămîne același dacă se scade numărul mai mic din cel mai mare (demonstrați!). Presupunînd că a este numărul mai mare, scăzînd în mod repetat pe b din a, în a va rămîne restul împărțirii lui a la b. Rezultă că CMMDC(a, b) este totuna cu CMMDC(b, a % b). Algoritmul care rezultă este următorul: luăm restul împărțirii lui a la b, apoi restul împărțirii lui b la rest, și așa mai departe, pînă ce obținem un rest zero. CMMDC este numărul rămas, cel diferit de zero.

Exemplu Să calculăm CMMDC(252, 105). Calculăm 252 % 105 = 42. De aceea va trebui să calculăm CMMDC(105, 42). În continuare calculăm 105 % 42 = 21. Deci, vom calcula CMMDC(42, 21). Calculăm 42 % 21 = 0. Deoarece restul este zero CMMDC va fi ultimul număr nenul, adica 21.

Algoritmul ce foloseste structura while do

Pseudocod C C++ 
citeste a,b;
while( b <> 0 )
 r ← a mod b;
 a ← b;
 b ← r;
scrie a

#include<stdio.h>
int main(){
int a,b,r;
scanf("%d%d",&a,&b);
while( b > 0){
 r = a % b;
 a = b;
 b = r;
}
printf("%d", a);
return 0;
}
 
#include <iostream>
using namespace std;
int main(){
int a,b,r;
cin>> a >> b;
while( b > 0 ){
 r = a % b;
 a = b;
 b = r;
}
cout << a;
return 0;
}

Algoritmul ce foloseste structura do while

Pseudocod C C++ 
citeste a, b;
daca ( b > 0 ) atunci
  executa
    r ← a mod b;
    a ← b;
    b ← r;
  cat_timp( r <> 0 )
scrie a
 
#include<stdio.h>
int main(){
int a, b, r;
scanf( "%d%d", &a, &b );
if( b > 0)
  do{
    r = a % b;
    a = b;
    b = r;
  }while( r != 0 );
printf( "%d", a );
return 0;
}
 
#include <iostream>
using namespace std;
int main(){
int a, b, r;
cin>> a >> b;
if( b > 0)       
  do{
    r = a % b;
    a = b;
    b = r;
  }while( r != 0 );
cout << a;
return 0;
}

Observatie: Atentie, daca b poate fi si 0, trebuie sa testam valoarea acestuia inainte de intrarea i nstructura repetitiva. Aplicatie: Doi prieteni, un iepure și o broscuță joacă un joc: pornesc de la o linie de start și încep să sară. Broasca sare n centimetri, iar iepurele m centimetri. Cine este mai în spate vine la rînd să sară. Jocul se termină atunci cînd iepurele și broasca sînt iarăși la egalitate. Cîți centimetri au parcurs cei doi prieteni?

Săriturile broscuței și iepurelui

Răspuns: după cum se vede și din figură, broscuța și iepurele vor sări o lungime egală cu CMMMC(m, n). Precum știm 

CMMMC(m, n) = m ∙ n / CMMDC(m, n)

.

Tema

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_IX-a_lecția_9&oldid=18283"