( powiązane )
Pitagorasa potrójny jest lista (a, b, c)
, która spełnia równanie 2 + b 2 = C 2 .
Primitive Pitagorasa Triple (PPT) jest jedną gdzie a
, b
i c
wszystkie są względnie pierwsze (czyli tylko wspólny dzielnik między trzema elementami jest 1
). Na przykład (3, 4, 5)
prawy trójkąt to słynna potrójna pitagorejska potrójna trójka.
Wyzwanie
- Biorąc pod uwagę wejście
n
,n
wyślij th PPT. Lub, - Biorąc pod uwagę dane wejściowe
n
,n
wypisz pierwsze PPT.
Istnieje wiele sposobów na uporządkowanie tych PPT w celu utworzenia dobrze uporządkowanej listy w celu ustalenia, która z nich jest n
th. Możesz wybrać dowolne zamówienie, o ile możesz udowodnić (nieformalnie, że jest w porządku), że Twój algorytm może wygenerować każdy możliwy unikalny PPT. Na przykład, twój kod nie powinien wypisywać obu, (3,4,5)
a (4,3,5)
ponieważ są to duplikaty tego samego potrójnego - proszę o jedno lub drugie.
Podobnie, czy twój kod jest zerowy czy indeksowany jest w porządku, pod warunkiem, że określisz, którego używasz.
Przykłady
W poniższych przykładach używam indeksowania jednokrotnego, generowania n
th PPT i sortowania według najmniejszego c
, następnie najmniejszego a
, a następnie najmniejszego b
.
n | output
1 | (3, 4, 5)
2 | (5, 12, 13)
5 | (20, 21, 29)
12| (48, 55, 73)
Zasady
- Dane wejściowe i wyjściowe można podawać w dowolnym dogodnym formacie .
- W swoim zgłoszeniu podaj, w jaki sposób są uporządkowane Twoje wpisy i czy Twoje wpisy są indeksowane 0 czy indeksowane 1.
- Wybrane zamówienie nie może tworzyć duplikatów.
- Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
- Jeśli to możliwe, dołącz link do internetowego środowiska testowego, aby inni mogli wypróbować Twój kod!
- Standardowe luki są zabronione.
- To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).
źródło
Odpowiedzi:
Galaretka ,
2725 bajtów2 bajty dzięki Jonathanowi Allanowi.
Wypróbuj online!
Wyprowadza pierwsze
n
1-indeksowane tróje[b, a, c]
, posortowane według wzrostu,b
a następniea
.Wykorzystuje algorytm z Wikipedii :
Generuje to wszystkie prymitywne tróje dla wszystkich unikalnych par nieparzystych liczb całkowitych
m > n > 0
.Wyjaśnienie
źródło
g/Ị$Ðf
->,g/ÐṂ
aby zapisać dwa bajty (ponieważ minimalny gcd wynosi 1 i zawsze będzie przynajmniej jeden taki wpis).+2ḶḤ‘Œc
z²Rm2Œc
- złom, że to przyzwyczajenie praca dla wejścia1
:(²ḶḤ‘Œc
był jednym z pierwszych, o których myślałem.)MATL , 36 bajtów
Dane wejściowe są oparte na 1. Kolejność wyjściowa gwarantuje, że każdy potrójny pojawi się dokładnie raz. Kolejność wyjaśniono poniżej. Wyjaśnienie wymaga dokładniejszego zapoznania się z działaniem programu.
Kod stale zwiększa licznik
k
w pętli, zaczynając od1
. Dla każdegok
generuje wszystkie pary za = 1,...,k
,b = 1,...,k
,a < b
, i wybiera te, które otrzymano z pitagorejską potrójnec <= k
. Par uzyskuje się w celu zwiększeniab
, a następniea
.Każda para jest następnie dzielona przez gcd. Powstałe (ewentualnie zduplikowane) pary są ułożone jako macierz dwukolumnowa. Macierz ta jest konkatenowana pionowo z podobną matrycą zawierającą skumulowane wyniki uzyskane dla mniejszych wartości
k
. Rzędy macierzy są następnie stabilnie deduplikowane. Usuwa to dwa typy duplikatów:Pary, które zostały znalezione więcej niż raz dla prądu
k
(takie jak3,4
, które również wynikają z6,8
dzielenia przez jego gcd);Pary, które zostały już znalezione z mniejszymi
k
.W rzeczywistości każda iteracja
k
znajduje wszystkie pary, które zostały już znalezione dla poprzednich iteracji. Ale może znaleźć je w innej kolejności . Na przykładk=25
znajdzie potrójne7,24,25
i nie20,21,29
(boc
nie może przekroczyćk
). Później iteracjak=29
znajdzie oba, ale20,21,29
wcześniej7,24,25
(kolejność rośnieb
, a następniea
). Dlatego zamiast zachować wszystkie znalezione pary dla najnowszychk
, dołączamy je do poprzednich i stabilnie deduplikujemy. Takie postępowanie zapewnia, że kolejność jest taka sama dla każdego wejścian
.Powyższe gwarantuje, że każdy prymitywny potrójny pitagorejczyk w końcu pojawi się i pojawi się tylko raz. W przypadku danych wejściowych
n
pętlak
kończy się, gdyn
uzyskano przynajmniej ważne trzykrotności; a następnien
-ty potrójny jest wyjściem.Wypróbuj online!
Lub użyj tego zmodyfikowanego kodu, aby zobaczyć pierwsze
n
trzykrotnie:Wypróbuj online!
źródło
Haskell , 98 bajtów
Wypróbuj online!
Jak to działa
To interpretuje dwuskładnikowe 3-cyfrowe cyfry n jako ścieżkę w dół drzewa pierwotnych triad pitagorejskich . Działa bez wyszukiwania w operacjach O (log n ).
źródło
Galaretka ,
1918 bajtówProgram przyjmuje indeks 1 n i drukuje pierwsze n PPT [c, b, a] w kolejności leksykograficznej.
Jest to rozwiązanie O (64 n ) , więc TIO będzie dławić się na wejściach 4 i wyższych. Popracuję nad tym, aby było to szybsze.
Wypróbuj online!
Alternatywna wersja, O (n 3 ), prawdopodobnie ważna
Aby znaleźć n- tą tryplet - [c n , b n , a n ] - powyższe rozwiązanie zakłada, że c n ≤ 4 n , co jest łatwe do zweryfikowania. Jednak A020882 dowodzi, że c n ~ 2πn , więc istnieje k takie, że c n ≤ kn dla wszystkich n .
Jeśli możemy przyjąć k = 7 , poniższe rozwiązanie jest również poprawne (i znacznie, znacznie szybsze).
Wypróbuj online!
Jak to działa
źródło
JavaScript (ES7),
106105103 bajtówWysyła N-ty PPT. Wyniki są indeksowane 1 i uporządkowane według wartości b .
Próbny
Pokaż fragment kodu
źródło
MATL , 63 bajty
Wypróbuj online!
Lekcja gry w golfa poszła bardzo źle. W każdym razie publikuję to, ponieważ zastanawiam się, czy istnieją sposoby na grę w golfa lepiej.
Oparłem to na tej stronie Wikipedii w połączeniu ze wzorem Euclida, aby konstruktywnie wygenerować wszystkie potrójne, a nie metody prób i błędów.
Po pierwsze, nieparzyste pary coprime są generowane jako drzewo trójskładnikowe. Odbywa się to przez mnożenie dużej macierzy, co odpowiada większości bajtów. Następnie stosuje się wzór Euklidesa, być może również w sposób bardzo marnotrawczy. Jeśli ktoś ma wskazówki dotyczące tych dwóch części, chciałbym je usłyszeć.
Zauważ, że aby zapisać bajty, program ten generuje drzewo o tej samej głębokości co dane wejściowe, a nie
log3(n)
. Ponadto dzieci są generowane dla każdego wiersza, a nie tylko dla ostatniego wiersza drzewa, a następnie ponownie filtrowane za pomocąXu
. Tyle o efektywnym, konstruktywnym podejściu.źródło
Haskell, 65 bajtów
Indeksowanie na podstawie 0. Na dany
c
,b
biegnie aż doc
ia
maksymalnieb
, więcc > b > a
zawsze trzyma.Wypróbuj online!
źródło
Python,
67504846 bajtówUżywając formuł znalezionych na wikipedii,
a=m*n, b=(m^2-n^2)/2, c=(m^2+n^2)/2
gdzie
m>n>0
im
in
są pierwszymi i nieparzystymi. Oto kod-17 bajtów dzięki @Martin Ender
Wypróbuj online
Działa, zawsze mając wartość
n
zmiennej w równaniu równą 1, co oznacza, żem
jest to po prostu każda inna nieparzysta wartość, w tym przypadku,3+2*n
gdzien
jest liczba pierwotnej potrójnej pitagorejskiej potrójnej wartości. To pozwala nam przyjąć wartość 1 dla wszystkichn
wartości.źródło
a
(a jeśli tak, możesz pozbyć się dwóch spacji). Nie jestem też pewien, dlaczegoprint
tam jesteś , możesz po prostu zwrócić wartości z samej lambda.Łuska , 18 bajtów
Wypróbuj online!
-4 bajty dzięki Zgarbowi, z inspiracją Dennisa
Super powolne podejście brutalnej siły, nie będzie działać na TIO dla danych wejściowych większych niż 1. Możesz wypróbować bardziej łatwą do zarządzania wersję, ograniczoną do a, b ≤ 200 tutaj
Wyjaśnienie
źródło
c
? w takim przypadku to rozwiązanie musiałoby zostać naprawionec
. To 18-bajtowe rozwiązanie (które wykorzystuje inną sztuczkę Dennisa) działa niezależnie.Mathematica, 89 bajtów
za pomocą Solve uporządkowanego przez c
Mathematica, 124 bajty
źródło
R (+ cyfry), 88 bajtów
Aby użyć wbudowanego do wygenerowania liczb, potrzeba naprawdę zaskakującej ilości bajtów, aby uzyskać to, czego chcemy. Polecenie wbudowane pobiera dwa argumenty
c1
ic2
, i zwraca te, które mają trojaczkic >= c1 & c <= c2
. To sprawia, że nieco denerwujące jest dotarcie don
-tego trypletu. To będzie po prostu zwiększaćc2
1 na raz, aż wynik będzie wystarczającą ilością wierszy.źródło
PHP , 273 bajtów
t($n)
zwraca tablicę [a, b, c] z uporządkowaniema < b < c
Wypróbuj online! (tam też kod jest czytelny)
źródło
C, 158 bajtów
Wierzę, że to moje pierwsze zgłoszenie tutaj, więc najprawdopodobniej możesz zrobić lepiej.
I wersja bez golfa:
Na się 2 + b 2 = c 2 , kolejność wzrasta C , a następnie zwiększa .
Nie ma może być dwukrotnie tego samego PPT jako b jest leas a w tym algorytmem.źródło
Galaretka ,
2725 bajtówJest to implementacja podejścia drzewiastego z odpowiedzi Haskell @ AndersKaseorga , z inną kolejnością rozgałęzień. Program korzysta z indeksowania opartego na 0 i pobiera dane wejściowe ze STDIN.
Wypróbuj online!
tło
Jak wspomniano na stronie Wikipedii Drzewo prymitywnych trójek pitagorejskich , każdy PPT można uzyskać poprzez wielokrotne lewe mnożenie wektora wiersza (3, 4, 5) przez macierze o określonych właściwościach.
W każdej iteracji poprzedni wynik można pomnożyć w lewo przez A , B lub C , które można wybrać w następujący sposób.
Kiedy A , B i C są ustalone, każdy PPT można uzyskać w unikalny sposób.
Jak to działa
źródło
APL (NARS), 90 znaków, 180 bajtów
jeśli argumentem powyższej funkcji jest ⍵, powyższa funkcja zwróci element indeksu ⍵ (oparty na 1) tablicy ma elementy triagów pitagorejskich (a, b, c), gdzie a = b <= c i ta tablica jest najpierw rzędu a, (strona krótsza), a następnie b (druga strona nie jest przeciwprostokątna). Byłoby coś nie tak, ponieważ nie widać, gdzie zamawiam też b ... test:
jest związany z http://oeis.org/A020884 i http://oeis.org/A020884/b020884.txt
A020884: Zamówione krótkie nogi prymitywnych trójkątów pitagorejskich.
Nie wiem, czy to prawda, wydaje się, że funkcja daje poprawny wynik pierwszej strony trójkąta do 1000, ale nie wiem do końca, i możliwe, że może być potrójne, a nawet <1000.
źródło
JavaScript, 101 bajtów
Według wzoru Euclida wszystkie prymitywne tróje pitagorejskie można wygenerować z liczb całkowitych
m
i zan
pomocąm>n>0
,m+n
nieparzystegcd(m,n)==1
( Wikipedia )Ta funkcja wylicza wszystkie
m,n
pary zwiększające m, zaczynając odm=2
i zmniejszającn
o 2, zaczynając odm-1
(więc tom+n
jest nieparzyste)Mniej golfa
Test
źródło