Ägyptische Bruchrechnung

3 Lösungen

#238

Fortgeschrittener - Python von hollst - 22.12.2019 um 22:50 Uhr

Gegeben seien zwei positive Ganzzahlen Z (wie Zaehler) und N (wie Nenner) mit N > Z
und Z sei kein Teiler von N.

Der Bruch Z/N ist immer als Summe der Kehrwerte positiver Ganzzahlen (Stammbrüche) darstellbar,
wobei es meist mehrer Möglichkeiten der Darstellung gibt.

Beispiele:

5/6 = 1/2 + 1/3 = 1/2 + 1/4 + 1/12 = 1/2 + 1/4 + 1/13 + 1/156 = ...

17/39 = 1/3 + 1/10 + 1/390 = ...

Man schreibe ein Programm, das Z und N entgegennimmt und die Zahlen der Stammbrüchesumme mit den wenigsten Summanden ausgibt.

Also obere Beispiele:

Input 5 und 6, Output 2 und 3,
Input 17 und 39, Output 3, 10 und 390.

Viel Spaß.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von satn1241 (3090 Punkte) - 02.04.2020 um 15:07 Uhr

Python-Code

def kgv(Zahl1, Zahl2):
    while True:
        i = 1
        while True:
            d = i * Zahl1
            r2 = d % Zahl2
            if r2 == 0:
                break
            i += 1
        break
    return d

def ggt(zahl1, zahl2):
    while zahl2!=0:
        c=zahl1%zahl2
        zahl1=zahl2
        zahl2=c
    return zahl1

# Code Ägyptische Bruchrechnung
# Eingabe
print("Wilkommen bei der ägyptischen Bruchrechnung. Der Nenner muss hier größer als der Zähler sein!")
zaehler = int(input("Gib einen Zaehler ein:   "))
nenner = int(input("Gib einen Nenner ein:   "))
# Prüfe, ob der Bruch gekürzt werden kann
ggt_neu = ggt(zaehler, nenner)
if ggt_neu != nenner:
    zaehler = zaehler / ggt_neu
    nenner = nenner / ggt_neu
   
bruch = zaehler/nenner   
nenner_neu = nenner//zaehler+1 

while True:
    # Prüfe, ob der Bruch schon gekürzt wurde
    if zaehler ==1:
        break
    # regulärer Algorithmus
    print("Ein Stammbruch ist: 1/"+ str(int(nenner_neu)))
    nenner = kgv(nenner_neu, nenner)
    rest = round((bruch - 1/nenner_neu)*nenner,0)  
    nenner_neu = nenner//rest+1     
    bruch = rest/nenner      
    if rest ==1:
        break
print("Ein Stammbruch ist: 1/"+ str(int(nenner)))