kgv und ggt



  • kennt ihr einen besonders schnellen Algorithmus um das kgv und den ggt von zwei Zahlen zu bestimmen?



  • der "euklidische algo". damit kriegste ggt(a,b) raus. und kgv ist dann einfach a*b/ggt(a,b).



  • volkard rules



  • danke



  • also rekursiv sollte das ca. so aussehen, oder?

    int ggt(int a, int b)
    {
        if (b==0)
            return a;
        else
            return ggt(b, a%b);
    }
    


  • jo, solange du dafür sorgen kannst, daß a>=b ist beim aufruf.



  • ist aber lahm! Nimm besser den binären euklid. Alg.!



  • und wie wärs mit diesem algorithmus:
    (ich denke, er ist insofern schneller, weil a%b und b%a, und nicht nur eins von beiden)

    // greatest common divisor
    long gcd(long a,long b)
    {
        if(a<0)
            a=-a;
        if(b<0)
            b=-b;
    
        for(;;)
        {
            if(a==0) // trap if a==0
                return b;
            b%=a; // otherwise here would be an error
            if(b==0) // trap if b==0
                return a;
            a%=b; // otherwise here would be an error
        }
    }
    


  • schneller und mit der selben einschränkung.
    mir wäre es da lieber, auf a>=b zu testen, als auf a<0 und b<0. dafür lieber unsigned als typ nehmen, damit der aufrufer weiß, daß hier keine minuszahlen reinsollen. was aber sehr gut war, ist, daß die rekursion weg ist. die schleife ist viel schneller.



  • Eine Iterative Lösung ist:

    while (y!=0) {
    z=x%y;
    x=y;
    y=z;
    }

    Der ggt steht dann in x



  • Meine lösung war auch iterativ 😃
    wenn ich nur unsigned typen übergebe, dann brauche ich doch gar nicht auf a>=b zu testen..
    Hier die verbesserte Version:

    // greatest common divisor
    long gcd(unsigned long a,unsigned long b)
    {
        for(;;)
        {
            if(a==0) // trap if a==0
                return b;
            b%=a; // otherwise here would be an error
            if(b==0) // trap if b==0
                return a;
            a%=b; // otherwise here would be an error
        }
    }
    


  • Original erstellt von Gary:
    wenn ich nur unsigned typen übergebe, dann brauche ich doch gar nicht auf a>=b zu testen..

    in der tat. der test hat mich immer gestört. ich behalt mir mal deine lösung, weil sie ohne den test auskommt.



  • Edit by SideWinder: Hier stand Mist den ein Thread-Aufwärmer geposted hat.



  • volkard schrieb:

    was aber sehr gut war, ist, daß die rekursion weg ist. die schleife ist viel schneller.

    Huch? Das ist doch ne Endrekursion. Das sollte dieselbe Geschwindigkeit ergeben wie bei ner Schleife.



  • Und es ist schon 7 Jahre her ...



  • habe dieses Programm für berechnung des ggT

    Jedoch habe ich das problem mit dem cout es wird mir als fehlermeldung nicht deklariert angezeigt. Wo ist det fehler versteckt?
    Danke ihm Voraus

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>

    int main(int argc, char *argv[])

    {

    int ggT( int a , int b);
    int a , b ;

    printf ("Gib einen beliebigen Integer ein :\n");
    scanf ("%d",& a);

    printf ("Gib den zweiten beliebigen Integer ein:\n");
    scanf ("%d",& b);

    int ggt = ggT(b, a%b);
    cout<< "ggT von " << a << " und " << b << " ist " << ggt << endl;
    return 0;

    }

    int ggT(int a, int b) {
    if( b==0)
    return a;
    else
    ggT(b, a%b);
    }



  • 1. Falsches Unterforum.
    2. Zu alter Thread.
    3. Codetags vergessen.
    4. Problem hat nichts mit dem Algorithmus zu tun.
    5. cout ist in iostream drin.
    6. using namespace std; nicht vergessen.

    6 Sachen, die mich stören - das hab' selbst ich nicht alle Tage.



  • Hej Leute,

    fange auch grad an zu programmieren und hatte die letzten Tage Kopfschmerzen wegen GgT und kgT. Eure Lösungsansätze waren aber noch ausserhalb meines Verständnisses, also hab ich etwas einfacheren Code verwendet, aber ist eben umständlicher:

    #include <iostream>

    using namespace std;

    int main()
    {
    int Zahl1;
    int Zahl2;
    int GrosseZahl;
    int KleineZahl;
    int Rest1;
    int Rest2;
    int i1;
    int Rest3;
    int Rest4;
    int RestENDE1;
    int RestENDE2;
    int i2;
    int Eingabe;

    cout << "Programm zur Berechnung des kleinsten gemeinsamen Teilers und des groessten gemeinsamen Teilers zweier Zahlen." << endl<<endl;
    cout << "Geben Sie zwei Zahlen ein!"<<endl<<endl;
    cout<<"Zahl1: "; cin>> Zahl1;cout<<endl;
    cout<<"Zahl2: ";cin>> Zahl2;cout<<endl;
    if (Zahl1<Zahl2) {GrosseZahl=Zahl2;KleineZahl=Zahl1;}
    else {GrosseZahl=Zahl1;KleineZahl=Zahl2;};
    i2=2;
    i1=GrosseZahl;

    for (i1=GrosseZahl;i1>=KleineZahl;i1--)
    {
    Rest1=(GrosseZahl % i1);
    Rest2=(KleineZahl % i1);
    RestENDE1=Rest1+Rest2;
    if (RestENDE1==0) {cout<<"Der groesste gemeinsame Teiler ist: "<<i1<<endl<<endl;i1=0;
    } }
    if (RestENDE1 != 0) {cout<<"Es gibt keinen groessten gemeinsamen Teiler ausser 1."<<endl<<endl;}

    for (i2=2;i2<=KleineZahl;i2++)
    {
    Rest3=(GrosseZahl % i2);
    Rest4=(KleineZahl % i2);
    RestENDE2=Rest3+Rest4;
    if (RestENDE2==0) {
    cout<<"Der kleinste gemeinsame Teiler ist: "<<i2<<endl<<endl;i2=GrosseZahl;
    }
    }
    if (RestENDE2 != 0) {cout<<"Es gibt keinen kleinsten gemeinsamen Teiler ausser 1."<<endl<<endl;}

    cin>>Eingabe;
    return 0;

    }

    hoffe, dass es trotzdem jmd. etwas bringt, der vielleicht gerade anfängt....

    Lg,
    Micha



  • Micha1984 schrieb:

    Eure Lösungsansätze waren aber noch ausserhalb meines Verständnisses,

    Hast du Probleme mit der Mathematik oder dem Programmieren?

    Micha1984 schrieb:

    also hab ich etwas einfacheren Code verwendet, aber ist eben umständlicher:

    Das widerspricht sich (und er ist nicht einfacher, aber umständlich).

    Und es gilt auch für dich:

    Glühbirne schrieb:

    2. Zu alter Thread.
    3. Codetags vergessen.


Log in to reply