Ułamki ciągłe są wyrażeniami, które iteracyjnie opisują ułamki. Mogą być reprezentowane graficznie:

Lub mogą być reprezentowane jako lista wartości: [a0; a1, a2, a3, ... an]

Wyzwanie:

weź liczbę podstawową: i listę wartości mianownika: i uprość dalszy ciąg ułamkowy do uproszczonego ułamka wymiernego: osobno powróć lub wydrukuj licznik i mianownik.a0[a1, a2, a3, ... an]

Przykłady:

• √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

Przykładowa implementacja: (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

Zwycięski:

J, 8 5 bajtów

Taki sam jak ten , ale używa wbudowanego w rationals.

Argumentem jest {a0, a1, a2, a3, ...} jako lista liczb wymiernych rozszerzonej precyzji J. Wynikiem jest ułamek jako liczba wymierna J z rozszerzoną precyzją.

(+%)/

(+%) plus-wzajemność

/ redukcja ponad

Wypróbuj online!

-3 dzięki milom .

Haskell, 37 36 18 bajtów

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

Ta funkcja oczekuje typu Haskell Ratiojako danych wejściowych. Przykład użycia:

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

Uwaga: wystarczy jedno wyraźne Rationa liście danych wejściowych ( 4%1), systemy typów stwierdzają, że inne również muszą być Ratio.

Edycja: @Lynn zapisał bajt. Dzięki!

Edycja II: usunięto import(zobacz tę dyskusję na temat meta ).

GolfScript , 13 bajtów

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

Wypróbuj online!

Yay dla ukrytych uzasadnień GolfScript . :)

Wyjaśnienie

Jedynym „oficjalnym” typem numeru GolfScript są liczby całkowite. Ale operator potęgowania nie rzutuje wyniku na liczbę całkowitą, a dogodnie natywny wynik potęgowania liczby całkowitej w Rubim (języku interpretera języka GolfScript) jest liczbą wymierną. Możemy więc łatwo uzyskać ułamki, podnosząc coś do potęgi -1. Dogodnie, i tak chcemy wzajemności ...

~]     # 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 bajtów

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

Zasadniczo część mojej odpowiedzi w GolfScript . Oto kilka alternatyw:

Dla 24 bajtów możemy napisać rekurencyjną funkcję wariadyczną:

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

Dla 21 bajtów możemy nawet zdefiniować „operator variadic”, ale jego konwencja wywoływania byłaby tak dziwna, że ​​niechętnie liczę ten:

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

Będziesz musiał to nazwać sekwencją wartości wejściowych, np . ±Sequence[3, 7, 15, 1, 292, 1]Lub ±##&[3, 7, 15, 1, 292, 1].

A także dla 21 bajtów byłoby (zabronione) wbudowane:

FromContinuedFraction

LabVIEW, 36 równoważnych bajtów

Dość prosta naiwna implementacja z wykorzystaniem algorytmu OP. Czy jest na to lepszy sposób?

Dyalog APL , 10 bajtów

Nawet nie używa wbudowanego w racjonalne.

Jako argument przyjmuje {a ₀ , a ₁ , a ₂ , a ₃ , ...}, zwraca {mianownik, licznik}.

1(,÷∨)+∘÷/

1(,÷∨) 1-prepured-podzielone przez GCD z 1 i

+∘÷ plus-wzajemności

/ redukcja ponad

Wypróbuj APL online!

Python 2, 62 bajty

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

Niestety nie jest tak golfowy (patrz odpowiedź @ xnor w skrócie ), ale oblicza ułamek bez konieczności odwracania danych wejściowych. Używa „magiczne tabeli” podejście do convergents - biorąc pod uwagę ostatnie dwie frakcje a/ci b/d, następna część jest (n*b+a)/(n*c+d).

Na przykład dla pi:

          3    7    15     1      292        1

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

Widzimy, że 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113, itd.

M, 5 bajtów

Ṛİ+¥/

Dane wejściowe są listą wartości [a0, a1, ..., aN]i generują liczbę wymierną.

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe.

Wyjaśnienie

Ṛİ+¥/  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 bajtów

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

Rekurencyjnie dodaje każdą warstwę wychodząc na zewnątrz, aktualizując n/d do h+(1/(n/d)), co jest równe h+d/nlub (h*n+d)/n. Frakcja jest przechowywana jako krotka (num,denom). Początkowa część (1,0)przewrotek, do 0/1której jest 0.

Python, 50 bajtów

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

Tworzy ciągłą frakcję od końca listy, cofając się, wielokrotnie aktualizując ułamek n/dostatniego elementu xjako n/d -> 1+1/(n/d) == (x*n+d)/n.

 Common Lisp, 54

Nieco pełne składanie w prawo:

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

Testy

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 bajtów)

Po raz pierwszy używam Julii, jeśli przeoczyłem iterator, mogłem stracić więcej bajtów, daj mi znać. Oto wskazówka dla każdego, kto nie wie, jaki język wybrać dla tego konkretnego wyzwania: 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;)

• Odwróć tablicę wejściową.
• Iteruj przez to z racjonalnym podziałem.
• Dodaj c do wyniku dziesiętnego.

JavaScript (ES6), 55 bajtów

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

Przypadki testowe

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 bajtów

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

Tłumacz online .

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 bajtów

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

Wyjaśnienie

Dane wejściowe są traktowane jako lista liczb

                     # 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

Wypróbuj online!

JavaScript (ES6), 44 bajty

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

JavaScript (ES6), 50 bajtów

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

To dzięki odpowiedzi Arnaulda, zanim ją zobaczyłem, utknąłem na 66 bajtach:

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]

Przykład:
Call: f([1, 0, 1, 1, 2, 1, 1])
Output:Array [ 19, 7 ]

Perl 6 , 24 bajtów

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

Wyjaśnienie:

• 1 / * + *jest lambda z dwoma parametrami ( *), która przyjmuje odwrotność pierwszego i dodaje drugi. (zwraca szczura )

• R[&(…)]używa tego, jakby to był operator infix i odwraca go.
  (w tym ustawienie odpowiedniej asocjacji)

• […](@_) bierze to i używa go do zmniejszenia nakładu.

• … .nudezwraca nu merator i de nominator of the Rat .

• { … }uczyń go czystym blokiem lambda z niejawnym parametrem @_.

Stosowanie:

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 bajtów

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 to pierwszy język programowania, jaki kiedykolwiek stworzyłem. Został zaprojektowany tak, aby był intuicyjny i miał czystą składnię - raczej kosztem zwięzłości. Dlaczego grasz w golfa, pytasz? Ponieważ, w przeciwieństwie do jakiegokolwiek języka, który napisałem, ma on wbudowany Fractiontyp. Możesz nawet użyć operatora podziału/ jako jednoargumentowego dla „odwrotności” (funkcja, którą pożyczyłem dla Pipa).

Teraz istnieją znaczące ograniczenia. Największym problemem dla tego wyzwania jest to, że tablice muszą być zdefiniowane ze stałym rozmiarem, co oznacza, że ​​program rozpoczyna się od odczytania rozmiaru tablicy od użytkownika. (Mam nadzieję, że jest to w porządku; alternatywą jest ustalenie rozmiaru na stałe.) Istnieje również niewielki problem polegający na tym, że pierwszeństwo operatorów nie istnieje, co oznacza, że ​​wyrażenia wielu operatorów muszą mieć nawiasy.

Oto przykładowy przebieg:

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

Rubinowy, 34 bajty

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

Wykonuje to składanie w prawo (przez odwrócenie, a następnie składanie w lewo), dodając każdy element do 1 powyżej bieżącej sumy (elementy po prawej). Ruby ma typ Rational, co jest naprawdę miłe. A dosłowne racjonalności to liczba z przyrostkiem r.

Stax , 4 bajty

╣╩┼►

Uruchom i debuguj

Choć jest tak mały, nie jest wbudowany. Wbudowane racjonalności są jednak całkiem pomocne. Program został rozpakowany do asciirksu+ .

1. Odwróć tablicę.
2. Złóż tablicę za pomocą (a, b) => (a + 1/b).

APL (NARS), 15 + 1 znaków, 30 + 2 bajtów

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

Tłumaczenie w Apl (Nars) z rozwiązania Adama J ... wejściem dozwolonym dla tej funkcji będzie cała lista liczb całkowitych, gdzie pierwszy element będzie typu racjonalnego. Test:

  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 

będzie to 15 znaków jako długość funkcji i 1 znak dla „x” dla wprowadzenia żądanego typu danych wejściowych i wyjścia z typu, którego chcę…