Python :: Aufgabe #150

1 Lösung Lösung öffentlich

Endliche Kettenbrüche rationaler Zahlen

Anfänger - Python von hollst - 30.03.2017 um 11:10 Uhr
Mit einem Kettenbruch K = a0 + 1/(a1 + 1/(a2 + 1 /(....))) - mit a0 als ganze Zahl und a1, a2 ... als
positve natürliche Zahlen ungleich Null - lässt sich bekanntlch jede reelle Zahl darstellen.
In der Praxis sind Kettenbrüche etwas unhandlich und man bevorzugt die Schreibweise
K = [a0; a1, a2, a3 ...]. Ist der Kettenbruch endlich, können damit alle rationale Zahlen beschrieben werden.

Die meisten Anwendungen finden Kettenbrüche in der Zahlentheorie, aber auch für Informatiker können sie
nutzbringend sein, insbesondere wenn man Rundungsprobleme umgehen muss. Z. B.

Quellcode ausblenden C#-Code
Double x = 1.0E+15 + 1.0 / 3;
WriteLine(x.ToString());
WriteLine((x / 1.0E+15).ToString());


gibt als Ergebnisse 1E+15 und 1 hervor. Der Term (1.0 / 3) wird ohne jegliche Vorwarnung einfach verschluckt
und man bekommt gegebenenfalls am Ende einer Rechnung völligen Unfug heraus, ohne es zu merken
(einer der schlimmsten Fallstricke für den Programmierer).

Würde man x als Kettenbruch darstellen

x = 3.000.000.000.000.001 / 3 = [1.000.000.000.000.000; 3]

blieben alle Informationen erhalten und die Welt wäre wieder in Ordnung.

Nun, wir wollen keine komplette Algebra mit Kettenbruchobjekten entwickeln,
sonder lediglich folgende Aufgabenstellungen lösen:

Schreibe ein Programm, das

1.) zwei Zahlen (ZAEHLER und NENNER mit NENNER != 0) entgegennimmt
und eine entsprechende Kettenbruchdarstellung zurückgibt und

2.) diese Kettenbruchdarstellung wieder rücktransformiert.

Das Interessante an Teilaufgabe 2.) ist, dass sich der Bruch ZAEHLER/NENNER
automatisch selbst kürzt, also z. B. ZAEHLER = 50 und NENNER = 100 -> [0; 2],
rücktransformiet führt dies richtig zu ZAEHLER = 1 und NENNER = 2. Bei negativen
Zahlen ist allerdings nicht entscheidbar, ob der ZAEHLER oder der NENNER negativ ist
(möglicherweise ein neuer Fallstrick, das Programmiererleben ist manchmal sehr schwer).

Lösungen:

vote_ok
von nitnat (670 Punkte) - 26.01.2018 um 19:57 Uhr
Quellcode ausblenden Python-Code
def frame():

    kb=[]
    kb_inv=[]
    
    def kbruch(a,b):
        if ((a%b)!=0):
            kb.append(a//b)
            kbruch(b, a%b)
        else:
            kb.append(int(a/b))
            return  

    def kbruch_inv(i,b,q):
        if i==0:
            return 
        else:
            a = kb[i-1]*b+q
            kb_inv.append((a,b))
            kbruch_inv(i-1,a,b) 
           
    z=int(input("Bitte gib einen ganzzahligen Zähler ein:          "))
    n=int(input("Bitte gib einen ganzzahligen Nenner (!=0) ein:    "))

    if n==0:
        print ("ICH HAB GESAGT KEINE 0 IM NENNER!!11einself")
        print ("Also nochmal von vorne..")
        frame()
    elif z==0:
        print ("Tja, 0 geteilt durch ", n, " ist 0, beziehungsweise [0].")
        print ("Also nochmal von vorne..")
        frame()
    
    kbruch(z,n)
    kbruch_inv(len(kb)-1,kb[len(kb)-1],1)
       
    print("")
    print(z,"/",n," = ",kb)
    print("=", z/n)
    print("")
    print("Zähler: ",kb_inv[len(kb_inv)-1][0], ", Nenner: ",kb_inv[len(kb_inv)-1][1], "(rückwärts berechnet..)")
    
frame()

while input("Weiter rechnen? Gib 'JA' ein.. (sonst beendet sich das Programm..)")=="JA":
    frame()
1800902

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.