Vereinfachen Sie einen fortgesetzten Bruch

21

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

Bildbeschreibung hier eingeben

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:

kürzester Code in Bytes: --keine eingebauten Elemente, die das gesamte Problem lösen, erlaubt--

Aaron
quelle
Sie sollten diesen Satz klarer formulieren, "und den fortgesetzten Bruch zu einem einzigen Bruch vereinfachen"; es sei denn, Sie beabsichtigten, dass die Formulierung ein Ergebnis von bedeutet, 2.002kann ausgedrückt werden als 2002/1000. Das ist technisch gesehen eine "einzelne Fraktion", Sie möchten wahrscheinlich sagen, "eine einzelne Fraktion in ihrer einfachsten Form".
Magic Octopus Urn
@carusocomputing point taken .. obwohl ich mich mit 2/4 (oder ähnlichem) nicht schlecht fühlen würde, da es die Mehrfachbruchstruktur immer noch zu einem einzigen Bruch vereinfacht hat
Aaron
Hmm ... Ich denke, es gibt eine Möglichkeit, das auszunutzen, aber mit der 13-Byte-Antwort auf Golfscript müsste ich wahrscheinlich MATL verwenden, um zu gewinnen.
Magic Octopus Urn
@carusocomputing Ich würde sagen, es geht los ... Wenn Sie die 13-Byte-Antwort schlagen können, wäre das fantastisch
Aaron
Sie können den Pi früher stoppen lassen - 355/113.
Thorbjørn Ravn Andersen

Antworten:

15

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 .

Adam
quelle
Wenn Sie die Eingabe als Liste erweiterter Ganzzahlen betrachten, können Sie 3 Bytes einsparen. Außerdem haben Sie in der Erläuterung die APL-Division verwendet.
Meilen
@miles Danke. Kann nicht näher an das eingebaute Verbot als das kommen. Schade, dass J keinen Hook-Kompositionscharakter wie Dyalog APL hat .
Adám
Der Online-Link für Versuch J ist unterbrochen
Chiel ten Brinke
@ChieltenBrinke Danke. Fest.
Adám
12

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 ).

nimi
quelle
1
Oooh, netter Randfall. Die Funktion selbst ist polymorph, daher wird die nicht benötigt import. Um es jedoch aufzurufen, müssen Sie es mit Ratios füttern , das das benötigt import. Soll ich das importzur Byteanzahl hinzufügen oder nicht?
nimi
1
Das klingt nach einer guten Frage für Meta.
Martin Ender
Ich habe noch nie Haskell verwendet. Korrigieren Sie mich, wenn ich falsch liege, aber wenn die Python-Entsprechung lautet: Um from fractions import FractionOperationen mit FractionObjekten auszuführen , wird auch die import-Anweisung gezählt.
Aaron
.. das hatten wir schon mal .
nimi
@Aaron: Das Problem ist: Die Definition der Funktion benötigt keinen Import, da sie polymorph ist. Wenn Sie es aufrufen möchten, müssen Sie Nummern vom Typ Ratioangeben, die nur über erstellt werden können %, was den Import erfordert. Normalerweise zählen wir keine Bytes für den Aufruf von Overhead, nur für die Funktion selbst.
nimi
11

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.
}*
Martin Ender
quelle
11

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
Martin Ender
quelle
10

LabVIEW, 36 äquivalente Bytes

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

Bildbeschreibung hier eingeben

ijustlovemath
quelle
5
Ihr Abschluss in Elektrotechnik wird angezeigt.
Magic Octopus Urn
1
@ijustlovemath Requisiten, aber ..... relevant
Aaron
Ja, es ist eine umstrittene Sprache, um sicher zu sein. Ich sehe LabVIEW als das "Ich hasse Mathe" der Programmiererwelt. Das Problem ist nicht die Mathematik selbst, sondern wie sie unterrichtet wird (oder oft der Mangel an Unterricht überhaupt).
ijustlovemath
6

Dyalog APL , 10 Bytes

Verwendet nicht einmal ein eingebautes Rationalsystem.

Nimmt {a 0 , a 1 , a 2 , a 3 , ...} 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!

Adam
quelle
6

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.

Sp3000
quelle
4

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
Meilen
quelle
1
Was ist das? Ein neuer Jelly-Dialekt?
Adám
@ Meilen tatsächlich 9 Bytes Entschuldigung :(
Aaron
@ Adám Es ist eine alte Gabel aus Jelly, die für Mathematik und Symbolik gedacht ist. Hier ist sein Github-Repo .
Meilen
1
@Aaron M verwendet dieselbe Codepage wie Jelly und kann mit einem Byte für jedes Zeichen codiert werden.
Meilen
@miles OK, hinzugefügt .
Adám
4

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.

xnor
quelle
3

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.

xnor
quelle
3

 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                
Core-Dump
quelle
2

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.
Magische Kraken-Urne
quelle
Sie können zwei Bytes speichern, indem Sie einen Operator (z. B. ) anstelle einer Funktion definieren
Tasos Papastylianou
Ändern Sie auch die for-Schleife für eine Weile und Pop:x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
Tasos Papastylianou
1
25: x->foldr((x,y)->x+1//y,x)(wie Haskell-Lösung). Nutzung:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Fengyang Wang
Oooo ... eine Reverse-Folding-Funktion? Das ist schön! Ich habe es nicht verdient, das anzuerkennen, haha.
Magic Octopus Urn
2

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]));

Arnauld
quelle
2

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
Sp3000
quelle
2

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!

Emigna
quelle
2

JavaScript (ES6), 44 Byte

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

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 ]

Hedi
quelle
1

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)
Brad Gilbert b2gills
quelle
1

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
DLosc
quelle
1

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.

IMP1
quelle
1

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).
rekursiv
quelle
1

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 ...

RosLuP
quelle