Euklidischer Algorithmus

hotplugger

Hallo!!!!

Ich bin neu hier im Forum, und weiß auch nicht ob ich das hier richtig poste. Falls es falsch ist, bitte verzeiht mir. Ich habe heute ne Schulaufgabe gekriegt, bin also nur C++ Schulprogrammierer, und muss dort alle Brüche die es gbt ausrechnen lassen, d.h. Div, Sub, Mult, Add...

Das ist soweit kein Problem, siehe Quelltext...

struct bruch
{      int z;
       int n;
};
bruch einbruch()
{     bruch h;
      cout << "\nZähler: "; cin >> h.z;
      do 
      {cout << "\nNenner: "; cin >> h.n;}
      while (h.n==0);                   
      return h;
}
void ausbruch (bruch ab)
{    cout << ab.z << "/" << ab.n;
}
unsigned int ggT (unsigned int z, unsigned int n)
{    if (!n||!z) return 0;
     while (n)
     { if (z>n) {z+=n;n=z-n;z-=n;}
       n-=z;
       }
       return z;  
}
bruch mul (bruch f1, bruch f2)
{    bruch h;
     h.z=f1.z*f2.z;
     h.n=f1.n*f2.n;
     return h; 
}
bruch div (bruch f1, bruch f2)
{    bruch h;
     h.z=f1.z*f2.n;
     h.n=f1.n*f2.z;
     return h; 
}
bruch add (bruch f1, bruch f2)
{    bruch h;
     h.n=f1.n*f2.n;
     h.z=(f1.z*(h.n/f1.n))+(f2.z*(h.n/f2.n));
    return h; 
}
bruch sub (bruch f1, bruch f2)
{    bruch h;
     h.n=f1.n*f2.n;
     h.z=(f1.z*(h.n/f1.n))-(f2.z*(h.n/f2.n));
     return h; 
}
int main()
{   bruch f1, f2, p;
    cout << "Eingabe 1. Bruch: \n";
    f1 = einbruch();
    cout << "\nEingabe 2. Bruch: \n";
    f2 = einbruch();
    cout << "\nMultiplikation mit diesen Brüchen: \t" ;
    ausbruch (f1); cout << " * ";
    ausbruch (f2); cout << " = ";
    p=mul (f1, f2);
    ausbruch (p); cout << endl;
    cout << "\nDivision mit diesen Brüchen: \t\t" ;
    ausbruch (f1); cout << " / ";
    ausbruch (f2); cout << " = ";
    p=div (f1, f2);
    ausbruch (p); cout << endl;
    cout << "\nAddition mit diesen Brüchen: \t\t" ;
    ausbruch (f1); cout << " + ";
    ausbruch (f2); cout << " = ";
    p=add (f1, f2);
    ausbruch (p); cout << endl;
     cout << "\nSubtraktion mit diesen Brüchen: \t" ;
    ausbruch (f1); cout << " + ";
    ausbruch (f2); cout << " = ";
    p=sub (f1, f2);
    ausbruch (p); cout << endl;
  getchar();
  return 0;
}

Soweit so gut. Nun stehe ich aber vor einem Rätsel und zwar. Wie kann man die Brüche kürzen..........

Mein Lehrer meinte es geht mit dem Euklidischen Algorithmus..
Der sieht wie folgt aus:

unsigned int ggT (unsigned int z, unsigned int n)
{    if (!n||!z) return 0;
     while (n)
     { if (z>n) {z+=n;n=z-n;z-=n;}
       n-=z;
       }
       return z;  
}

Leider, habe ich dies überhaupt nicht kapiert, weder was dort vorgeht noch wie ich das drauf anwenden soll...

Könnt ihr mir vielleicht einen Tip geben?

Danke im voraus schonmal, ich versuchs schon ne ganze Weile, komm aber irgendwie nicht weiter....

:(I

was kapierst du denn nicht? alles? etwas? ein bisschen was?

ps: wenigstens ist die formatierung des quelltextes astrein

Jester

Der euklidische Algorithmus berechnet den ggT von zwei Zahlen. Nimm das zunächst einfach mal so hin. Kannste mit der Information einen Bruch kürzen?

hotplugger

Raiser: derobere Quelltext ist von MIR. das heißt den habe ich kapiert.

jester: anfangen kann ich was damit, dann muss ich das doch aber in die funktionen mul und so weiter einarbeiten oder?

damit der bei der berechnung, gleich kürzt...?!

CStoll

Kürzen kannst du am besten mit (x)/(y) == (x/ggT(x,y))/(y/ggT(x,y)).

hotplugger

bruch mul (bruch f1, bruch f2)
{    bruch h;
     h.z=f1.z*f2.z;
     h.n=f1.n*f2.n;
     h.z=h.z/ggT(h.z,h.n);
     h.n=h.n/ggT(h.z,h.n);
     return h; 
}

ich habs jetzt so gemacht.
bei der erste zahl, dem zähler funzt es...
bei der zweiten jedoch nicht. der teilt die nicht...

ich werd noch bekloppt

hotplugger

CStoll schrieb:

Kürzen kannst du am besten mit (x)/(y) == (x/ggT(x,y))/(y/ggT(x,y)).

haha, das war mein denkfehler

dankE!!!!! ich bin vielleicht doch nicht so blöd!

danke cstoll

edit: laut meinem post oben müsste es doch gehen....tuts aber nicht.....warum nur? ich hab doch nichts anderes geschrieben als du, oder?

CStoll

Du solltest dir das ggT zwischendurch merken - durch die Zuweisung ändern sich die Werte und damit wird ein anderer Teiler (=1) berechnet.

int t=ggT(h.z,h.n);
h.z/=t;
h.n/=t;

hotplugger

Ok, das ist einleuchtend. Aber dadrauf wäre ich nie gekommen!
Vielen vielen Danke für deine/eure Hilfe, ich werd mich hier nochn bisschen umschauen und hoffe das ich irgendwem auch mal helfen kann.

Danke nochmal