Rekursive Berechnung von PGCD in der Sprache C

Der GCD (größter gemeinsamer Teiler) zweier ganzer Zahlen, wenn mindestens eine der beiden nicht gleich Null ist, ist der größte positive ganzzahlige Teiler, der zwei Zahlen dividiert. Zum Beispiel ist die GCD von 45 und 30 15.

1- Finden Sie die GCD mit dem Modulo

Weisen Sie a den Wert von b und b den Wert des Rests der Division von a über b zu.
Wiederholen Sie, bis der Rest Null ist.

pgcd modulo Euclids erweiterter C++-Algorithmus

Beispiel:

Das entsprechende Programm in C:

#include< stdio.h> 

int main()
{
 int a,b,r,x,y; 
 do
 scanf("%d",& a); 
 while (a<=0); 
 do
 scanf("%d",& b); 
 while (b<=0); 

 if (a> b)
 {
 x=b; 
 r=a%b; 
 }
 else
 {
 x=a; 
 r=b%a; 
 }

 while(r!=0)
 {
 y=x;
 x=r; 
 r=y%x; 
 }
 printf("%d",x); 
 0 zurückgeben; 
}

2- Finde die GCD mit der rekursiven subtraktiven Methode

Wenn a und b zwei positive ganze Zahlen sind, haben wir die folgenden arithmetischen Eigenschaften:

Beispiel:

PGCD Programm mit rekursion.

int PGCD(int a, int b)
{
 if(a==b)
 {
 return a; 
 } 
 else
 {
 if(a> b)
 PGCD(a-b, b) zurückgeben; 
 else
 PGCD(a, b-a); 
 }
}

References:
Wikipedia: Größter gemeinsamer Teiler
Wikipedia: Euclids Algorithmus erweitert

Rekursive Berechnung von PGCD in der Sprache C

1- Finden Sie die GCD mit dem Modulo

2- Finde die GCD mit der rekursiven subtraktiven Methode

Commentaires (12)

Connectez-vous pour commenter