Algorithmus des Euklid auf unübliche Art und Weise



  • Guten Abend!
    Für mein Studium wurde ich mit einer Aufgabe konfrontiert, die mir aufgrund des überhaupt nicht vorhandenen Vorwissens doch einige Schwierigkeiten bereitet. Ich habe mich nun den ganzen Nachmittag und Abend mit C beschäftigt und immerhin schon mal ein kleines Programm schreiben können, sodass mir zumindest einige der grundlegenden Begriffe schon geläufig sind.
    Aufgabe ist es, ein Programm zu schreiben, das den größten gemeinsamen Teiler zweier ganzer Zahlen berechnet. Über Google bin ich auf viele Seiten mit Beispielen gestoßen, alle benutzen aber im Prinzip nur eine Folgerung aus dem euklidischen Algorithmus so wie wir ihn in der Vorlesung vorgestellt bekommen haben und diese Folgerung möchte ich nicht verwenden, da sie für uns erstmal noch nicht bewiesen ist.

    Nach folgendem Schema haben wir bisher den ggT bestimmt:
    Man nehme zwei Zahlen a und b und wende folgende Schritte an:
    1. c=a-(a/b)*b (Division ohne Rest, wie auch in C bei gleicher Schreibweise!)

    Falls c 0 ergibt, ist b der ggT, ansonsten geht es mit der gleichen Formel weiter, wobei a und b neu definiert werden:

    2. a':=b, b':=c

    Die Formel aus 1. wird nun mit den neuen Werten angewendet. Die Anwendung der Formel und anschließende Neudefinition von a und b findet nun solange statt, bis c=0. Hier endet der Algorithmus und der ggT ist b.

    Hier nun mein Versuch, das ganze in C umzusetzen:

    #include<stdio.h>
    #include<conio.h>
    unsigned int main ()
    {
    	unsigned int a,b,c;
    	scanf("%d",&a);
    	scanf("%d",&b);
    	c=a-(a/b)*b;
    	if (c=0)
    	{
    		printf("ggT:%d",b);
    	}
    	else 
    	{
    		while (c!=0)
    		{	
    		c=a-(a/b)*b;
    		a=b;
    		b=c;
    		}
    	printf("%d",b);
    	}
    	getch();
    }
    

    Ich erhalte zudem folgende Fehlermeldungen, die ich nicht wirklich loswerde:

    1. Ungültiges 'else' ohne zugehöriges 'if'

    (Ich habe doch oben ein 'if'?)

    2. Dateiende erreicht, bevor das zugehörige Element für das linke Element Klammer "{" in "c:\users\...." gefunden wurde

    Den Meisten von euch wird sich so wahrscheinlich schon bei Ansicht des Codes der Magen umdrehen, ich hoffe, ihr könnt es einem Neuling nachsehen und vielleicht konstruktive Hilfen geben, wie ich die Fehlermeldungen loswerde und was am Code evtl. noch geändert werden muss um die Vorgabe umzusetzen.

    Vielen Dank im Voraus!



  • Der logische Fehler ist behoben durch
    printf("%d",a);
    Über die Rückgabe der main-Funktion, daß zu jeder { eine } gehört und = in Vergleichen mag ich gerade nicht ausführlich schwadronieren.



  • Danke für die schnelle Antwort!
    Wo habe ich den printf-Befehl dann einzufügen? Und lässt sich das nicht vermeiden? Eine Ausgabe von a ist für den Benutzer eigentlich uninteressant bzw. verwirrend. Bei den { und } zähle ich jeweils 4, dass sie paarweise zusammengehören, ist mir schon klar, aber so verstehe ich nicht, wo hier der Fehler liegt.



  • Therminator schrieb:

    Den Meisten von euch wird sich so wahrscheinlich schon bei Ansicht des Codes der Magen umdrehen

    Wieso nicht rekursiv?



  • Terminator schrieb:

    Ich erhalte zudem folgende Fehlermeldungen, die ich nicht wirklich loswerde:
    ...

    Ich eher diese:

    main.c:3: Warnung: Rückgabetyp von »main« ist nicht »int«
    main.c: In Funktion »main«:
    main.c:6: Warnung: format »%d« erwartet Typ »int *«, aber Argument 2 hat Typ »unsigned int *«
    main.c:7: Warnung: format »%d« erwartet Typ »int *«, aber Argument 2 hat Typ »unsigned int *«
    main.c:9: Warnung: Um Zuweisung, die als Wahrheitswert verwendet wird, werden Klammern empfohlen
      (siehe volkard)
    


  • Falsch war auch z.B. if(c=0) was gerne if(c==0) oder if(!c) heißen wollte.

    int main()
    {
      unsigned long a,b,c;
      scanf("%lu",&a);
      scanf("%lu",&b);
      do {
        c=a-(a/b)*b;
        a=b;
        b=c;
      }
      while( c );  /* äquivalent zu while( c!=0 ); */
      printf("%lu",a);
      return 0;
    }
    

    Schmeiße mal den ganzen conio-Nichtstandard-Schrott raus.



  • Terminator schrieb:

    c=a-(a/b)*b;
    

    Umständlich, besser c = a % b; ;

    Wutz schrieb:

    int main()
    

    main() mit beliebigen Argumenten?

    Warum nicht so?

    #include <stdio.h>
    
    void clearbuf(void)
    {
        int c;
        while ((c = getchar()) != EOF && c != '\n')
            ;
    }
    
    unsigned int ggt(unsigned int a, unsigned int b)
    {
        if (b) return ggt(b, a % b);
        else return a;
    }
    
    int main(void)
    {
        unsigned int a, b;
        scanf("%u", &a); clearbuf();
        scanf("%u", &b); clearbuf();
        printf("%u", ggt(a, b));
    }
    


  • @Therminator: Studierst du zufällig an der TU Braunschweig? 😃


Log in to reply