Bella: Created page with "== Algoritmul lui Euclid - cmmdc / cmmmc == [http://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid Algoritmul lui Euclid] este o metodă eficientă de calcul al celui mai mare di..."

2023-03-14T20:39:30Z

Created page with "== Algoritmul lui Euclid - cmmdc / cmmmc == [http://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid Algoritmul lui Euclid] este o metodă eficientă de calcul al celui mai mare di..."

New page

== Algoritmul lui Euclid - cmmdc / cmmmc ==
[http://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid Algoritmul lui Euclid] este o metodă eficientă de calcul al celui mai mare divizor comun (<tt>CMMDC</tt>). El este denumit după matematicianul grec Euclid, care l-a inventat. Un avantaj important al algoritmului lui Euclid este că el poate găsi <tt>CMMDC</tt> eficient fără să trebuiască să calculeze factorii primi ai numerelor.

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

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

====Algoritmul ce foloseste structura ''while do''====
{| class="wikitable"
!Pseudocod
!C
!C++
|- style="vertical-align:top;"
|
citeste a,b;
while( b <> 0 )
r ← a mod b;
a ← b;
b ← r;
scrie a
|
<syntaxhighlight>
#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;
}
</syntaxhighlight>
|
<syntaxhighlight>
#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;
}
</syntaxhighlight>
|}

====Algoritmul ce foloseste structura ''do while''====
{| class="wikitable"
!Pseudocod
!C
!C++
|- style="vertical-align:top;"
|
<syntaxhighlight>
citeste a, b;
daca ( b > 0 ) atunci
executa
r ← a mod b;
a ← b;
b ← r;
cat_timp( r <> 0 )
scrie a
</syntaxhighlight>
|
<syntaxhighlight>
#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;
}
</syntaxhighlight>
|
<syntaxhighlight>
#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;
}
</syntaxhighlight>
|}
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 <tt>n</tt> centimetri, iar iepurele <tt>m</tt> 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?

[[Image:cmmmc.gif|frame|none|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 <tt>CMMMC(m, n)</tt>. Precum știm

<pre>CMMMC(m, n) = m ∙ n / CMMDC(m, n)</pre>.
= Tema =
* [https://www.pbinfo.ro/?pagina=probleme&id=378 pavare] teorie
* [https://www.pbinfo.ro/?pagina=probleme&id=410 cmmdc2]
* [https://www.pbinfo.ro/?pagina=probleme&id=2771,Covorul Covorul]
* [https://www.pbinfo.ro/probleme/61/afisaredivizoricomuni afisaredivizoricomuni]

Clasa a IX-a lecția 9 - Revision history

Bella: Created page with "== Algoritmul lui Euclid - cmmdc / cmmmc == [http://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid Algoritmul lui Euclid] este o metodă eficientă de calcul al celui mai mare di..."