Uprość dalszą część

21

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

wprowadź opis zdjęcia tutaj

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:

najkrótszy kod w bajtach: - brak wbudowanych, które wykonują cały problem dozwolone -

Aaron
źródło
Powinieneś uściślić to zdanie „i uprościć ciągły ułamek do jednego ułamka”; chyba że zamierzałeś, aby sformułowanie oznaczało wynik, 2.002można wyrazić jako 2002/1000. Z technicznego punktu widzenia jest to „pojedyncza frakcja”, zapewne chcesz powiedzieć, „pojedyncza frakcja w najprostszej formie”.
Magic Octopus Urn
@carusocomputing punkt zajęty .. chociaż nie czułbym się źle z powodu 2/4 (lub podobnego), ponieważ wciąż uprościł strukturę wielu frakcji do pojedynczej frakcji
Aaron
Hmm ... Myślę, że jest sposób na wykorzystanie tego, ale z 13-bajtową odpowiedzią na golfscript prawdopodobnie musiałbym użyć MATL-a, aby wygrać.
Magic Octopus Urn
@carusocomputing Powiedziałbym, że idź ... Jeśli potrafisz pokonać 13-bajtową odpowiedź, byłoby wspaniale
Aaron
Możesz zatrzymać pi wcześniej - 355/113.
Thorbjørn Ravn Andersen

Odpowiedzi:

15

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 .

Adám
źródło
Jeśli weźmiesz dane jako listę rozszerzonych liczb całkowitych, możesz zapisać 3 bajty. W wyjaśnieniu użyto również podziału APL.
mile
@miles Thanks. Nie może zbliżyć się do wbudowanego zakazu. Szkoda, że ​​J nie ma hakowej kompozycji, jak Dyalog APL .
Adám
Link do strony J J jest zepsuty
Chiel ten Brinke
@ChieltenBrinke Thanks. Naprawiony.
Adám
12

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

nimi
źródło
1
Oooh, fajna skrzynia. Sama funkcja jest polimorficzna, więc nie potrzebuje import. Jednak aby to nazwać, musisz nakarmić Ratiogo, który potrzebuje import. Czy powinienem dodać importliczbę bajtów, czy nie?
nimi
1
To brzmi jak dobre pytanie do meta.
Martin Ender
Nigdy nie korzystałem z Haskell, więc popraw mnie, jeśli się mylę, ale jeśli równoważny byłby python: from fractions import Fractionaby wykonywać operacje na Fractionobiektach, liczona jest również instrukcja importu.
Aaron
@Aaron: problem polega na tym, że definicja funkcji nie wymaga importu, ponieważ jest polimorficzna. Kiedy chcesz to wywołać, musisz podać numery typu, Ratioktóre można zbudować tylko za pomocą %, co wymaga importu. Zwykle nie liczymy bajtów dla wywołania narzutu, tylko dla samej funkcji.
nimi
11

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.
}*
Martin Ender
źródło
11

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
Martin Ender
źródło
10

LabVIEW, 36 równoważnych bajtów

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

wprowadź opis zdjęcia tutaj

ijustlovemath
źródło
5
Twój stopień inżyniera elektrycznego pokazuje.
Magic Octopus Urn
1
@ijustlovemath Props, ale ..... dotyczy
Aaron
Tak, to jest wątpliwy język. Widzę LabVIEW jako „nienawidzę matematyki” świata programistów. Problemem nie jest sama matematyka, ale sposób jej uczenia (lub często brak nauczania).
ijustlovemath
6

Dyalog APL , 10 bajtów

Nawet nie używa wbudowanego w racjonalne.

Jako argument przyjmuje {a 0 , a 1 , a 2 , a 3 , ...}, zwraca {mianownik, licznik}.

1(,÷∨)+∘÷/

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

+∘÷ plus-wzajemności

/ redukcja ponad

Wypróbuj APL online!

Adám
źródło
6

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.

Sp3000
źródło
4

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
mile
źródło
1
Co to jest? Jakiś nowy dialekt galaretki?
Adám
@miles faktycznie 9 bajtów przepraszam :(
Aaron
@ Adám To stary widelec galaretki przeznaczony do matematyki i symboliki. Oto jego repozytorium Github .
mile
1
@Aaron M używa tej samej strony kodowej co Jelly i może być kodowany za pomocą bajtu dla każdego znaku.
mile
@miles OK, dodano .
Adám
4

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.

xnor
źródło
3

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.

xnor
źródło
3

 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                
rdzeń rdzeniowy
źródło
2

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.
Urna Magicznej Ośmiornicy
źródło
możesz zapisać dwa bajty, definiując operator (np. ) zamiast funkcji
Tasos Papastylianou
również zmień na chwilę pętlę for i 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)(tak samo jak roztwór Haskell). użycie:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Fengyang Wang,
Ooo ... Funkcja odwrotnego składania? To jest piękne! Nie zasługuję jednak na uznanie tego za haha.
Magic Octopus Urn
2

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

Arnauld
źródło
2

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
Sp3000
źródło
2

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!

Emigna
źródło
2

JavaScript (ES6), 44 bajty

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])
Neil
źródło
1

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 ]

Hedi
źródło
1

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)
Brad Gilbert b2gills
źródło
1

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
DLosc
źródło
1

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.

IMP1
źródło
1

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).
rekurencyjny
źródło
1

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ę…

RosLuP
źródło