Wypisuje listę wszystkich liczb wymiernych

13

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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/3której pierwszy numer jest numerem wejściowym, a następnie numerem wymiernym. Zauważ, że 1: 0zawsze 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.

PhiNotPi
źródło
1
Jaki jest sens reguły 1? Czy chcesz po prostu, aby ludzie grali wspólnie w dwa oddzielne programy, aby przetestować pierwszeństwo i wyliczyć racjonalne przesłanki?
Peter Taylor
Pokazuje, jak bardzo niewielka część liczb całkowitych wciąż ma taką samą liczność jak pełny zestaw liczb wymiernych, a także pozwala na procentowy udział pustych szczelin zbliżający się (ale nigdy nie osiągający) 100%.
PhiNotPi
Zakładam, że program musi również działać w stałej ilości pamięci, tzn. Nie może założyć, że maszyna zawsze może przydzielić więcej? Ponadto, czy używanie indeksu listy dla indeksu listy, gdy wiadomo, że ma on skończony zakres, jest sprzeczne z regułami? (Mimo że dokładny limit może się różnić w zależności od implementacji). Czy wymagana jest jakaś forma bignum?
pudełko na chleb
1
@PhiNotPi, istnieją o wiele prostsze sposoby, aby to zrobić, i odwraca to uwagę od bardziej interesującej części pytania.
Peter Taylor
1
Zauważ, że 1: 0zawsze będzie to pierwszy wiersz wyniku. - Jest to sprzeczne z twoim przykładem, a także nie ma dla mnie sensu.
Wrzlprmft

Odpowiedzi:

6

Haskell, 184 znaki

main=putStr.unlines$zip[1..](s>>=g)>>=h
s=(1,1):(s>>=f)
f(a,b)=[(a,a+b),(a+b,b)]
g x@(a,b)=[x,(-a,b)]
h(i,(a,b))=(i^2)%(u a++'/':u b):map(%"0")[i^2+1..i*(i+2)]
i%s=u i++": "++s
u=show

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):

1: 1/1
4: -1/1
9: 1/2
16: -1/2
25: 2/1
36: -2/1
49: 1/3
64: -1/3
81: 3/2
100: -3/2
...
hammar
źródło
5

Sage, 103 113 128

Sage z łatwością wymienia racjonalne uzasadnienia! Formatowanie zgodne z wymaganiami programu, jak zwykle, wszystko psuje.

for i,q in enumerate(QQ):
 for j in[(i-1)^2+1..i*i]:print'%d:'%j,[0,'%d/%d'%(q.numer(),q.denom())][j==i*i]

Szałwia wylicza QQwedług ich wysokości : maksymalna wartość bezwzględna licznika i mianownika po redukcji GCD.

boothby
źródło
Można wyeliminować x.next()i użyć printtylko 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.
res
BTW, zauważam, że po pierwszych 4 pozytywnych elementach wyliczenie Mędrca nie jest takie samo jak w innych odpowiedziach. Wzory Calkina-Wilfa dają sekwencję, w której mianownik wymiernego jest licznikiem następnego wymiernego; np. (..., 1/3, 3/2, 2/3, ...), w porównaniu do Sage'a (..., 1/3, 3/1, 2/3, ...). Nie mogę zlokalizować żadnej dokumentacji dla wyliczenia Sage'a, aby zobaczyć, jak jest obliczany.
res
@res, dzięki! Chciałem scalić instrukcje drukowania, ale zapomniałem użyć notacji [x..y]. Wspaniale jest zobaczyć tutaj innego użytkownika Sage!
stoisko do
4

Python, 162

f=lambda n:f(n/2)if n%2 else f(n/2)+f(n/2-1)if n else 1
n=i=1
while 1:
 print'%d:'%i,
 if i-n*n:s=0
 else: n+=1;s='%d/%d'%((-1)**n*f(n/2-1),f(n/2))
 print s
 i+=1

Wykorzystuje rekurencję podaną w Recounting the Rationals autorstwa Calkin & Wilf.

res
źródło
2

Haskell, 55 bajtów

mapM_ print$join$iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1]

wyjścia

1 % 1
2 % 1
1 % 2
3 % 1
2 % 3
3 % 2
1 % 3
4 % 1
...

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:

import Data.Ratio
import Control.Monad
main=mapM_ print$0:(join(iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1])>>=(\x->[-x,x]))

wyjścia

0 % 1
(-1) % 1
1 % 1
(-2) % 1
2 % 1
(-1) % 2
1 % 2
(-3) % 1
3 % 1
(-2) % 3
2 % 3
(-3) % 2
3 % 2
(-1) % 3
1 % 3
(-4) % 1
4 % 1
...

wyprowadzanie pustych miejsc? to jest w kiepskim guście :( miałeś mnie na „liście wszystkich pozytywnych uzasadnień”

John Tromp
ź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
Ness,
1

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.

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.~Ð.++$µ:"-$x":0,~õ;

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):

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.'/'.++$µ:"-$x":0,'
';
primo
źródło
1
Otrzymuję błędy w czasie wykonywania z tym kodem (który wydaje się zawierać dziwne znaki; np. „$ Ö. ~ Ð.”).
res
Czy możesz wykazać, że to rozwiązanie działa, powiedzmy na ideone? Pojawiają się
mellamokb
Wygląda na to, że Ideone popełnia błąd, gdy generowanych jest zbyt wiele komunikatów NOTICE: zarówno ~ Ð (równa się „/”), jak i ~ õ (równa się „\ n”) będą generować UWAGA przy każdej iteracji. Oczywiście, jeśli masz wyłączone UWAGI, nie stanowi to problemu. Pasta z obydwoma wymienionymi (107 bajtów): ideone.com/lFUbl
primo
Właśnie zauważyłem, że interpreter PHP Ideone generuje nieprawidłowe dane wyjściowe. Jeśli uruchomisz kod lokalnie, zobaczysz, że jest poprawny. Możesz też przetestować go przy użyciu prawidłowego interpretera PHP, takiego jak narzędzie do sprawdzania wydajności Anarchy Golf: golf.shinh.org/checker.html (zapisz go w pliku i prześlij)
primo
Kiedy zapisuję poprawiony kod do pliku z kodowaniem ANSI, działa on na interpreterze Anarchy Golf. Istnieje jednak inny problem: narusza on wymóg, aby „żadna niezerowa liczba wymierna nigdy nie występowała dwukrotnie” na liście. W rzeczywistości kod wydaje się wymieniać każdy rozsądny nieskończenie wiele razy; np. 1/1, 2/2, 3/3, ... są takie same racjonalne, i podobnie dla 1/2, 2/4, 3/6, ... itd.
res
0

Oktawa, 168 bajtów

a=b=p=1;do for i=(p-1)^2+1:p^2-1 printf("%d: 0\n",i)end
printf("%d: %d/%d\n",p^2,a,b)
a=-a;if a>0do if b==1 b=a+1;a=1;else a++;b--;end until 1==gcd(a,b)end
p++;until 0

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/bjest zawsze drukowane, zanim przejdzie kolejna z sekwencji.

Przekątne przejście wszystkich pozytywnych uzasadnień

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:

a=b=p=1
do
    for i=(p-1)^2+1:p^2-1
        printf("%d: 0\n",i)         # p=2,3,4: 1..3,5..8,10..15
    end
    printf("%d: %d/%d\n", p^2,a,b); # p=2,3,4: 4,9,16
    a=-a;
    if a>0                          # the rule is: after a/b, a>0 output -a/b
        do
            if b==1 b=a+1;a=1; else a++;b--; end
        until 1==gcd(a,b)
    end
    p++;
until 0
pawel.boczarski
źródło