☰

再帰シュテルン・ブロコット木の定義

tag-icon • tag-icon tikz-trees recursion
再帰シュテルン・ブロコット木の定義

私は Stern-Brocot ツリー (有理数の列挙) を構築しようとしています。

結果はほぼ満足できるものでしたが、以下の点については依然として不満が残ります。

  1. 親からのエッジは、子ノードの上部境界ではなく、中央に移動します。
  2. このコマンドは各反復で引数を（再）評価しません（1+1+1代わりに保持します3）
  3. 再帰呼び出しでは\bt@nand を使用できません。何らかの理由で混乱が生じているからです (なぜでしょうか?)。\bt@d
  4. ノードに名前を付ける必要がありますが、これは役に立ちません。ただし、名前を付けないと LaTeX はコンパイルされません。

コードは次のとおりです:

\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}

こんな感じになるはずです シュテルン・ブロコット木

ですから、どんな助けでも大歓迎です。

答え1

あなたに提供できるものはforest?

コード

\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}

出力

ここに画像の説明を入力してください ここに画像の説明を入力してください

コード（その他）

\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}

出力（さらに追加）

ここに画像の説明を入力してください

答え2

以下は Metapost バージョンです。主に、 で再帰が適切に機能することを示すためのものですluamplib。

ここに画像の説明を入力してください

\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}

答え3

面白半分に、TeX任意の有理数の先行数を計算するために使用しています。これはない質問に対する答え。

以下の理由により、2013 年 9 月からバージョンを更新しています。

  1. 明示的にロードする必要があるxinttoolsので、

  2. この方法は、連分数の係数の計算、最​​後の分数の1つによる減少、分数の再構築、反復を経るため、非常に非効率的である。

  3. 結果を見ると、実装にバグがあることに気付きました。最後の係数の減少が正しく括弧で囲まれていなかったため、連分数係数が少なくとも10:-(((

新しい実装では、連分数の係数ではなく、収束点から処理を進めます。収束点は一度だけ計算されます。収束点は指定された分数の祖先の中にありますが、すべての祖先を見つけるには分数をさらに追加する必要があります。方法はコード コメントで説明されています。収束点は、ツリーを上るときに方向が変わる場所に対応します。

\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}

ここに画像の説明を入力してください

関連情報