Z całej matematyki zawsze będzie kilka twierdzeń, które wykraczają poza wszelki zdrowy rozsądek. Jednym z nich jest fakt, że istnieją różne rozmiary nieskończoności. Innym interesującym faktem jest pomysł, że wiele nieskończoności, które wydają się być różnej wielkości, są w rzeczywistości tego samego rozmiaru. Istnieje tyle samo liczb parzystych, co liczb całkowitych, tak jak liczb wymiernych.
Ogólna koncepcja tego pytania polega na skonfrontowaniu się z dziwną rzeczywistością nieskończoności. W tym wyzwaniu Twój program wyświetli listę, która:
- W dowolnym momencie zawsze masz całą liczbę wpisów
- Ostatecznie zawierają (jeśli pozostawione na wystarczająco długo) dowolny konkretny (niezerowy) numer wymierny dokładnie raz na całej liście
- Zawierają nieograniczoną liczbę pustych miejsc (wpisy na liście, które są niepotrzebnie ustawione na 0)
- Posiadaj odsetek pustych miejsc, który zbliża się do limitu 100%
- Dla każdej dodatniej liczby całkowitej N należy mieć nieskończoną liczbę miejsc z N kolejnymi pustymi miejscami
Wyzwanie
Twoim wyzwaniem jest napisanie możliwie najkrótszego programu, który wyświetli specjalną listę z następującymi zasadami:
- Wszystkie wpisy z indeksem, który nie jest liczbą kwadratową, należy ustawić na zero. Tak więc pierwszy wpis będzie niezerowy, drugi i trzeci będzie zerowy, czwarty będzie niezerowy itp.
- Wszystkie liczby wymierne będą miały postać niewłaściwego ułamka (takiego jak 4/5 lub 144/13), który został uproszczony. Wyjątkiem są zera, które będą po prostu
0
. - Wszystkie (dodatnie i ujemne) liczby wymierne powinny ostatecznie pojawić się na liście, jeśli program działa wystarczająco długo i przy wystarczającej ilości pamięci. Dla każdej konkretnej liczby wymiernej wymagany czas może być dowolnie duży, ale zawsze skończony.
- Jeśli działa przez nieskończony czas, żadna niezerowa liczba wymierna nigdy nie powinna pojawić się dwukrotnie.
Zasada 3 dopuszcza pewną zmienność, ponieważ istnieje nieskończona liczba różnych możliwych legalnych wyników.
Wyjście będzie strumieniem linii. Każda linia będzie miała ogólną formę, w 5: 2/3
której pierwszy numer jest numerem wejściowym, a następnie numerem wymiernym. Zauważ, że 1: 0
zawsze będzie to pierwszy wiersz wyniku.
Przykładowy fragment wyniku:
1: 1/1
2: 0
3: 0
4: 2/1
5: 0
6: 0
7: 0
8: 0
9: -2/1
10: 0
etc...
Zasady, przepisy i uwagi
To jest kod golfowy. Obowiązują standardowe zasady gry w golfa. Ponadto, ze względu na dopuszczalną zmienność w danych wyjściowych, musisz przynajmniej pokazać, dlaczego uważasz, że twoja lista będzie zawierała wszystkie możliwe liczby wymierne dokładnie raz, a twoje rozwiązanie jest poprawne.
EDYCJA: Ponieważ liczby pierwsze odwracają uwagę od wyzwania, zmieniam je na liczby kwadratowe. Osiąga to ten sam cel, a także skraca rozwiązania.
źródło
1: 0
zawsze będzie to pierwszy wiersz wyniku. - Jest to sprzeczne z twoim przykładem, a także nie ma dla mnie sensu.Odpowiedzi:
Haskell, 184 znaki
Odbywa się to po raz pierwszy w przejściu drzewa Calkin-Wilf , dając jednokrotnie wszystkie dodatnie liczby wymierne w zmniejszonej formie. Następnie przełącza się między dodatnim i ujemnym, aby objąć wszystkie niezerowe liczby wymierne i pola zerowe między kwadratowymi wpisami.
Wynik (z wyjątkiem linii zerowych dla zwięzłości):
źródło
Sage, 103
113128Sage z łatwością wymienia racjonalne uzasadnienia! Formatowanie zgodne z wymaganiami programu, jak zwykle, wszystko psuje.
Szałwia wylicza
QQ
według ich wysokości : maksymalna wartość bezwzględna licznika i mianownika po redukcji GCD.źródło
x.next()
i użyćprint
tylko raz, w następujący sposób, zmieniając wynik na dół do 124:x=enumerate(QQ) for i,q in x: for j in[(i-1)^2+1..i*i]: print'%d: '%j,'%d/%d'%(q.numer(),q.denom())if j.is_square()else 0
. Nie wyświetla się to poprawnie w komentarzu, ale myślę, że rozumiesz, co mam na myśli.Python, 162
Wykorzystuje rekurencję podaną w Recounting the Rationals autorstwa Calkin & Wilf.
źródło
Haskell, 55 bajtów
wyjścia
1% 1 jest korzeniem drzewa Calkin-Wilf; iterat dodaje oba elementy podrzędne każdego węzła; złączenie zwija poziomy w jedną listę.
120 znaków, jeśli dodasz odpowiedni import, 0 i negatywy:
wyjścia
wyprowadzanie pustych miejsc? to jest w kiepskim guście :( miałeś mnie na „liście wszystkich pozytywnych uzasadnień”
źródło
mapM_ print$fix((1%1:).(>>= \x->[x+1,1/(x+1)]))
jest 47 znaków. z haskellwiki . działa tak, jak jest, bez żadnego importu, w REPL (spróbuj, bez części ...) w haskell.orgmapM_ print
PHP 105 bajtów
Uwaga: Ten kod musi być zapisany jako iso-8859-1 (ansi), aby działał poprawnie. Interpretatory online, które domyślnie kodują wszystkie dane wejściowe do utf8 (takie jak ideone), generują nieprawidłowe dane wyjściowe.
Korzystanie z wyliczenia Georga Cantora (nieznacznie zmodyfikowane dla wartości +/-).
Jeśli masz problemy z uruchomieniem powyższego kodu (prawdopodobnie z powodu nadmiernej ilości komunikatów NOTICE), użyj tego (107 bajtów):
źródło
Oktawa, 168 bajtów
Rozwiązanie nie jest bardzo wyrafinowane, jest to po prostu przekątna „dywanu” liczb wymiernych, odrzucająca wszystkie ułamki, które można uprościć. Po dodatniej liczbie
a/b
, jej przeciwieństwo-a/b
jest zawsze drukowane, zanim przejdzie kolejna z sekwencji.Ponieważ wszystkie pozytywne proste ułamki zwykłe zostaną wydrukowane, a ułamki przeciwne do tych zostaną wydrukowane i nigdy nie jest możliwe, aby dwie różne proste ułamki miały tę samą wartość, każda niezerowa liczba wymierna zostanie wydrukowana dokładnie raz.
Degolfed:
źródło