Fortgesetzte Brüche sind Ausdrücke, die Brüche iterativ beschreiben. Sie können grafisch dargestellt werden:

Oder sie können als Werteliste dargestellt werden: [a0; a1, a2, a3, ... an]

Die Herausforderung:

Nehmen Sie eine Basiszahl: und eine Liste von Nennerwerten: und vereinfachen Sie den fortgesetzten Bruch zu einem vereinfachten rationalen Bruch: Geben Sie Zähler und Nenner getrennt zurück oder drucken Sie sie aus.a0[a1, a2, a3, ... an]

Beispiele:

• √19 : [4;2,1,3,1,2]: 170/39
• ℯ: [1;0,1,1,2,1,1]: 19/7
• π: [3;7,15,1,292,1]: 104348/33215
• ϕ: [1;1,1,1,1,1]: 13/8

Beispielimplementierung: (Python)

def foo(base, sequence):
    numerator = 1
    denominator = sequence[-1]
    for d in sequence[-2::-1]:
        temp = denominator
        denominator = d * denominator + numerator
        numerator = temp
    return numerator + base * denominator, denominator

Gewinnen:

J, 8 5 Bytes

Das Gleiche wie hier , verwendet jedoch ein eingebautes Rationalisierungsmodul.

Das Argument ist {a0, a1, a2, a3, ...} als Liste von rationalen Zahlen mit erweiterter Genauigkeit. Ergebnis ist der Bruch als J erweiterte rationale Genauigkeitszahl.

(+%)/

(+%) das plus-das-gegenseitige-von

/ Reduktion vorbei

Probieren Sie es online!

-3 dank meilen .

Haskell, 37 36 18 Bytes

foldr1$(.(1/)).(+)

Diese Funktion erwartet den RatioTyp von Haskell als Eingabe. Anwendungsbeispiel:

Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2] 
170 % 39

Hinweis: Ein expliziter RatioEintrag in der Eingabeliste ( 4%1) reicht aus, das Typensystem erkennt, dass auch die anderen Ratios sein müssen.

Bearbeiten: @Lynn hat ein Byte gespeichert. Vielen Dank!

Edit II: entfernt die import(siehe diese Diskussion auf Meta ).

GolfScript , 13 Bytes

~]-1%{\-1?+}*

Probieren Sie es online!

Ja, für die versteckten Gründe von GolfScript . :)

Erläuterung

Der einzige "offizielle" Zahlentyp in GolfScript ist eine Ganzzahl. Der Exponentiationsoperator wandelt das Ergebnis jedoch nicht in eine Ganzzahl um. Praktischerweise ist das native Ergebnis einer Ganzzahl-Exponentiation in Ruby (der Sprache des GolfScript-Interpreters) eine rationale Zahl. So können wir leicht Brüche erhalten, indem wir etwas auf die Potenz von -1 erhöhen. Praktischerweise wollen wir sowieso Gegenseitigkeiten ...

~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*

Mathematica, 23 22 Bytes

Fold[#2+1/#&]@*Reverse

Im Wesentlichen ein Port meiner GolfScript-Antwort . Hier sind ein paar alternativen:

Für 24 Bytes können wir eine rekursive Variadic-Funktion schreiben:

f@n_=n
n_~f~m__:=n+1/f@m

Für 21 Bytes können wir sogar einen "variadischen Operator" definieren, aber seine Aufrufkonvention wäre so seltsam, dass ich diesen nicht zählen möchte:

±n_=n
n_ ±m__:=n+1/±m

Sie müssten dies mit einer Folge der Eingabewerte aufrufen , z . B. ±Sequence[3, 7, 15, 1, 292, 1]oder ±##&[3, 7, 15, 1, 292, 1].

Und auch für 21 Bytes gäbe es das (verbotene) eingebaute:

FromContinuedFraction

LabVIEW, 36 äquivalente Bytes

Ziemlich einfache, naive Implementierung unter Verwendung des OP-Algorithmus. Gibt es eine schönere Möglichkeit, dies zu tun?

Dyalog APL , 10 Bytes

Verwendet nicht einmal ein eingebautes Rationalsystem.

Nimmt {a ₀ , a ₁ , a ₂ , a ₃ , ...} als Argument, gibt {Nenner, Zähler} zurück.

1(,÷∨)+∘÷/

1(,÷∨) 1-vorangestellt-geteilt durch die GCD von 1 und

+∘÷ plus-das-gegenseitige-von

/ Reduktion vorbei

TryAPL online!

Python 2, 62 Bytes

a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

Es ist leider nicht so golfig (siehe @ xnors Antwort für kürzere), aber es berechnet den Bruch, ohne die Eingabe umkehren zu müssen. Dies verwendet den "Zaubertabellen" -Ansatz für Konvergente - vorausgesetzt, die letzten beiden Fraktionen a/cund b/ddie nächste Fraktion sind (n*b+a)/(n*c+d).

Zum Beispiel für pi:

          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

Wir können sehen , dass 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113etc.

M, 5 Bytes

Ṛİ+¥/

Die Eingabe ist eine Liste der Werte [a0, a1, ..., aN]und gibt eine rationale Zahl aus.

Probieren Sie es online! oder Überprüfen Sie alle Testfälle.

Erläuterung

Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly

Haskell, 30 Bytes

foldr(\h(n,d)->(h*n+d,n))(1,0)

Recursively fügt jede Schicht nach außen gehen, die Aktualisierung n/dauf h+(1/(n/d)), die gleich h+d/noder (h*n+d)/n. Die Fraktion wird als Tupel von gespeichert (num,denom). Der anfängliche Bruchteil der (1,0)Flips, zu 0/1denen 0.

Python, 50 Bytes

f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

Erstellt den fortgesetzten Bruch ab dem Ende der Liste in umgekehrter Reihenfolge und aktualisiert wiederholt den Bruch n/dauf dem letzten Element xals n/d -> 1+1/(n/d) == (x*n+d)/n.

 Gemeiner Lisp, 54

Ein etwas wortreiches Fold-Right:

(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

Tests

PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39              
T     ℯ     19/7                 19/7                
T     π     104348/33215         104348/33215        
T     ϕ     13/8                 13/8                

Julia (53 Bytes)

Dies ist das erste Mal, dass ich Julia verwende. Wenn ich einen Iterator übersehen hätte, mit dem ich mehr Bytes hätte verlieren können, lassen Sie es mich wissen. Hier ist ein Hinweis für alle, die nicht wissen, welche Sprache sie für diese spezielle Herausforderung wählen sollen: https://en.wikipedia.org/wiki/Rational_data_type

f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)

• Kehren Sie das Eingabearray um.
• Durchlaufen Sie es mit rationaler Teilung.
• Addiere c zum Dezimalergebnis.

Javascript (ES6), 55 Byte

s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

Testfälle

var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));

CJam , 18 16 Bytes

XUq~W%{2$*+\}/]p

Online-Dolmetscher .

XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output

05AB1E , 19 17 Bytes

R¬V¦vyY*X+YUV}YX)

Erläuterung

Eingabe als Liste von Zahlen

                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

Probieren Sie es online!

JavaScript (ES6), 44 Byte

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])

Javascript (ES6), 50 Byte

f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

Es ist Arnauld's Antwort zu verdanken, bevor ich es sah, blieb ich bei 66 Bytes:

f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

Beispiel:
Aufruf: f([1, 0, 1, 1, 2, 1, 1])
Ausgabe:Array [ 19, 7 ]

Perl 6 , 24 Bytes

{[R[&(1/*+*)]](@_).nude}

Erläuterung:

• 1 / * + *ist ein Lambda mit zwei Parametern ( *), das den Kehrwert des ersten nimmt und den zweiten addiert. (gibt eine Ratte zurück )

• R[&(…)]verwendet das als ob es ein Infix Operator wäre und kehrt es um.
  (einschließlich der richtigen Assoziation)

• […](@_) Nimmt das und verwendet es, um die Eingabe zu reduzieren.

• … .nudegibt die nu merator und de nominator der Ratte .

• { … }Machen Sie es zu einem Bare-Block-Lambda mit impliziten Parametern @_.

Verwendung:

say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)

Zephyr , 145 Bytes

input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

Zephyr ist die erste Programmiersprache, die ich jemals erstellt habe. Es wurde so konzipiert, dass es intuitiv ist und eine saubere Syntax hat - eher auf Kosten der Kürze. Warum spiele ich damit Golf, fragst du? Denn im Gegensatz zu jeder Sprache, die ich seitdem geschrieben habe, ist ein FractionTyp eingebaut . Sie können sogar den Divisionsoperator verwenden/ als unären Operator für "inverse" verwenden (eine Funktion, die ich für Pip ausgeliehen habe).

Jetzt gibt es erhebliche Einschränkungen. Das größte Problem bei dieser Herausforderung besteht darin, dass Arrays mit fester Größe definiert werden müssen. Dies bedeutet, dass das Programm zunächst die Größe des Arrays vom Benutzer liest. (Ich hoffe, das ist in Ordnung; die Alternative ist das Hardcodieren der Größe.) Es gibt auch das kleinere Problem, dass keine Operator-Rangfolge besteht, dh Ausdrücke mit mehreren Operatoren müssen Klammern haben.

Hier ist ein Beispiellauf:

C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8

Ruby, 34 Bytes

->a{a.reverse.inject{|b,i|i+1r/b}}

Dies führt eine Rechtsfaltung durch (durch Umkehren und anschließende Linksfaltung), wobei jedes Element über die laufende Summe (die Elemente rechts) zu 1 addiert wird. Ruby hat den Rational-Typ, der wirklich nett ist. Und wörtliche Begründungen sind eine Zahl, an die angehängt wird r.

Stax , 4 Bytes

╣╩┼►

Führen Sie es aus und debuggen Sie es

So klein es auch ist, es ist kein eingebautes Gerät. Die eingebauten Rationen helfen allerdings einiges. Entpackt nach ASCII ist das Programm rksu+.

1. Kehren Sie das Array um.
2. Falten Sie das Array mit (a, b) => (a + 1/b).

APL (NARS), 15 + 1 Zeichen, 30 + 2 Byte

{1=≢⍵:↑⍵⋄+∘÷/⍵}

Übersetzung in Apl (Nars) aus der Adam-J-Lösung ... Die für diese Funktion zulässige Eingabe ist eine Liste mit ganzen Zahlen, wobei das erste Element vom Typ rational ist. Prüfung:

  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}      
  f 4x 2 1 3 1 2
170r39 
  f 1x 0 1 1 2 1 1
19r7 
  f 3x 7 15 1 292 1
104348r33215 
  f 1x 1 1 1 1 1
13r8 
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828 
158824716824887954093160207727r52744031585005490644982548907 
  f ,0x
0 
  f ,9x
9 

es wären also 15 Zeichen als Länge der Funktion und 1 Zeichen für "x", um den gewünschten Eingabetyp einzugeben und den gewünschten Typ zu beenden ...