☰

Rekursiver Stern-Brocot-Baum – Definition

tag-icon • tag-icon tikz-trees recursion
Rekursiver Stern-Brocot-Baum – Definition

Ich versuche, einen Stern-Brocot-Baum (Aufzählung rationaler Zahlen) zu erstellen.

Das Ergebnis ist nahezu akzeptabel, allerdings bin ich mit folgenden Punkten dennoch unzufrieden.

  1. Die Kante von den Eltern geht bis zur Mitte des Kindknotens, nicht bis zur oberen Grenze.
  2. Der Befehl wertet seine Argumente bei jeder Iteration nicht (neu) aus (wir behalten 1+1+1bei statt 3)
  3. Ich kann \bt@nund \bt@din den rekursiven Aufrufen nicht verwenden, da sie irgendwie durcheinander sind (warum?).
  4. Ich muss meinen Knoten einen Namen geben, was nutzlos ist, aber ohne wird LaTeX nicht kompiliert.

Hier ist der Code:

\documentclass{standalone}
\usepackage{tikz}
\usepackage{etoolbox}

\newcommand{\eval}[1]{\pgfmathparse{int(#1)}\pgfmathresult}

\makeatletter  % We can use the `@` symbol in macro names
\def\mybtree#1#2#3#4#5{%

  \pgfextra{ % Allows us to use non-drawing commands
    \pgfmathtruncatemacro\bt@depth{#5}    % Current depth
    \pgfmathtruncatemacro\bt@ndepth{\bt@depth - 1}  % Next depth

    \pgfmathtruncatemacro\bt@n{#1+#3}
    \pgfmathtruncatemacro\bt@d{#2+#4}

    %% Calculate the sibling distance
    %  distance = 2^{remaining depth}
    \pgfmathsetmacro\bt@sdistance{pow( 2, \bt@depth)}
  }

  node (\bt@n/\bt@d) {$\frac{\eval{#1+#3}}{ \eval{#2+#4}}$}

  \ifnumgreater{\bt@depth}{0}{% if( depth > 0 ) then:
    child [sibling distance=\bt@sdistance*2em] {
      \mybtree{#1}{#2}{#1+#3}{#2+#4}{\bt@ndepth}
    } 
    child [sibling distance=\bt@sdistance*2em] { 
      \mybtree{#1+#3}{#2+#4}{#3}{#4}{\bt@ndepth} 
    } 
  }{% else:
    %% Do nothing
  }
}
\newcommand*{\btree}[1]{\mybtree{0}{1}{1}{0}{#1}}
\makeatother 

\begin{document}
%% Now we can draw our tree
\begin{tikzpicture} 
  \draw \btree{3};
\end{tikzpicture}

\end{document}

Es sollte so etwas geben Stern-Brocot-Baum

Jede Hilfe ist also willkommen.

Antwort1

Kann ich Ihnen einforest?

Code

\documentclass[tikz]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest}
  Stern Brocot/.style n args={5}{%
    content=$\frac{\number\numexpr#1+#3\relax}{\number\numexpr#2+#4\relax}$,
    if={#5>0}{% true
      append={[,Stern Brocot={#1}{#2}{#1+#3}{#2+#4}{#5-1}]},
      append={[,Stern Brocot={#1+#3}{#2+#4}{#3}{#4}{#5-1}]}
    }{}}% false (empty)
[,Stern Brocot={0}{1}{1}{0}{3}]
\end{forest}
\end{document}

Ausgabe

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Code (mit mehr Inhalt)

\documentclass[tikz]{standalone}
\usepackage{forest}
\makeatletter
\pgfmathdeclarefunction{strrepeat}{2}{%
  \begingroup\pgfmathint{#2}\pgfmath@count\pgfmathresult
    \let\pgfmathresult\pgfutil@empty
    \pgfutil@loop\ifnum\pgfmath@count>0\relax
      \expandafter\def\expandafter\pgfmathresult\expandafter{\pgfmathresult#1}%
      \advance\pgfmath@count-1\relax
    \pgfutil@repeat\pgfmath@smuggleone\pgfmathresult\endgroup}
\makeatother
\tikzset{
  Stern Brocot at/.style={at/.wrap 2 pgfmath args={([rotate around=180:(!##1)] !##22)}
    {strrepeat("#1",\SBLevel)}{strrepeat("#1",\SBLevel-1)}},
  Stern Brocot at*/.style n args={3}{
    at/.wrap pgfmath arg={(!##1-|SB@#3)}{strrepeat("#1",#2)},
    /forest/if={#2<\SBLevel}{append after command=
      (\tikzlastnode) edge[densely dotted] (SB@#3@\the\numexpr\SBLLoop+1\relax)}{}}}
\forestset{
  Stern Brocot*/.style n args={2}{
    content=$\frac{#1}{#2}$,
    edge=densely dotted,
    if={level()<\SBLevel}{append={[,Stern Brocot*={#1}{#2}]}}{}},
  Stern Brocot/.style n args={5}{
    /utils/exec=\edef\SBLevel{#5},@Stern Brocot={#1}{#2}{#3}{#4}},
  @Stern Brocot/.style n args={4}{
    /utils/exec=\edef\SBTop   {\number\numexpr#1+#3\relax}% eTeX instead of PGFmath
                \edef\SBBottom{\number\numexpr#2+#4\relax},
    content/.expanded=$\frac{\SBTop}{\SBBottom}$,
    if/.expanded={level()<\SBLevel}{% true
      append={[,@Stern Brocot={#1}{#2}{\SBTop}{\SBBottom}]},
      append={[,Stern Brocot*={\SBTop}{\SBBottom}]},
      append={[,@Stern Brocot={\SBTop}{\SBBottom}{#3}{#4}]}
    }{}}}% false (empty)
\begin{document}
\begin{forest}[,Stern Brocot={0}{1}{1}{0}{3}]
\coordinate[Stern Brocot at=1] (SB@left) coordinate[Stern Brocot at=3] (SB@right);
\foreach \SBLLoop in {\SBLevel, ..., 0}
  \path node[Stern Brocot at*={1}{\SBLLoop}{left}]  (SB@left@\SBLLoop)  {$\frac01$}
        node[Stern Brocot at*={3}{\SBLLoop}{right}] (SB@right@\SBLLoop) {$\frac10$};
\end{forest}
\end{document}

Ausgabe (mit mehr Inhalt)

Bildbeschreibung hier eingeben

Antwort2

Hier ist eine Metapost-Version – hauptsächlich um zu zeigen, dass die Rekursion in ordnungsgemäß funktioniert luamplib.

Bildbeschreibung hier eingeben

\documentclass[border=10mm]{standalone}
\usepackage{unicode-math}
\setmainfont{TeX Gyre Schola}
\usepackage{luamplib}
\mplibtextextlabel{enable}
\begin{document}
\begin{mplibcode}
path S; S = superellipse(9 right, 12 up, 9 left, 12 down,0.79);
def connect(expr a,b) = 
    draw a -- b cutbefore S shifted a cutafter S shifted b
enddef;              
def putfrac(expr num, den, pos) = 
    draw (left--right) scaled 4 shifted pos;
    label.top(decimal num,pos);
    label.bot(decimal den,pos);
enddef;    
vardef mediant(expr a,b,c,d, depth, L, R) =
    save m,n, p; pair p;
    p = ((L+R)/2,depth * v);
    m = a+c; n = b+d;
    if depth > 1:
        connect(p, mediant(a,b,m,n,depth-1, L, xpart p)) withcolor .53 red;
        connect(p, mediant(m,n,c,d,depth-1, xpart p, R)) withcolor .53 blue;
        connect(p, p shifted (0,-v)) dashed withdots scaled 1/2;
        connect((L, ypart p), (L,ypart p-v)) dashed withdots scaled 1/2;
        if d=0:
            connect((R, ypart p), (R,ypart p-v)) dashed withdots scaled 1/2;
        fi
    fi
    if depth > 0:
        putfrac(m,n,p);
        putfrac(a,b,(L,ypart p));
        if d=0: 
            putfrac(c,d,(R,ypart p));
        fi
    fi
    p
enddef;
beginfig(1);
v = 1.618cm;
z0 = mediant(0,1,1,0, 5, 0,220mm);
endfig;
\end{mplibcode}
\end{document}

Antwort3

Aus Spaß TeXwerden hier die Vorgänger einer beliebigen rationalen Zahl berechnet. Beachten Sie, dass diesnichteine Antwort auf die Frage.

Ich aktualisiere die Version vom September 2013 aus folgenden Gründen:

  1. xinttoolsman muss jetzt explizit laden ,

  2. Die Methode umfasste die Berechnung der Kettenbruchkoeffizienten, die Verminderung des letzten um einen, die Neukonstruktion des Bruchs und eine Iteration und war daher sehr ineffizient.

  3. beim Betrachten des Ergebnisses ist mir aufgefallen, dass es einen Fehler in der Implementierung gab, der um eins verringerte letzte Koeffizient war nicht richtig in Klammern gesetzt, daher war das Ganze fehlerhaft, wenn ein Kettenbruchkoeffizient mindestens 10:-(((

Die neue Implementierung geht nicht mit den Koeffizienten des Kettenbruchs, sondern mit den Konvergenten vor. Sie werden ein für alle Mal berechnet. Sie gehören zu den Vorfahren des gegebenen Bruchs, aber wir müssen weitere Brüche hinzufügen, um alle Vorfahren zu finden. Das Rezept wird in den Codekommentaren erklärt. Konvergenten entsprechen den Stellen, an denen man beim Aufwärtsbewegen im Baum die Richtung ändert.

\documentclass{article}
\usepackage{xintcfrac, xinttools}

\makeatletter
\newcommand*\defSBAncestors [1]{% 
% we first compute all convergents of a positive fraction
% we need to reverse the order, then we will scan and 
% add the needed intermediate fractions.
% \SBA@i will see p/q.p'/q'....... n/1.\relax 
% The ending n/1 is 0/1 if original fraction was <1.
% We need to add intermediate (p-p')/(q-q'), (p-2p')/(q-2q'), ...
   \def\SBAncestors{}%
   \expandafter\SBA@i 
   \romannumeral0\xintlistwithsep.{\xintRevWithBraces{\xintFtoCv{#1}}}.\relax
}
\def\SBA@i #1/#2.{\if1\xintiiIsOne{#1}\xintdothis\SBA@D\fi
                  \if1\xintiiIsOne{#2}\xintdothis\SBA@N\fi
                  \xintorthat\SBA@ii #1/#2.}
\def\SBA@ii #1/#2.#3/#4.{%
    \edef\SBAncestors{\SBAncestors{#1/#2}}%
    \edef\SBA@P {\xintiiSub{#1}{#3}}%
    \edef\SBA@Q {\xintiiSub{#2}{#4}}%
    \if1\xintiiGtorEq {#3}{\SBA@P}\xintdothis\SBA@i\fi
    \xintorthat{\SBA@ii \SBA@P/\SBA@Q.}#3/#4.}

% Treat the special situations N/1 or 1/D

\def\SBA@D 1/#1.#2\relax {\edef\SBAncestors{\SBAncestors
                          \xintApply{1/\@firstofone}{\xintSeq[-1]{#1}{1}}}}

\def\SBA@N #1/#2\relax {\edef\SBAncestors{\SBAncestors\xintSeq[-1]{#1}{1}}}
\makeatother      


\newcommand*\STRUT{\rule[4pt]{0pt}{9pt}} % line spacing

% #1 must evaluate to a **positive** fraction. It will be reduced to smalles
% terms initially.
\newcommand*\ShowParents [1]{%
   \defSBAncestors {#1}%
   $\xintListWithSep{\to}{\xintApply{\STRUT\xintFrac}\SBAncestors}$%
}

\begin{document}

\ShowParents {5}

\ShowParents {1/5}

\ShowParents {23/16}

\ShowParents {355/113}

\ShowParents {137197119/2110810820}

\end{document}

Bildbeschreibung hier eingeben

verwandte Informationen