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:
- 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.
- 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
. - 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.
- 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/3
mana angka pertama adalah nomor masuk, kemudian diikuti oleh nomor rasional. Perhatikan bahwa 1: 0
akan 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.
sumber
1: 0
akan selalu menjadi baris pertama output. - Ini bertentangan dengan teladan Anda dan juga tidak masuk akal bagi saya.Jawaban:
Haskell, 184 karakter
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):
sumber
Sage, 103
113128Sage dapat membuat daftar rasional dengan mudah! Memformat agar sesuai dengan persyaratan program, seperti biasa, merusak segalanya.
Sage menghitung
QQ
sesuai dengan tinggi mereka : nilai absolut maksimum pembilang & penyebut setelah pengurangan GCD.sumber
x.next()
dan menggunakanprint
hanya 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.Python, 162
Ini menggunakan rekursi yang diberikan dalam Menghitung Rasional oleh Calkin & Wilf.
sumber
Haskell, 55 byte
output
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:
output
mengeluarkan slot kosong? itu rasanya kurang enak :( Anda membuat saya di "daftar semua rasional positif"
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, tanpamapM_ print
bagian ...)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.
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):
sumber
Oktaf, 168 byte
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/b
selalu dicetak sebelum yang berikutnya dari urutan berjalan.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:
sumber