Finden Sie die Position eines Bruchs im Stern-Brocot-Baum

11

Der Stern-Brocot-Baum ist ein binärer Baum von Brüchen, bei dem jeder Bruch durch Addition der Zähler und Nenner der beiden benachbarten Brüche in den obigen Ebenen erfasst wird.

Es wird erzeugt, indem mit 0/1und 1/0als "Endpunktbrüche" begonnen wird und von dort aus iteriert wird, indem ein Bruch zwischen jedes aufeinanderfolgende Bruchpaar gesetzt wird, indem die Zähler und Nenner dieser Brüche wie folgt addiert werden:

0.  0/1                                                             1/0
1.  0/1                             1/1                             1/0
2.  0/1             1/2             1/1             2/1             1/0
3.  0/1     1/3     1/2     2/3     1/1     3/2     2/1     3/1     1/0
4.  0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0

In jeder Iteration des Stern-Brocot-Baums (der nth-Iteration) gibt es 2^n + 1Elemente in der Sequenz, denen wir einen Bruchteil von 0/2^nbis zuordnen können 2^n/2^n. Jede neue Iteration fügt einfach einen Bruch "auf halbem Weg" zwischen jedem Paar aufeinanderfolgender Brüche ein.

Dies macht den Stern-Brocot-Baum zu einer Eins-zu-Eins-Abbildung zwischen den positiven rationalen Zahlen und den binären Brüchen zwischen 0 und 1 und dient damit auch als Beweis dafür, dass die beiden Mengen dieselbe Kardinalität haben.

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu schreiben, die unter Berücksichtigung des Zählers und Nenners einer positiven rationalen Zahl in niedrigsten Begriffen den binären Bruch bestimmt, der der Position dieses Bruchs im Stern-Brocot-Baum entspricht.

Beispiele für Ein- und Ausgänge finden Sie unten:

2/3 -> 3/8   (4th number in iteration 3)
4/7 -> 9/32  (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2   (middle number in the first iteration)

Eingaben, die Sie nicht unterstützen müssen, die jedoch als Referenz dienen:

0/1 -> 0/1   (0/1 is considered the left number)
1/0 -> 1/1   (1/0 is considered the rightmost number)

Das kürzeste Programm in einer Sprache, um dieses Ziel zu erreichen, gewinnt.

Joe Z.
quelle
Gibt es Eingabe- / Ausgabeanforderungen? zB Reicht nur eine Funktion wie in Ihrer Referenzlösung aus oder muss es sich um ein eigenständiges Programm handeln? Ist das Ausgabeformat für Brüche wichtig?
Darren Stone
Eine Funktion ist ausreichend. Ich werde das in der Problembeschreibung klarer machen.
Joe Z.
Es ist ein bisschen spät für mich, darüber nachzudenken; Ich werde wahrscheinlich versuchen, es morgen zu klären.
Joe Z.
2
Ok, ich denke, die Bijektion, die Sie im Sinn haben, besteht darin, jeder Tiefe im Baum einen konstanten Nenner 2 ^ (Tiefe + 1) und Zähler 1, 3, 5, 7, ... von links zuzuweisen.
Peter Taylor
1
Eine alternative Möglichkeit , sie zu konstruieren ist , um die erste Anzahl Knoten des Baums in Breiten erste Ordnung beginnend bei 1 ( das heißt 1/1 => 1, 1/2 => 2, 2/1 => 3, 1/3 => 4, etc.). Wenn die so erzeugte Zahl für einen Knoten ist n, dann ist 2^lg n(Binärprotokoll) das höchste gesetzte Bit n, und der gewünschte Binärbruch ist (2*(n - 2^lg n) + 1) / 2^(lg n + 1). (Jeder, der versucht, eine Assembler-Lösung in einem Befehlssatz mit einem Get-Highest-Set-Bit zu versuchen, wird wahrscheinlich diesen Ansatz verwenden wollen.)
Peter Taylor

Antworten:

1

GolfScript ( 49 48 46 Zeichen)

{0\@{}{@2*2$2$>!+@@{{\}3$)*}:j~1$-j}/\)\,?}:f;

oder

{0:x;\{}{.2$<!2x*+:x){\}*1$-{\}x)*}/x@)@,?}:g;

Beides sind Funktionen, die den Zähler und den Nenner auf dem Stapel nehmen und den Zähler und den Nenner auf dem Stapel belassen. Online-Demo .

Die Kernidee wird im Pseudocode in Abschnitt 4.5 der Konkreten Mathematik (S. 122 in meiner Ausgabe) ausgedrückt :

while m != n do
    if m < n then (output(L); n := n - m)
             else (output(R); m := m - n)

Wenn die Zeichenfolge von Ls und Rs als Binärwert mit L = 0 und R = 1 interpretiert wird, ist der doppelte Wert plus eins der Zähler, und der Nenner ist ein Bit länger.

Als ein Punkt von Interesse für Golfscripters ist dies eine der seltenen Gelegenheiten, in denen ich die Entfaltung als nützlich empfunden habe. (Ok, ich benutze es nur als Schleifenzähler, aber das ist besser als nichts).

Peter Taylor
quelle
1

Mathematica, 130 114 111 Zeichen

f=#~g~0&;0~g~q_=q;p_~g~q_:=g[#,(Sign[p-#]+q)/2]&@FromContinuedFraction[ContinuedFraction@p/.{x___,n_}:>{x,n-1}]

Beispiel:

f[2/3]

3/8

f[4/7]

9/32

f[1]

1/2

Alephalpha
quelle
1

Ruby, 132 125

Rubied & Golfed die Referenzlösung von @JoeZ.

def t(n,d)u=k=0;v,j,f,g,b=[1,]*5;c=2
while(z=(f*d).<=>(g*n))!=0;z>0?(j,k=f,g):(u,v=f,g);b=b*2-z;f,g=u+j,v+k;c*=2;end
[b,c]end

Anwendungsbeispiele:

>> t(2,3)
=> [3, 8]
>> t(4,7)
=> [9, 32]
>> t(1,1)
=> [1, 2]
Darren Stone
quelle
1

Ruby (69 Zeichen) CoffeeScript (59 Zeichen)

Dies ist eine Funktion, die Zähler und Nenner als Argumente verwendet und nach der Bijektion ein Array zurückgibt, das Zähler und Nenner enthält.

g=(a,b,x=0,y=1)->c=a>=b;a&&g(a-b*c,b-a*!c,2*x+c,2*y)||[x,y]

Online-Demo

Es verwendet den gleichen Ansatz wie meine GolfScript-Lösung oben, ist jedoch viel besser lesbar, da ich 4 Variablen verwenden kann, ohne mich um das Ein- und Auspacken in ein Array kümmern zu müssen. Ich habe mich für CoffeeScript entschieden, weil es Variablen keine Präfixe mit $(20 Zeichen, die über z. B. PHP gespeichert wurden) voranstellt , eine kurze Funktionsdefinitionssyntax hat, die Standardparameterwerte zulässt (es ist also nicht erforderlich, f(a,b,x,y)eine Funktion g(a,b) = f(a,b,0,1)einzuschließen), und ich Boolesche Werte als Ganzzahlen verwenden kann Ausdrücke mit nützlichen Werten. Für diejenigen, die es nicht wissen, hat CoffeeScript nicht den ternären Standardoperator im C-Stil ( C?P:Q), aber ich kann ihn C&&P||Qhier ersetzen , weilP niemals falsch sein wird.

Eine wohl elegantere, aber unbestreitbar weniger kurze Alternative besteht darin, die wiederholte Subtraktion durch Division und Modulo zu ersetzen:

f=(a,b,x=0,y=1,p=0)->a&&f(b%a,a,(x+p<<b/a)-p,y<<b/a,1-p)||[x+p,y]

(65 Zeichen; Online-Demo ). Wenn Sie es so schreiben, wird die Beziehung zum Euklid-Algorithmus sichtbar.

Peter Taylor
quelle
Sie brauchen keine Klammern, um a<bdie Sie ein Zeichen sparen. Inlining cgibt zwei weitere. Sie können auch die Syntax f=->a,b,x=0,y=1{...}für eine noch kürzere Definition berücksichtigen .
Howard
@Howard, ich weiß nicht, welche Version von Ruby Sie verwenden, aber bei IDEOne wird ein Syntaxfehler angezeigt, wenn ich versuche, diese Klammern zu entfernen oder diese Funktionssyntax zu verwenden.
Peter Taylor
Versuchen Sie es c=a<b ?mit einem zusätzlichen Platz danach b. Andernfalls wird das Fragezeichen als Teil des behandelt b.
Howard
0

Python - 531

Eine ungolfed Lösung in Python, um als Referenzlösung für den letzten Platz zu dienen:

def sbtree(n, d): 
    ufrac = [0, 1]
    lfrac = [1, 0]
    frac = [1, 1]
    bfrac = [1, 2]
    while(frac[0] * d != frac[1] * n): 
        if(frac[0] * d > frac[1] * n): 
            # push it towards lfrac
            lfrac[0] = frac[0]
            lfrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 - 1 
        elif(frac[0] * d < frac[1] * n): 
            # push it towards ufrac
            ufrac[0] = frac[0]
            ufrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 + 1 
        frac[0] = ufrac[0] + lfrac[0]
        frac[1] = ufrac[1] + lfrac[1]
        bfrac[1] *= 2
    return bfrac

Es wird einfach eine binäre Suche zwischen Brüchen durchgeführt, wobei die Tatsache ausgenutzt wird , dass der Mediant von zwei beliebigen Brüchen immer zwischen den Werten dieser beiden Brüche liegt.

Joe Z.
quelle
0

GolfScript, 54 Zeichen

'/'/n*~][2,.-1%]{[{.~3$~@+@@+[\]\}*].2$?0<}do.@?'/'@,(

Die Eingabe muss auf STDIN in der in der Aufgabe angegebenen Form erfolgen. Sie können den Code online ausprobieren .

> 4/7
9/32

> 9/7
35/64

> 5/1
31/32
Howard
quelle
0

Mathematica 138

Nicht so rational wie das Verfahren von alephalpha, aber es war das Beste, das ich bisher produzieren konnte.

q_~r~k_:=Nest[#+Sign@k/(2Denominator@# )&,q,Abs@k]  
g@d_:=
Module[{l=ContinuedFraction@d,p=-1},
l[[-1]]-=1;
(p=-p;# p)&/@l]
h[q_]:=Fold[r,1/2,g@q]

Testen

h[2/3]
h[4/7]
h[1]

3/8
9/32
1/2

DavidC
quelle
0

JavaScript 186

f=(p1,q1,p2,q2)=>{if(p1*q2+1==p2*q1){return{p:p1+p2,q:q1+q2}}let p,q,pl=0,ql=1,ph=1,qh=0;for(;;){p=pl+ph;q=ql+qh;if(p*q1<=q*p1){pl=p;ql=q}else if(p2*q<=q2*p){ph=p;qh=q}else return{p,q}}}

könnte weniger sein, aber ich mag lesbares Golf

caub
quelle
0

Haskell , 125 Bytes

n((a,b):(c,d):r)=(a,b):(a+c,b+d):n((c,d):r)
n a=a
z=zip[0..]
t x=[(j,2^i)|(i,r)<-z$iterate n[(0,1),(1,0)],(j,y)<-z r,x==y]!!0

Probieren Sie es online aus!

Eingabe und Ausgabe in Form eines Paares (n,d).

Kurze Erklärung:

nKonstruiert die nächste Zeile aus der vorherigen, indem jedes Fraktionspaar betrachtet und die neue zwischen der ersten und der Rekursion eingefügt wird (wodurch die zweite Fraktion genau dort platziert wird). Der Basisfall ist sehr einfach, da es sich im Grunde nur um die Identitätsfunktion handelt. Die tFunktion iteriert diese Funktion auf unbestimmte Zeit basierend auf dem Anfangszustand mit nur den beiden Grenzfraktionen. tindiziert dann jede Zeile ( i) und jedes Element in der Zeile ( j) und sucht nach dem ersten Bruch, der dem entspricht, wonach wir suchen. Wenn es es findet, gibt es jals Zähler und 2^ials Nenner nach.

user1472751
quelle