Größter gemeinsamer Teiler

120739

Ich habe ein Programm geschrieben, um den größten gemeinsamen Teiler zwischen zwei Zahlen zu finden. Wie verbessere ich dieses Programm?

#include<iostream>
using namespace std;

int main() {

int first_number;
cout<<"Enter First Number : ";
cin>>first_number;

if(first_number < 0)
cout << "Please enter a positive number" << endl;
cin >> first_number;

int  second_number;
cout<<"Enter Second Number: ";
cin>>second_number;


if(second_number < 0)
cout << "Please enter a positive number" << endl;
cin >> second_number;

int  gcd;
for(int i=1;i<=first_number&&i<=second_number;i++){

if(first_number%i==0 && second_number%i == 0 ){

gcd=i;

   }

}

cout<<"Greatest Common Divison (GCD):"<<gcd<<endl;
return 0;
}
Antworten
14
btw C ++ hat jetzt ein `std :: gcd` eingebaut Aryaman vor 2 Jahren 0

5 Antworten auf die Frage

22
janos

Eine elegantere Implementierung der gcdFunktion:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Um sicherzustellen, dass die Argumente positiv sind, ist es am einfachsten, die abs(...)Funktion zu verwenden.


Bitte ziehen Sie auch Ihren Code gut ein, um ihn lesbarer zu machen.

Und Platz für die Bediener. Zum Beispiel stattdessen:

for(int i=1;i<=first_number&&i<=second_number;i++){

Schreiben Sie wie folgt:

for (int i = 1; i <= first_number &&i <= second_number; i++) {

Zusammenfassend kann die Umsetzung des gesamten Programms kurz und bündig werden:

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int num1, num2;

    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;

    cout << "Greatest Common Divisor: " << gcd(abs(num1), abs(num2)) << endl;
}

Sie können damit auf Ideone spielen .

9
Quaxton Hale
  1. Stoppen Sie die Verwendung using namespace std. Lies das hier

  2. Es scheint, dass Sie nicht möchten, dass Benutzer negative Zahlen eingeben. Wenn ein Benutzer dies tut, wird er zur erneuten Eingabe aufgefordert. Was ist, wenn der Benutzer erneut eine negative Zahl eingibt? Sie müssen hier eine while-Schleife verwenden oder Ihr Programm die Eingabe in positiv ändern.

    //Check if user input is negative. 
    num1 = (num1 > 0) ? num1 : -num1;
    num2 = (num2 > 0) ? num2 : -num2;
    
  3. Ich denke, die Rekursion wird helfen. Schauen Sie sich diese Frage an

    So würde ich den Algorithmus von Euclid implementieren. (Vielleicht ist eine eigene Bewertung erforderlich):

    #include <iostream>
    #include <functional>
    
    using std::cin;
    using std::cout;
    using std::endl;
    using std::function;
    
    int main() {
    
        //Wrapped lambda expression. You can create a function that does the same thing.
        function<int(int,int)> gcd = [&](int m, int n){
            if(m<n) return gcd(n,m);
            int remainder(m%n);
            if(0 == remainder) return n;
            return gcd(n,remainder);
        };
    
        int num1,num2;
    
        cout << "Enter first number: ";
        cin >> num1;
        cout << "Enter second number: ";
        cin >> num2;
    
        //Check if user input is negative. 
        num1 = (num1 > 0) ? num1 : -num1;
        num2 = (num2 > 0) ? num2 : -num2;
    
    
        cout << "Greatest Common Divisor: " << gcd(num1,num2) << endl;
    
    }
    
Ähm ... wo ist "hcf" definiert? vnp vor 5 Jahren 0
@vnp oops, bearbeitet. Ich dachte an den höchsten gemeinsamen Faktor. Quaxton Hale vor 5 Jahren 1
Warum nicht "unsigned int" verwenden, wenn Sie keine negativen Zahlen zulassen möchten? Markus Mayer vor 5 Jahren 0
Ja, ich weiß, wofür 'hcf' steht. Ð £ Ñ ?? пех ов. vnp vor 5 Jahren 0
@ MarkusMayer Ich glaube nicht, dass das funktionieren wird. Wenn der Eingang negativ ist, wird er in UINT_MAX + 1 + num konvertiert. Quaxton Hale vor 5 Jahren 0
8
CashCow

Erstens, da dies für Code-Reviews gedacht ist, werde ich sofort darauf hinweisen, dass Sie alles in main setzen und den Algorithmus wirklich in seine eigene Funktion bringen sollten. Ihr main kann sich die Argumentliste ansehen und möglicherweise unterstützen, die Parameter dort zu haben. Für vereinfachte Begriffe können Sie sie verwenden, wenn sie vorhanden sind, und wenn nicht, werden Sie dazu aufgefordert.

Bei einer Implementierung der Funktion kann es sich um eine einfache freie Funktion handeln. Es ist nicht notwendig, eine Klasse dafür zu verwenden.

int gcd( int x, int y )
{
   if( x < y )
      return gcd( y, x );

   int f = x % y;
   if( f == 0 )
     return y;
   else
      return gcd( y, f );
}

ohne Rekursion

 int gcd( int x, int y )
 {
       if( x < y )
          std::swap( x, y );

       while( y > 0 )
       {
          int f = x % y;
          x = y;
          y = f;
       }
       return x;
 }  

Für ein einfaches Beispiel gcd von 987 und 1491

x takes the greater value so:
   x = 1491
   y = 987
   f (mod) = 504

next iteration
   x = 987
   y = 504
   f (mod) = 483

next iteration:
   x = 504
   y = 483
   f (mod) = 21

next iteration
   x = 483
   y = 21
   f( mod ) = 0

final:
   x = 21
   y = 0

return 21

Die Komplexität dieses Algorithmus: Nun, im schlimmsten Fall gibt es zwei aufeinanderfolgende Fibonacci-Zahlen. Die Antwort wird 1 sein, aber wenn dies die n-te und (n + 1) -te Fibonacci-Zahl ist, sind zur Entschlüsselung n Iterationen erforderlich.

Daher ist die O(log N)Komplexität, wenn N die höhere der beiden Zahlen ist.

5
Brythan

Ich werde auf Ihren ursprünglichen Algorithmus eingehen, da ich denke, dass es einige nützliche Lektionen gibt, die man dort lernen kann. Beachten Sie, dass EngieOP-Algorithmus als diese allerdings schneller sein wird.

Wenn Sie so etwas tun, denken Sie über die Richtung nach, in die die for-Schleife gehen soll. Sie wollen den größten gemeinsamen Divisor, aber Ihre for-Schleife beginnt mit dem kleinstmöglichen Divisor. Drehen Sie es herum und gehen Sie in die andere Richtung.

Beachten Sie auch, dass Sie wissen, dass der größte gemeinsame Teiler höchstens die kleinere der beiden Zahlen sein wird. Berechnen Sie also die kleinere Zahl.

for ( int divisor = std::min(first_number, second_number); divisor > 0; divisor-- ) {
    if ( 0 == first_number % divisor && 0 == second_number % divisor ) {
        cout << "Greatest Common Divisor (GCD):  " << divisor << endl;
    }
}

Beachten Sie, wie wir aufhören können, sobald wir das erste Spiel gefunden haben, weil wir vom kleinsten zum größten gingen. Dies erspart uns Schleifeniterationen, eine Variablendeklaration und eine if-Anweisung.

Die Verwendung von "std :: min ()" würde die Lesbarkeit Ihrer for-Schleife erheblich verbessern. Markus Mayer vor 5 Jahren 1
Ich würde in Betracht ziehen, diese [Yoda-Bedingungen] (http://2.bp.blogspot.com/-M61Y-VuCCSM/TtIQMTYPNrI/AAAAAAAAAGM/YtTOGRknF1s/s1600/yoda-conditions.jpg) zu beseitigen. Pharap vor 3 Jahren 0
3
vnp

In erster Linie möchten Sie kein Programm zum Berechnen schreiben gcd. Sie möchten eine Funktion schreiben, um sie zu berechnen, und ein Programm, um die Funktion zu testen. Legen Sie nicht alles hinein main.

Zweitens hat Euklid den Algorithmus sehr gut beschrieben. Es gibt (fast) keinen Grund, davon abzuweichen, wenn Sie nicht ernsthaft mit der Zahlentheorie befasst sind. Schau dir einen Ansatz von Stein an.

Der Rest ist in den obigen Antworten gut angesprochen.