Das in der Aufgabe verwendete Schema ist der sogenannte Stern-Brocot-Baum. Er wird in der Numerik verwendet, um reelle Zahlen durch Brüche zu approximieren. Interpretiert man die beiden Zahlen an jedem Knoten als Bruch, so bilden alle Knoten von links nach rechts eine streng monoton aufsteigende Folge von Brüchen. Alle Brüche liegen in bereits gekürzter Form vor.
Das heißt, wenn ich eine bestimmte reelle Zahl approximieren möchte, muss ich mir nur merken welche beiden Brüche zuletzt links bzw. rechts von der gesuchten Zahl liegen. Die nächst bessere Approximation ergibt sich dann durch Addition der beiden Zähler und der beiden Nenner. Ist der neue Bruch größer als die gesuchte Zahl, muss ich nach links gehen. Ist er kleiner - nach rechts.
Den ersten Bruch 22/7 erreicht man auf diesem Weg:
Statt Brüchen hab ich die einzelnen Zweige als Punkte in 2D aufgefasst. Somit hab ich die Suche nach den beiden Zielpunkten immer weiter eingrenzen können, indem ich mir immer jeweils 2 Halbgeraden gezeichnet hab, so nach dem Motto: Was passiert, wenn ich ab einem Punkt X nur noch stets weiter nach links bzw. nur noch stets weiter nach rechts gehe. Liegt dann der Zielpunkt zwischen oder gar auf einer der beiden Halbgeraden, ist der bisher eingeschlagene Weg via Punkt X offensichtlich der Richtige. So kann man die Suche immer weiter führen, bis irgendwann der Zielpunkt auf einer Halbgeraden liegt. Ich hoffe, das war einigermaßen verständlich...?
Ich wusste nicht, dass es ein Stern-Brocot-Baum ist. Aber wer sortierte Binärbäume aus der Informatik kennt, konnte auch ohne diesen Baum im speziellen zu kennen sehr schnell auf die Idee kommen, wie man die zwei gesuchten Wege findet.
Man kann auch umgekehrt vorgehen, indem man die gesuchte Zahl als regulären Kettenbruch schreibt: z.B. 22/7 = 3 + 1/7. Verringert man den letzten/innersten Nenner des Kettenbruchs um 1, erhält man den Elternknoten (3 + 1/6 = 19/6). Nun wiederholt man den Prozess, bis man irgendwann bei 1/1 angelangt ist.
Die beiden vorgegebenen Brüche sind Näherungen für pi und e.
Eine Näherung für Phi ( (1+sqrt(5)) / 2 ) wechselt bei jedem Schritt die Richtung und man erhält stets einen Bruch aus zwei aufeinanderfolgenden Fibonacci-Zahlen.
(12-21-2024, 02:02 AM)Georg J. aus D. schrieb: Die beiden vorgegebenen Brüche sind Näherungen für pi und e.
Eine Näherung für Phi ( (1+sqrt(5)) / 2 ) wechselt bei jedem Schritt die Richtung und man erhält stets einen Bruch aus zwei aufeinanderfolgenden Fibonacci-Zahlen.
Das ist cool, hätte auch gut in die Aufgabe gepasst.
Auf langwierige Abwege hat mich hier der Hinweis in der Aufgabenstellung geführt, dass die Beschriftungen nicht unbedingt als rationale Zahlen aufzufassen sind. So habe ich lange nicht erkannt, dass sie ja eben sortiert sind.
(12-21-2024, 08:42 AM)tfry schrieb: Auf langwierige Abwege hat mich hier der Hinweis in der Aufgabenstellung geführt, dass die Beschriftungen nicht unbedingt als rationale Zahlen aufzufassen sind. So habe ich lange nicht erkannt, dass sie ja eben sortiert sind.
Ja, ging mir genauso. Nachdem ich endlich darauf gekommen war, die Ausdrücke doch als Brüche zu interpretieren, war die Lösung schnell gefunden.
