| Autor |
Beitrag |
    
Mandy
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 17:53: | 
|
Ich brauche schnellstmöglich Hilfe bei der Bestimmung des Kettenbruchs zu 4711099/8022001, sowie den ggT von Zähler und Nenner. |
IQzero
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 20:12: |
|
Hi Mandy!
Die Koeffizienten der Kettenbruchentwicklung und den ggT liefert Dir die erweiterte Fassung des eukliedischen Algorithmus. Die einfache Fassung liefert nur den ggT.
Der Algorithmus funktioniert folgendermassen:
Du hast 2 Zahlen a und b, dann definiert man 4 Folgen a(n), q(n), x(n) und y(n) und eine Zählvariable i mit:
a(0):=a ; a(1):=b
x(0):=1 ; x(1):=0
y(0):=0 ; y(1):=1
i:=0
Die weiteren Folgenglieder berechnet man dann so:
q(i+1) := a(i) DIV a(i+1)
a(i+2) := a(i) MOD a(i+1)
x(i+2) := x(i) - q(i+1) * x(i+1)
y(i+2) := q(i) - q(i+1) * y(i+1)
danach erhöhst Du i um 1 und wiederholst das ganze bis a(i+1) Null geworden ist.
Mit deinen Zahlen a=4711099 und b=8022001 passiert das bei i=20.
Zur Kontrolle:
Ich habe als ggT(a,b) = 1 erhalten, die Zahlen sind also teilerfremd. Die sich ergebende Folge q(n) sind die Koeffitienten der Kettenbruchdarstellung von a/b .
Da habe ich folgendes Ergebnis erhalten:
0 / 1 / 1 / 2 / 2 / 1 / 2 / 1 / 7 / 1 / 6 / 1 / 9 / 5 / 1 / 1 / 2 / 1 / 4
Die Berechnungen habe ich mit EXCEL gemacht, die Tabelle ist recht einfach. Per Hand würde ich das jedenfalls nicht rechnen. Wenn Du Probleme damit hast, dann kann ich Dir die Tabelle auch mailen. Du müsstest dann Deine Adresse mit angeben wenn Du Dich das nächste Mal anmeldest.
P.S.: Das ist doch nicht Dein normaler Schulstoff, oder? Schreibst Du darüber eine Facharbeit? |
|
