Keluarkan daftar semua angka rasional

13

Dari semua matematika, akan selalu ada beberapa teorema yang melampaui semua akal sehat. Salah satunya adalah kenyataan bahwa ada berbagai ukuran tak terbatas. Fakta lain yang menarik adalah gagasan bahwa banyak infinities yang tampaknya berbeda ukuran sebenarnya dengan ukuran yang sama. Ada bilangan genap sebanyak bilangan bulat, karena ada bilangan rasional.

Konsep umum dari pertanyaan ini adalah untuk menghadapi realitas infinity yang aneh. Dalam tantangan ini, program Anda akan menampilkan daftar yang akan:

  • Pada setiap saat waktu tertentu, selalu memiliki sejumlah entri
  • Akhirnya berisi (jika dibiarkan berjalan cukup lama) angka rasional spesifik (bukan nol) tepat sekali pada seluruh daftar
  • Berisi jumlah slot kosong yang tidak terbatas (entri pada daftar yang tidak perlu diatur ke 0)
  • Memiliki proporsi slot kosong yang mendekati batas 100%
  • Untuk setiap bilangan bulat positif N, miliki jumlah tempat tanpa batas dengan N slot kosong berturut-turut

Tantangan

Tantangan Anda adalah menulis program sesingkat mungkin yang akan menampilkan daftar khusus dengan aturan berikut:

  1. Semua entri dengan indeks yang bukan angka kuadrat harus ditetapkan ke nol. Jadi, entri pertama akan nol, yang kedua dan ketiga akan nol, yang keempat akan nol, dll.
  2. Semua bilangan rasional akan dalam bentuk fraksi yang tidak tepat (seperti 4/5 atau 144/13) yang telah disederhanakan. Pengecualiannya adalah nol, yang akan sederhana 0.
  3. Semua angka rasional (positif dan negatif) pada akhirnya akan muncul dalam daftar jika program Anda berjalan cukup lama dan dengan memori yang cukup. Untuk bilangan rasional tertentu, waktu yang dibutuhkan mungkin jumlah waktu yang besar, tetapi selalu terbatas.
  4. Jika dijalankan untuk jumlah waktu yang tidak terbatas, tidak boleh ada nomor rasional yang tidak nol muncul dua kali.

Aturan 3 memang memungkinkan untuk beberapa variasi, karena di sana ada jumlah tak terbatas hasil hukum yang berbeda.

Output akan menjadi aliran garis. Setiap baris akan berupa umum di 5: 2/3mana angka pertama adalah nomor masuk, kemudian diikuti oleh nomor rasional. Perhatikan bahwa 1: 0akan selalu menjadi baris pertama output.

Cuplikan contoh output:

1: 1/1
2: 0
3: 0
4: 2/1
5: 0
6: 0
7: 0
8: 0
9: -2/1
10: 0
etc...

Aturan, Peraturan, dan Catatan

Ini golf kode. Aturan golf kode standar berlaku. Juga, karena variasi yang diizinkan dalam output, Anda harus setidaknya menunjukkan mengapa Anda percaya bahwa daftar Anda akan berisi semua angka rasional yang mungkin tepat sekali, dan bahwa solusi Anda benar.

EDIT: Karena bilangan prima mengalihkan perhatian dari tantangan, saya mengubahnya menjadi bilangan kuadrat. Ini mencapai tujuan yang sama, dan juga mempersingkat solusi.

PhiNotPi
sumber
1
Apa gunanya aturan 1? Apakah Anda hanya ingin orang-orang saling golf dua program terpisah untuk menguji keutamaan dan menghitung rasional?
Peter Taylor
Ini menunjukkan bagaimana sebagian kecil dari bilangan bulat masih memiliki kardinalitas yang sama dengan set lengkap bilangan rasional, dan juga memungkinkan persentase slot kosong untuk mendekati (tetapi tidak pernah mencapai) 100%.
PhiNotPi
Saya berasumsi bahwa program juga perlu dijalankan dalam jumlah memori tetap, yaitu tidak dapat berasumsi bahwa mesin selalu dapat mengalokasikan lebih banyak? Juga, apakah melanggar aturan untuk menggunakan (katakanlah) int untuk indeks daftar ketika Anda tahu bahwa ia memiliki rentang yang terbatas? (Meskipun batas pastinya dapat berbeda dengan implementasinya.) Apakah diperlukan beberapa bentuk bignum?
kotak roti
1
@PhiNotPi, ada banyak cara yang lebih sederhana untuk melakukan itu, dan ini merupakan gangguan dari bagian pertanyaan yang lebih menarik.
Peter Taylor
1
Perhatikan bahwa 1: 0akan selalu menjadi baris pertama output. - Ini bertentangan dengan teladan Anda dan juga tidak masuk akal bagi saya.
Wrzlprmft

Jawaban:

6

Haskell, 184 karakter

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

Ini melakukan lintas luas pertama dari Calkin-Wilf Tree , menghasilkan semua bilangan rasional positif dalam bentuk tereduksi tepat sekali. Kemudian berganti-ganti antara positif dan negatif untuk mencakup semua bilangan rasional nol dan bantalan dengan nol di antara entri kuadrat.

Output (tidak termasuk garis nol untuk singkatnya):

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
sumber
5

Sage, 103 113 128

Sage dapat membuat daftar rasional dengan mudah! Memformat agar sesuai dengan persyaratan program, seperti biasa, merusak segalanya.

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]

Sage menghitung QQsesuai dengan tinggi mereka : nilai absolut maksimum pembilang & penyebut setelah pengurangan GCD.

stan
sumber
Anda dapat menghilangkan x.next()dan menggunakan printhanya sekali, sebagai berikut, membawa skor turun ke 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. Ini tidak ditampilkan dengan benar dalam komentar, tetapi saya pikir Anda dapat melihat apa yang saya maksud.
res
BTW, saya perhatikan bahwa setelah 4 elemen positif pertama, enumerasi Sage tidak sama dengan jawaban lainnya. Rumus Calkin-Wilf memberikan urutan di mana penyebut rasional adalah pembilang rasional berikutnya; misal (..., 1/3, 3/2, 2/3, ...), dibandingkan dengan Sage (..., 1/3, 3/1, 2/3, ...). Sepertinya saya tidak dapat menemukan dokumentasi untuk penghitungan Sage, untuk melihat bagaimana perhitungannya.
res
@res, terima kasih! Saya ingin menggabungkan pernyataan cetak, tetapi lupa untuk menggunakan notasi [x..y]. Luar biasa melihat pengguna Sage lain di sini!
Stanby
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

Ini menggunakan rekursi yang diberikan dalam Menghitung Rasional oleh Calkin & Wilf.

res
sumber
2

Haskell, 55 byte

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

output

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

1% 1 adalah akar dari pohon Calkin-Wilf; iterate menambahkan kedua anak dari setiap node; gabungan tersebut meruntuhkan level menjadi satu daftar.

120 karakter jika Anda menambahkan impor yang tepat, 0, dan negatif:

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

output

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
...

mengeluarkan slot kosong? itu rasanya kurang enak :( Anda membuat saya di "daftar semua rasional positif"

John Tromp
sumber
mapM_ print$fix((1%1:).(>>= \x->[x+1,1/(x+1)]))adalah 47 karakter. dari haskellwiki . berfungsi sebagaimana mestinya , tanpa impor, di haskell.org 's "try it" REPL (yah, tanpa mapM_ printbagian ...)
Will Ness
1

PHP 105 byte

Catatan: Kode ini harus disimpan sebagai iso-8859-1 (ansi) agar dapat berjalan dengan benar. Penerjemah online yang menyandikan semua input ke utf8 secara default (seperti ideone) akan menghasilkan output yang salah.

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

Menggunakan enumerasi Georg Cantor (sedikit dimodifikasi untuk nilai +/-).

Jika Anda mengalami masalah dalam menjalankan kode di atas (kemungkinan karena jumlah pesan PEMBERITAHUAN yang berlebihan), gunakan ini sebagai gantinya (107 byte):

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.'/'.++$µ:"-$x":0,'
';
primo
sumber
1
Saya mendapatkan kesalahan run-time dengan kode ini (yang tampaknya mengandung beberapa karakter aneh; misalnya, "$ ö. ~ Ð.").
res
Bisakah Anda menunjukkan bahwa solusi ini berhasil, katakanlah pada ideone? Saya mendapatkan error juga: ideone.com/ru1fo
mellamokb
Ideone kelihatannya salah ketika terlalu banyak pesan PEMBERITAHUAN dihasilkan: keduanya ~ Ð (sama dengan '/') dan ~ õ (sama dengan "\ n") akan menghasilkan PEMBERITAHUAN setiap iterasi. Tentu saja, jika Anda memiliki PEMBERITAHUAN, itu tidak masalah. Rekat dengan keduanya diganti (107 Bytes): ideone.com/lFUbl
primo
Saya baru saja memperhatikan bahwa penafsir PHP Ideone menghasilkan output yang salah. Jika Anda menjalankan kode secara lokal, Anda akan melihat bahwa itu benar. Atau, Anda dapat mengujinya dengan penerjemah PHP yang valid, seperti pemeriksa kinerja Anarchy Golf: golf.shinh.org/checker.html (simpan ke file dan unggah)
primo
Ketika saya menyimpan kode revisi Anda ke file dengan pengkodean ANSI, itu berjalan pada juru Golf Anarchy. Namun, sekarang ada masalah yang berbeda: itu melanggar persyaratan bahwa "tidak boleh ada bilangan rasional nol dua kali" dalam daftar. Bahkan, kode itu muncul untuk membuat daftar setiap rasional berkali-kali tak terhingga; misalnya 1/1, 2/2, 3/3, ... semuanya rasional, dan juga untuk 1/2, 2/4, 3/6, ..., dll.
res
0

Oktaf, 168 byte

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

Solusinya tidak terlalu canggih, itu hanya traversal diagonal sederhana dari "karpet" bilangan rasional, membuang semua fraksi yang dapat disederhanakan. Setelah angka positif a/b, kebalikannya -a/bselalu dicetak sebelum yang berikutnya dari urutan berjalan.

Traversal diagonal dari semua rasional positif

Karena semua pecahan sederhana yang positif akan dicetak dan pecahan bertanda tangan yang bertolak belakang dengan yang akan dicetak, dan dua pecahan sederhana yang berbeda tidak mungkin memiliki nilai yang sama, masing-masing bilangan rasional bukan nol akan dicetak tepat sekali.

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
sumber