Sekwencja Sterna- Brocota jest sekwencją podobną do Fibonnaci, którą można skonstruować w następujący sposób:
- Zainicjuj sekwencję za pomocą
s(1) = s(2) = 1
- Ustaw licznik
n = 1
- Dołącz
s(n) + s(n+1)
do sekwencji - Dołącz
s(n+1)
do sekwencji - Przyrost
n
, wróć do kroku 3
Jest to równoważne z:
Między innymi właściwościami sekwencję Sterna-Brocota można wykorzystać do wygenerowania każdej możliwej dodatniej liczby wymiernej. Każda liczba wymierna zostanie wygenerowana dokładnie raz i zawsze będzie wyświetlana w najprostszych słowach; na przykład 1/3
jest 4 liczba wymierna w sekwencji, ale równoważne numery 2/6
, 3/9
etc nie pojawi się w ogóle.
Możemy zdefiniować n-tą liczbę wymierną jako r(n) = s(n) / s(n+1)
, gdzie s(n)
jest n-ta liczba Sterna-Brocota, jak opisano powyżej.
Wyzwanie polega na napisaniu programu lub funkcji, która wygeneruje n-ty wymierny numer wygenerowany przy użyciu sekwencji Stern-Brocot.
- Algorytmy opisane powyżej mają indeks 1; jeśli twój wpis jest indeksowany jako 0, proszę podać w swojej odpowiedzi
- Opisane algorytmy służą wyłącznie celom ilustracyjnym, dane wyjściowe można uzyskać w dowolny sposób (inny niż kodowanie stałe)
- Dane wejściowe mogą odbywać się za pośrednictwem STDIN, parametrów funkcji lub dowolnego innego uzasadnionego mechanizmu wprowadzania danych
- Ouptut może być do STDOUT, konsoli, zwracanej wartości funkcji lub dowolnego innego rozsądnego strumienia wyjściowego
- Dane wyjściowe muszą być ciągiem znaków w postaci
a/b
, gdziea
ib
są odpowiednimi wpisami w sekwencji Sterna-Brocota. Ocena frakcji przed wyjściem jest niedopuszczalna. Na przykład dla danych wejściowych12
wartość wyjściowa powinna wynosić2/5
, a nie0.4
. - Standardowe luki są niedozwolone
To jest golf golfowy , więc wygra najkrótsza odpowiedź w bajtach.
Przypadki testowe
Przypadki testowe są tutaj indeksowane 1.
n r(n)
-- ------
1 1/1
2 1/2
3 2/1
4 1/3
5 3/2
6 2/3
7 3/1
8 1/4
9 4/3
10 3/5
11 5/2
12 2/5
13 5/3
14 3/4
15 4/1
16 1/5
17 5/4
18 4/7
19 7/3
20 3/8
50 7/12
100 7/19
1000 11/39
Wpis OEIS: A002487
Doskonałe wideo z Numphile omawiające sekwencję: Nieskończone ułamki
True
s zamiast1
s?True/2
nie jest prawidłową frakcją (o ile mi wiadomo ). Nawiasem mówiąc,True
nie zawsze1
- niektóre języki używają-1
zamiast tego, aby uniknąć potencjalnych błędów przy stosowaniu operatorów bitowych. [potrzebne źródło]True
jest równoważne1
iTrue/2
byłoby1/2
.Odpowiedzi:
Galaretka , 14 bajtów
Wypróbuj online!
Ooh, wygląda na to, że mogę pokonać zaakceptowaną odpowiedź @Dennis, i to w tym samym języku. Działa to przy użyciu wzoru z OEIS: liczba sposobów wyrażenia (liczba minus 1) w trybie hiperbinicznym (tj. Binarnym z cyframi 0, 1, 2). W przeciwieństwie do większości programów Jelly (które działają jako pełny program lub funkcja), ten działa tylko jako pełny program (ponieważ wysyła część wyjścia do standardowego wyjścia i zwraca resztę; gdy jest używany jako pełny program, zwracana wartość jest wysyłany na stdout niejawnie, więc wszystkie dane wyjściowe znajdują się w tym samym miejscu, ale nie działałoby to w przypadku przesyłania funkcji).
Ta wersja programu jest bardzo nieefektywna. Możesz stworzyć znacznie szybszy program, który działa dla wszystkich danych wejściowych do 2ⁿ poprzez umieszczenie n tuż po
ẋ
pierwszym wierszu; program ma wydajność O ( n × 3ⁿ), więc utrzymanie n małej wartości jest tutaj dość ważne. Program w postaci zapisanej ustawia n równe wartości wejściowej, która jest wyraźnie wystarczająco duża, ale także wyraźnie zbyt duża w prawie wszystkich przypadkach (ale hej, oszczędza bajty).Wyjaśnienie
Jak zwykle w moich objaśnieniach dotyczących Jelly, tekst w nawiasach klamrowych (np.
{the input}
) Pokazuje coś, co automatycznie wypełnia Jelly z powodu brakujących operandów w oryginalnym programie.Funkcja pomocnicza (oblicza n- ty mianownik, tj. N + 1-ty licznik):
Pierwsze pięć bajtów generuje po prostu wszystkie możliwe liczby hiperbiniczne do danej długości, np. Przy wejściu 3, wyjście
Ḷ
wynosi [[0,1,2], [0,1,2], [0,1,2 ]], więc iloczyn kartezjański to [[0,0,0], [0,0,1], [0,0,2], [0,1,0],…, [2,2,1], [2,2,2]].Ḅ
w zasadzie pomnaża ostatni wpis przez 1, przedostatni wpis przez 2, przedostatni wpis przez 4 itd., a następnie dodaje; chociaż jest to zwykle używane do konwersji wartości binarnych na dziesiętne, to dobrze radzi sobie z cyfrą 2, a zatem działa również z hiperbinicznymi. Następnie zliczamy, ile razy dane wejściowe pojawiają się na wynikowej liście, aby uzyskać odpowiedni wpis w sekwencji. (Na szczęście licznik i mianownik mają tę samą sekwencję).Program główny (prosi o licznik i mianownik oraz formatuje dane wyjściowe):
Jakoś ciągle piszę programy, które zajmują prawie tyle samo bajtów do obsługi I / O, jak robią to, aby rozwiązać rzeczywisty problem…
źródło
CJam (20 bajtów)
Demo online . Zauważ, że jest to indeksowane na 0. Aby indeksować 1, zastąp wartość początkową
1_
przezT1
.Sekcja
Wykorzystuje to charakterystykę ze względu na to, że Moshe Newman
Jeśli
x = s/t
to dostaniemyTeraz, jeśli założymy, że
s
it
są chronione prawem autorskim, toWięc
a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))
działa idealnie.źródło
Haskell,
78 77 6558 bajtówBezwstydne kradzież zoptymalizowanego podejścia daje nam:
Dzięki @nimi za grę w golfa w kilku bajtach za pomocą funkcji infix!
(Nadal) używa indeksowania opartego na 0.
Stare podejście:
Cholera formatu wyjściowego ... I operatorów indeksujących. EDYCJA: I pierwszeństwo.
Ciekawostka: jeśli listy heterogeniczne byłyby czymś, ostatnia linia mogłaby być:
źródło
s!!n
powinno być o jeden bajt krótsze:f n|x<-s!!n=x:x+x+1:f$n+1
s!!n+1
nie jest,(s!!n)+1
ales!!(n+1)
dlatego nie mogę tego zrobić: /s!!n
tam!++'/':(show.s$n+1)
w,r
aby zapisać bajt.(s#t)0=show...
,(s#t)n=t#(s+t-2*mod s t)$n-1
,r=1#1
. Możesz nawet pominąćr
, tzn. Ostatni wiersz jest po prostu1#1
.Galaretka , 16 bajtów
Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
Jak to działa
źródło
05AB1E ,
34332523 bajtówWyjaśnienie
Wypróbuj online
Zaoszczędzono 2 bajty dzięki Adnan.
źródło
XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý
.ý
można sformatować listę. Miły.MATL , 20 bajtów
Wykorzystuje to charakterystykę w kategoriach współczynników dwumianowych podanych na stronie OEIS .
Algorytm działa teoretycznie dla wszystkich liczb, ale w praktyce jest ograniczony precyzją liczbową MATL, więc nie działa w przypadku dużych pozycji. Wynik jest dokładny dla danych wejściowych
20
co najmniej.Wypróbuj online!
Wyjaśnienie
źródło
Python 2,
8581 bajtówTo zgłoszenie ma 1 indeks.
Za pomocą funkcji rekurencyjnej 85 bajtów:
Jeśli wyjście podobne do
True/2
jest akceptowalne, tutaj jest 81 bajtów:źródło
JavaScript (ES6), 43 bajty
1-indeksowany; zmień na
n=1
na 0-indeksowane. Powiązana strona OEIS ma przydatną relację powtarzalności dla każdego terminu w odniesieniu do poprzednich dwóch terminów; Po prostu zinterpretowałem to jako powtórzenie dla każdej frakcji w odniesieniu do poprzedniej frakcji. Niestety nie mamy wbudowanego TeXa, więc wystarczy wkleić go do innej witryny, aby dowiedzieć się, jak te formaty:źródło
Python 2, 66 bajtów
Wykorzystuje formułę rekurencyjną.
źródło
C (GCC), 79 bajtów
Wykorzystuje indeksowanie 0.
Ideone
źródło
x?:y
jest rozszerzeniem gcc.Właściwie 18 bajtów
Wypróbuj online!
To rozwiązanie wykorzystuje formułę Petera i jest również indeksowane na 0. Dzięki Leaky Nun za bajt.
Wyjaśnienie:
źródło
MATL ,
3230 bajtówWykorzystuje to bezpośrednie podejście: generuje wystarczającą liczbę elementów sekwencji, wybiera dwa pożądane i formatuje dane wyjściowe.
Wypróbuj online!
źródło
R, 93 bajty
Dosłownie najprostsza implementacja. Trochę pracuję nad golfem.
źródło
m4, 131 bajtów
Definiuje makro
r
, którer(n)
ocenia zgodnie ze specyfikacją. Nie bardzo grałem w golfa, właśnie kodowałem formułę.źródło
Ruby, 49 bajtów
Jest indeksowany na 0 i wykorzystuje formułę Petera Taylora. Sugestie dotyczące gry w golfa mile widziane.
źródło
> <> , 34 + 2 = 36 bajtów
Po zobaczeniu doskonałej odpowiedzi Petera Taylora, ponownie napisałem moją odpowiedź testową (która była zawstydzająca 82 bajtów, przy użyciu bardzo niezdarnej rekurencji).
Oczekuje, że dane wejściowe będą obecne na stosie, więc +2 bajty dla
-v
flagi. Wypróbuj online!źródło
Oktawa, 90 bajtów
źródło
C #,
9190 bajtówPrzesyłanie do
Func<int, string>
. To jest implementacja rekurencyjna.Nie golfowany:
Edycja: -1 bajt. Okazuje się, że C # nie potrzebuje spacji między
return
i$
dla interpolowanych ciągów.źródło
Python 2, 59 bajtów
Korzysta ze wzoru Petera i podobnie ma indeks 0.
Wypróbuj online
źródło
J, 29 bajtów
Stosowanie
Duże wartości n wymagają przyrostka,
x
który oznacza użycie rozszerzonych liczb całkowitych.źródło
100
liczy się jako „duża wartość”?Mathematica,
108106101 bajtówźródło
R , 84 bajtów
Wypróbuj online!
Starsze realizacja R nie wynika specyfikacje, zwracając zmiennoprzecinkowych zamiast ciąg, więc tutaj jest taki, który robi.
źródło