3. ggt Funktioniert nicht

ggt Funktioniert nicht

  • ?
     

    #include <iostream>

using namespace std;

void Kuerzen(int *zaehler, int *nenner)
{
    int teiler;
    teiler = ggt(*zaehler, *nenner);
    *zaehler = *zaehler/teiler;
    *nenner = *nenner/teiler;
}

int main()
{
    int z=14;
    int n=6;
    Kuerzen(&z, &n);

    cout << z << " " << n << endl;

    system ("PAUSE");

    return 0;
}

    Hmm hab den Quellcode genaus so abgeschrieben wie er im Buch steht. Allerdings bekomme ich den Fehler, das mein Compiler ggt nicht kennt. (First use in this Function). Hmm funktioniert das nicht weil ich mit dem dev-cpp arbeite oder woran könnte das liegen?

    0
  • F

    Es gibt keine Standard ggt-Funktion die musst du auch noch schreiben!
    Etwa so:

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

    So hab mir jetzt einfach selbst eine Funktion dazu geschreiben. Sie sieht zwar nicht schön aus aber sie erfüllt ihren Zweck und das ist meiner erste selbsterdachte Formale 😃

    #include <iostream>

using namespace std;

// Teiler
int Teiler(int x, int y)
{
    unsigned int z;
    int k = 1;

    for (z=2;k==1;z++)
    {
        if(x%z==0 && y%z==0)
        {
                k=0;
        }
    }
    z--;

    return z;
}

// Kuerzen
void Kuerzen(int *zaehler, int *nenner)
{
    int teiler;
    int x = *zaehler;
    int y = *nenner;
    teiler = Teiler(x, y);
    *zaehler = *zaehler/teiler;
    *nenner = *nenner/teiler;
}

// Main
int main()
{
    int z=9;
    int n=3;
    Kuerzen(&z, &n);

    cout << z << " " << n << endl;

    system ("PAUSE");

    return 0;
}
    0
  • .

    FireFlow schrieb:

    Es gibt keine Standard ggt-Funktion die musst du auch noch schreiben!
    Etwa so:

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

    Eher so:

    template <typename T>
inline T gcd (T a, T b)
{
    return (b == 0) ? a : gcd (b, a % b);
}
    0
  • ?

    ich würd's ohne Rekursion machen (Stack-Overflow vermeiden) und im νorraus nur für positive Ganzzahlen festlegen:

    unsigned long gcd(unsigned long a, unsigned long b)
{
	unsigned long r;
	while ((r = a % b) != 0)
	{
		a = b;
		b = r;
	}
	return b;
}
    0
  • C
    Mod

    ist ein simpler fall von tail-rekursion. die erkennt praktisch jeder compiler. ein stackoverflow ist somit nicht das problem.

    0
  • N

    camper schrieb:

    ist ein simpler fall von tail-rekursion. die erkennt praktisch jeder compiler. ein stackoverflow ist somit nicht das problem.

    Das stimmt leider nur bedingt. Folgendes Test-Programm funktioniert mit VC++ 7.1 und VC++ 8.0 beta 2 nur falls man den Release-Modus eingeschaltet hat und mit g++ 3.4.4 erst ab -O2

    #include <iostream>

using namespace std;

int test(int a)
{
	return a>1000000? a : test(a+1);
}

int main()
{
	cout << test(0) << endl;
	cin.get();    
}

    Wenn man also ein Programm, das eine solche Funktion verwendet, debuggen will, Pustekuchen.

    0
  • V

    camper schrieb:

    ist ein simpler fall von tail-rekursion. die erkennt praktisch jeder compiler. ein stackoverflow ist somit nicht das problem.

    ergebnis richtig, begründung nicht ganz.

    ich behaupte, daß keine tail recursion optimiert wird, wenn die optimierungen zu debug-zwecken gar nicht an sind. nicht nur zu debugzwecken, manchemal haben leute auch mit -O3 schlechte erfahrungen und machen immer zuerstmal ohnbe optimierungen und nur wenn das geht, probieren sie mal zaghaft -O1 oder -O2. also wollen wir doch so nett sein, c++-code, der aich auf solche optimierung verläßt, als falsch zu erklären.

    und nur zu einer alternativen begründung:
    aus A,B wird in einem durchlauf B,A%B und in einem weiteren durchlauf A%B,...
    nun ist der wert von A%B höchstens halb so groß wie A. also halbiert sich die größe von A mindestens jeden zweiten durchlauf und die maximale anzahl der durchläufe ist sowas wie log2(a)*2, was bei nem 64-bit-typ gerademal 128 durchläufe macht. bzw verschachtelungen, und 128 verschachtelungen sind als unproblematisch anzusehen.

    0
  • ?

    Die rekursive Version des Euklid-ggt braucht zwar relativ wenige Verschachtelungen, aber wenn sie an einer Stelle aufgerufen wird, die bereits eine hohe Verschachtelungstiefe aufweist, kann sogar das zuviel sein. Rekursion, die der Compiler gegebenenfalls wegoptimieren kann, ist in der Regel leicht im νorraus als Iteration codierbar und man kann sich darauf verlassen, auch ohne automatische Optimierung, Laufzeitstack und Zeit kostende Funktionsaufrufe zu sparen. Schwieriger wird es bei Fällen wie z. Bsp. dem Durchlaufen beliebig verschachtelter Strukturen. Dort kann man die Rekursion wegoptimieren, indem man einen Stack auf dem Heap anlegt und die nötigen Daten im Laufe der Iterationen darüber verwaltet.

    0
Anmelden zum Antworten