Aufgabe 12 2024 - Druckversion

Code:

Lösung: 2 (11 Links- und 8 Rechtsdrehungen)



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:



\begin{tabular}{c|c|c|c}

   Bruch links & Bruch rechts & Knoten & Abbiegen nach \\

   \hline

    0/1 &  1/0  &  $1/1 < 22/7$ & rechts \\

    1/1 &  1/0  &  $2/1 < 22/7$ & rechts \\

    2/1 &  1/0  &  $3/1 < 22/7$ & rechts \\

    3/1 &  1/0  &  $4/1 > 22/7$ & links \\

    3/1 &  4/1  &  $7/2 > 22/7$ & links \\

    3/1 &  7/2  &  $10/3 > 22/7$ & links \\

    3/1 &  10/3  &  $13/4 > 22/7$ & links \\

    3/1 &  13/4  &  $16/5 > 22/7$ & links \\

    3/1 &  16/5  &  $19/6 > 22/7$ & links \\

    3/1 &  19/6  &  $22/7$ &  \\

\end{tabular}



Zum zweiten Bruch 87/32 kommt man so:



\begin{tabular}{c|c|c|c}

   Bruch links & Bruch rechts & Knoten & Abbiegen nach \\

   \hline

    0/1 &  1/0  &  $1/1 < 87/32$ & rechts \\

    1/1 &  1/0  &  $2/1 < 87/32$ & rechts \\

    2/1 &  1/0  &  $3/1 > 87/32$ & links \\

    2/1 &  3/1  &  $5/2 < 87/32$ & rechts \\

    5/2 &  3/1  &  $8/3 < 87/32$ & rechts \\

    8/3 &  3/1  &  $11/4 > 87/32$ & links \\

    8/3 &  11/4  &  $19/7 < 87/32$ & rechts \\

    19/7 &  11/4  &  $30/11 > 87/32$ & links \\

    19/7 &  30/11  &  $49/18 > 87/32$ & links \\

    19/7 &  49/18  &  $68/25 > 87/32$ & links \\

    19/7 &  68/25  &  $87/32$ &  \\

\end{tabular}

Code:

22/7 = 3 + 1/7

--> 3 + 1/6 = 19/6

--> 3 + 1/5 = 16/5

--> 3 + 1/4 = 13/4

--> 3 + 1/3 = 10/3

--> 3 + 1/2 = 7/2

--> 4

--> 3

--> 2

--> 1



87/32 = 2 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/4))))

--> 2 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/3)))) = 68/25

--> 2 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/2)))) = 49/18

--> 2 + 1/(1 + 1/(2 + 1/(1 + 1/2))) = 30/11

--> 2 + 1/(1 + 1/(2 + 1/2)) = 19/7

--> 2 + 1/(1 + 1/3) = 11/4

--> 2 + 1/(1 + 1/2) = 8/3

--> 2 + 1/2 = 5/2

--> 3

--> 2

--> 1