Bruch maximal kuerzen mit Programm?

Wissenschaft Mathematik
#1

Oehm ya ich soll mit einem Programm z.B 2 Brueche addieren und dann maximal kuerzen. Dabei gehe ich wie folgt vor und wuerde gern erfragen, ob das klappt:

Erstmal multipliziere ich die Nenne miteinander sowie die Zaehler mit dem jeweils anderen Nenner, um die Brueche auf einen Hauptnenner zu bringen.

Zwischenfrage 1: Ist das okay, dass der neue Nenner [irgend]ein Vielfaches der Nenner ist und nicht das KgV?

Nun werden die Brueche mit Hilfe das Hauptnenners addiert und es geht ums kuerzen:

Eine Schleife wird durchlaufen von 2 bis über 9000!! und bei jeder Zahl wird geprueft, ob sich sowohl Zaehler und nenner dadurch teilen lassen. Falls ja, dann wird geteilt und der neue Bruch durchlaeuft dieselbe Schleife von vorne.

Klappt das so? Hab ich irgendwo was unvollstaendlich/unverstaendlich gesagt? Bitte um Rueckmeldung.

Anm. d. Red: Ich weiss, dass es guenstiger waere, lediglich Primzahlen zu durchlaufen anstatt alle Zahlen.

#2

Oehm ya

Ein freundliches Hallo zurück,

Anm. d. Red: Ich weiss, dass es guenstiger waere, lediglich
Primzahlen zu durchlaufen anstatt alle Zahlen.

und noch viel günstiger wäre es, einfach mit dem ggT zu arbeiten, genauer: den ggT der beiden Nenner zu bestimmen und sogleich beide Nenner durch den ggT zu teilen, damit sie so klein wie möglich werden. Das Weitere darfst Du Dir selbst überlegen.

Ein voll cooles ebenso simples wie effizientes Verfahren zur Berechnung des ggT ist übrigens seit mehr als 2000 Jahren bekannt. Es heißt Euklidischer Algorithmus.

Schönen Sonntag
Martin

#3

Oehm ya ich soll mit einem Programm z.B 2 Brueche addieren und
dann maximal kuerzen. Dabei gehe ich wie folgt vor und wuerde
gern erfragen, ob das klappt:

Generell ist die Frage schon richtig gestellt. Ein Programm soll funktionieren und nicht durch „elegante“ Optimierungen das letzte bisschen Performance rauskitzeln.

Dafür haben wir ja Computer, dass sie für uns rechnen, nicht wir für sie denken.

AAABER: Ein Programm muss auch in angemessener Zeit fertig werden. Wenn du mit 17stelligen Zahlen rechnest, kannst du evtll. das Ergebnis zum Renteneintritt genießen - falls es dann noch Renten gibt.

Erstmal multipliziere ich die Nenne miteinander sowie die
Zaehler mit dem jeweils anderen Nenner, um die Brueche auf
einen Hauptnenner zu bringen.

Zwischenfrage 1: Ist das okay, dass der neue Nenner
[irgend]ein Vielfaches der Nenner ist und nicht das KgV?

Meiner Meinung ja, denn um das KgV zu bestimmen, musst du ja (fast) genau das machen, was du später ohnehin tust: Teilbarkeiten bestimmen.

Also hast mur 1 mögliche Fehlerquelle, statt 2.

Nun werden die Brueche mit Hilfe das Hauptnenners addiert und
es geht ums kuerzen:

Wenn ich mich recht erinnere, ja.

Eine Schleife wird durchlaufen von 2 bis über 9000!!

Meinst du 9000-Fakultät? Also 1*2* … *9000?
Dann wird das mit der Rente kritisch. und 9000 als Grenze würde für Zahlen bis 9000*9000 reichen, also 81 Mio.
Scheint mit eine unnötige Grenze zu sein.

und bei
jeder Zahl wird geprueft, ob sich sowohl Zaehler und nenner
dadurch teilen lassen. Falls ja, dann wird geteilt und der
neue Bruch durchlaeuft dieselbe Schleife von vorne.

Das Verfahren ist zwar einfach und dürfte funktionieren, aber ein bisschen Nachdenken musst du schon, wegen Performance:

Zunächst solltest du mal prüfen, ob der Zähler wesentlich kleiner als der Nenner ist. Bei 2/521584564654651 weiß man sofort, dass nicht weiter gekürzt werden kann.

Außerdem hast du ja noch die ursprünglichen Nenner. Der Gesamtnenner kann ja keine Faktoren enthalten, die dort nicht schon vorkommen.

Beispiel: a/b + c/d = a*d+c*b/b*d

Ein Faktor kann nie größer sein als Wurzel(b) und Wurzel(d).

UND: Ein Faktor kann natürlich mehrfach vorkommen, aber eine Zahl, die beim ersten Durchlauf kein Faktor ist, ist es auch beim zweiten nicht. Wenn du z.B. beim ersten Durchlauf die 7 als Faktor ermittelst, musst du beim zweiten nur die Sieben und die >7 prüfen, usw.

Anm. d. Red: Ich weiss, dass es guenstiger waere, lediglich
Primzahlen zu durchlaufen anstatt alle Zahlen.

Aber um die Primzahlen zu bestimmen, ist wahrscheinlich mehr Aufwand nötig als für „stupides“ Durchprobieren.

Dann viel Spaß, Zoelomat

#4

Hi.

Eine Schleife wird durchlaufen von 2 bis über 9000!!

Meinst du 9000-Fakultät? Also 1*2* … *9000?

Wurde ja eigentlich alles wesentliche schon gesagt. Nur zu dieser Sache nochwas: Das ist eine Anspielung auf eine bescheuerte Szene in der Manga/Comic/Wieauchimmermansnennt-Serie „Dragonballz (Z?)“. In der Szene guckt ein Typ auf ein kleines Gerät und liest irgendwelche Kampfkraftwerte ab. Minutenlang. Und irgendwann schreit er sowas wie „Es ist über 9000!!!“. Findet man bei Youtube recht schnell. Suchwörter: Dragonballz over 9000

Dann viel Spaß, Zoelomat

#5

Hossa :smile:

Erstmal multipliziere ich die Nenne miteinander sowie die
Zaehler mit dem jeweils anderen Nenner, um die Brueche auf
einen Hauptnenner zu bringen.

Du addierst sozusagen „über Kreuz“, also:

\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}

Zwischenfrage 1: Ist das okay, dass der neue Nenner
[irgend]ein Vielfaches der Nenner ist und nicht das KgV?

Ja, ist ok.

es geht ums kuerzen:

Eine Schleife ist sehr zeitaufwändig. Um zu prüfen, durch welche Zahlen n eine Zahl z teibar ist, musst du ja für n alle Primzahlen von 2 bis Wurzel(z) einsetzen. Das kann dauern. Besser ist es daher, den sog. Euklidischen Algorithmus zu nutzen. Dieser basiert auf folgender Eigenschaft des ggT:

ggT(a, b) = ggT(b, a mod b)

„a mod b“ ist der Rest der Division von a durch b. In den C-ähnlichen Programmiersprachen wird diese Rechenoperation durch ein Prozent-Zeichen symbolisiert.

Beispiel:

ggT(168, 32) = ggT(32, 8) = ggT(8, 0) = 8

Das Verfahren endet, sobald das zweite Argument gleich 0 ist. Der ggT ist dann das erste Argument. Du kannst diese Funktion ganz leicht rekursiv implementieren:

ggT(a, b)
{ if (0==b) return a;
 return ggT( b, a%b );
}

Natürlich kannst du die Rekursion auch auflösen:

ggT(a, b)
{ while (b!=0)
 { r= a&b; /Rest der Division
 a= b;
 b= r;
 }
 return a;
}

Viele Grüße

Hasenfuß

#6

Danke schoen
Die Antworten waren hilfreich