Możesz utworzyć listę wszystkich wymiernych wartości 0 <r ≤ 1, wymieniając je najpierw według mianownika, a następnie według licznika:
1 1 1 2 1 3 1 2 3 4 1 5 1 2 3 4 5
- - - - - - - - - - - - - - - - -
1 2 3 3 4 4 5 5 5 5 6 6 7 7 7 7 7
Zauważ, że pomijamy każdą liczbę wymierną, która już wcześniej występowała. Np. 2/4 jest pomijane, ponieważ wymieniliśmy już 1/2.
W tym wyzwaniu interesują nas tylko liczniki. Patrząc na powyższą listę, napisz funkcję lub program przyjmujący dodatnią liczbę całkowitą n, która zwraca n-ty licznik z listy.
Przypadki testowe:
1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 3
7 -> 1
8 -> 2
9 -> 3
50 -> 4
80 -> 15
(0,1]
Odpowiedzi:
MATL ,
1713 bajtówWypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wielkość wejściowa może być ograniczona dokładnością zmiennoprzecinkową. Wszystkie przypadki testowe dają poprawny wynik.
Wyjaśnienie
To generuje wszystkie ułamki za
k/m
pomocąk
,m
w[1 2 ...n]
, jako macierzyn
×n
. Wiersz wskazuje licznik, a kolumna wskazuje mianownik. W rzeczywistości wpis macierzy zawiera ułamek odwrotnym/k
zamiastk/m
, ale nie ma to znaczenia i można go zignorować w dalszej części objaśnienia.Wpisy macierzy są domyślnie uważane za sortowane w porządku według kolumny. W tym przypadku odpowiada to wymaganej kolejności: mianownik, a następnie licznik.
W tej macierzy należy pominąć trzy typy wpisów:
k/m
,k>m
które mają taką samą wartość jak poprzedni wpis (na przykład2/4
nie są uwzględniane, ponieważ są takie same jak1/2
)k/k
,k>1
. Wpisy, których licznik przekracza mianownikk/m
,k<m
(nie są częścią problemu).Ignorowanie wpisów odbywa się za pomocą
unique
funkcji, która stabilnie usuwa zduplikowane wartości i wysyła wskaźniki pozostałych wpisów. Dzięki temu wpisy typu 1 powyżej są automatycznie usuwane. Aby poradzić sobie z typami 2 i 3, wpisy macierzy po przekątnej i poniżej są ustawione na0
. W ten sposób wszystkie wpisy zerowe zostaną usunięte z wyjątkiem pierwszego (odpowiadającego prawidłowej frakcji1/1
).Rozważ dane wejściowe
4
jako przykład.źródło
Galaretka ,
119 bajtówWypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
Jak to działa
źródło
Mathematica, 53 bajty
źródło
Haskell, 40 bajtów
Anonimowa funkcja. Całkiem proste: używa rozumienia listy do generowania nieskończonej listy, zapętlając wszystkie liczniki
n
i względnie główne mianownikid
. Aby przekonwertować indeks zerowy na jeden indeksowany, przygotowujemy a0
, który zajmuje4
bajty.źródło
n<-[0..d]
dodaje zero w krótszy sposób i oszczędza 4 bajtyPyth, 13 bajtów
Wypróbuj online. Zestaw testowy.
źródło
Pyth, 11 bajtów
Wypróbuj online: demonstracja
Wyjaśnienie:
źródło
Właściwie 15 bajtów
Ta odpowiedź jest oparta na odpowiedzi Jelly'ego na żelki . Używam
HN
na końcu, aby uniknąć problemów z indeksowaniem 0 i potrzebą zmniejszenia wartości n i zamiany na początku lub na końcu.H
pobiera pierwszychn
członków listy liczników, które są wynikiem, iN
pobiera ostatniego członka tej selekcji, tj.n
th licznika, wszystko bez konieczności manipulowania przy stosach. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!Ungolfing
źródło
Python,
111110 bajtówUłamek jest reprezentowany przez
x/y
. Argumentn
jest zmniejszany, gdy zostanie znaleziony nowy ułamek pasujący (nagcd
podstawiefractions
kontroli można zmniejszyć ułamek). W każdej iteracji pętlix
jest zwiększana, a następnie, jeśli rozpoczynax>=y
się nowa seria ułamkówy+1
,>
ze względu na „specjalny przypadek”(x,y)=(2,1)
, w golfax>y
.Jestem pewien, że można bardziej grać w golfa, ale brakuje mi tego, gdzie mógłbym to poprawić.Znaleziono to.Link do kodu i przypadków testowych
źródło
JavaScript (ES6), 95 bajtów
Działa poprzez generowanie wszystkich
n²
ułamków za pomocą liczników i mianowników od1
don
i filtrowanie tych większych niż1
lub wcześniej widziane, a następnie przyjmowanien
th.źródło
Perl, 82 + 2 (
-pl
flaga) = 84 bajtówNie golfowany:
źródło
JavaScript (ES6), 76
Mniej golfa
Test
źródło
Clojure, 85 bajtów
Używa rozumienia list do generowania listy wszystkich wymiernych, a następnie filtruje je, aby uzyskać tylko odrębne. Pobiera
nth
pozycję z listy i zwraca jej licznik. Potrzebny jest także osobny warunek dla pierwszego elementu, ponieważ Clojure nie jest w stanie pobrać licznika liczby całkowitej. (z dowolnego powodu uznając liczbę całkowitą za nieracjonalną - https://goo.gl/XETLo2 )Zobacz online - https://ideone.com/8gNZEB
źródło