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:
najkrótszy kod w bajtach: - brak wbudowanych, które wykonują cały problem dozwolone -
code-golf
math
rational-numbers
Aaron
źródło
źródło
2.002
można wyrazić jako2002/1000
. Z technicznego punktu widzenia jest to „pojedyncza frakcja”, zapewne chcesz powiedzieć, „pojedyncza frakcja w najprostszej formie”.Odpowiedzi:
J,
85 bajtówTaki 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 ponadWypróbuj online!
-3 dzięki milom .
źródło
∘
.Haskell,
373618 bajtówTa funkcja oczekuje typu Haskell
Ratio
jako danych wejściowych. Przykład użycia:Uwaga: wystarczy jedno wyraźne
Ratio
na 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 ).źródło
import
. Jednak aby to nazwać, musisz nakarmićRatio
go, który potrzebujeimport
. Czy powinienem dodaćimport
liczbę bajtów, czy nie?from fractions import Fraction
aby wykonywać operacje naFraction
obiektach, liczona jest również instrukcja importu.Ratio
które można zbudować tylko za pomocą%
, co wymaga importu. Zwykle nie liczymy bajtów dla wywołania narzutu, tylko dla samej funkcji.GolfScript , 13 bajtów
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 ...
źródło
Mathematica,
2322 bajtówZasadniczo część mojej odpowiedzi w GolfScript . Oto kilka alternatyw:
Dla 24 bajtów możemy napisać rekurencyjną funkcję wariadyczną:
Dla 21 bajtów możemy nawet zdefiniować „operator variadic”, ale jego konwencja wywoływania byłaby tak dziwna, że niechętnie liczę ten:
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:
źródło
LabVIEW, 36 równoważnych bajtów
Dość prosta naiwna implementacja z wykorzystaniem algorytmu OP. Czy jest na to lepszy sposób?
źródło
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-prepured-podzielone przez GCD z 1 i+∘÷
plus-wzajemności/
redukcja ponadWypróbuj APL online!
źródło
Python 2, 62 bajty
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/c
ib/d
, następna część jest(n*b+a)/(n*c+d)
.Na przykład dla pi:
Widzimy, że
15*22 + 3 = 333
,15*7 + 1 = 106
,1*333 + 22 = 355
,1*106 + 7 = 113
, itd.źródło
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
źródło
Haskell, 30 bajtów
Rekurencyjnie dodaje każdą warstwę wychodząc na zewnątrz, aktualizując
n/d
doh+(1/(n/d))
, co jest równeh+d/n
lub(h*n+d)/n
. Frakcja jest przechowywana jako krotka(num,denom)
. Początkowa część(1,0)
przewrotek, do0/1
której jest0
.źródło
Python, 50 bajtów
Tworzy ciągłą frakcję od końca listy, cofając się, wielokrotnie aktualizując ułamek
n/d
ostatniego elementux
jakon/d -> 1+1/(n/d) == (x*n+d)/n
.źródło
Common Lisp, 54
Nieco pełne składanie w prawo:
Testy
źródło
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
źródło
∘
) zamiast funkcjix∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
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])
JavaScript (ES6), 55 bajtów
Przypadki testowe
źródło
CJam ,
1816 bajtówTłumacz online .
źródło
05AB1E ,
1917 bajtówWyjaśnienie
Dane wejściowe są traktowane jako lista liczb
Wypróbuj online!
źródło
JavaScript (ES6), 44 bajty
źródło
JavaScript (ES6), 50 bajtów
To dzięki odpowiedzi Arnaulda, zanim ją zobaczyłem, utknąłem na 66 bajtach:
Przykład:
Call:
f([1, 0, 1, 1, 2, 1, 1])
Output:
Array [ 19, 7 ]
źródło
Perl 6 , 24 bajtów
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.… .nude
zwraca nu merator i de nominator of the Rat .{ … }
uczyń go czystym blokiem lambda z niejawnym parametrem@_
.Stosowanie:
źródło
Zephyr , 145 bajtów
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
Fraction
typ. 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:
źródło
Rubinowy, 34 bajty
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
.źródło
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 ascii
rksu+
.(a, b) => (a + 1/b)
.źródło
APL (NARS), 15 + 1 znaków, 30 + 2 bajtów
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:
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ę…
źródło