Tujuan
Buat program / fungsi yang mengambil input N
, periksa apakah N
pasangan acak bilangan bulat relatif prima, dan kembali sqrt(6 * N / #coprime)
.
TL; DR
Tantangan-tantangan ini adalah simulasi algoritma yang hanya membutuhkan alam dan otak Anda (dan mungkin beberapa sumber daya yang dapat digunakan kembali) untuk memperkirakan Pi. Jika Anda benar-benar membutuhkan Pi selama kiamat zombie, metode ini tidak membuang - buang amunisi ! Ada delapan tantangan lagi yang akan datang. Periksa pos kotak pasir untuk membuat rekomendasi.
Simulasi
Apa yang kita simulasikan? Nah, probabilitas bahwa dua bilangan bulat acak relatif prima (yaitu coprime atau gcd == 1) adalah 6/Pi/Pi
, jadi cara alami untuk menghitung Pi adalah dengan meraup dua ember (atau beberapa genggam) batu; hitung mereka; lihat apakah gcd mereka adalah 1; ulangi. Setelah melakukan ini beberapa kali, sqrt(6.0 * total / num_coprimes)
akan cenderung ke arah Pi
. Jika menghitung akar kuadrat dalam dunia pasca-apokaliptik membuat Anda gugup, jangan khawatir! Ada Metode Newton untuk itu.
Bagaimana kita mensimulasikan ini?
- Ambil input
N
- Lakukan waktu berikut
N
:- Secara seragam menghasilkan bilangan bulat positif acak,
i
danj
- Dengan
1 <= i , j <= 10^6
- Jika
gcd(i , j) == 1
:result = 1
- Lain:
result = 0
- Secara seragam menghasilkan bilangan bulat positif acak,
- Ambil jumlah
N
hasil,S
- Kembali
sqrt(6 * N / S)
Spesifikasi
- Memasukkan
- Fleksibel, mengambil input dengan cara standar apa pun (mis. Parameter fungsi, STDIN) dan dalam format standar apa pun (mis. String, Binary)
- Keluaran
- Fleksibel, memberikan hasil dengan cara standar apa pun (mis. Mengembalikan, mencetak)
- Ruang putih, trailing dan ruang putih utama dapat diterima
- Akurasi, harap berikan setidaknya 4 tempat desimal akurasi (yaitu
3.1416
)
- Mencetak gol
- Kode terpendek menang!
Uji Kasus
Output Anda mungkin tidak sejalan dengan ini, karena kebetulan acak. Tetapi rata-rata, Anda harus mendapatkan akurasi sebanyak ini untuk nilai yang diberikan N
.
Input -> Output
----- ------
100 -> 3.????
10000 -> 3.1???
1000000 -> 3.14??
sumber
N = 1000000
atau apakah itu ok jika program kembali misalnya stack overflow jikaN
terlalu besar?N=10^6
.Jawaban:
APL, 23 byte
Penjelasan:
?⍵2⍴1e6
: menghasilkan matriks 2-by-⍵ dari angka acak dalam rentang [1..10 6 ]1+.=∨/
: dapatkan GCD dari setiap pasangan dan lihat berapa banyak yang sama dengan 1. Ini menghitung S..5*⍨6×⍵÷
: (6 × ⍵ ÷ S) 0,5sumber
Jelly ,
20 1816 byte-2 bytes terima kasih kepada @ Pietu1998 (rantai & gunakan hitungan 1s,
ċ1
di tempat kurang dari dua dijumlahkan<2S
)-2 byte terima kasih kepada @Dennis (ulangi 1e6 beberapa kali sebelum pengambilan sampel untuk menghindari rantai)
(Sangat lambat karena fungsi acak)
Bagaimana?
TryItOnline
sumber
ḤRµȷ6Xµ€g2/ċ1÷³6÷½
menghemat 2 byte. (ȷ6
adalah 10 ^ 6 dalam satu nilad,ċ1
termasuk yang)ȷ²
ini sedikit lebih cepat daripadaȷ6
)ȷ²
menjadi dua tautan tidak ada salahnya di sini, tetapi akan membutuhkan tautan tambahan atau¤
untuk beberapa kasus penggunaanḤȷ6xX€
harus bekerja untuk pengambilan sampel acak.Python 2,
143140132124122124122 byteSudah cukup lama sejak saya mencoba bermain golf, jadi saya mungkin melewatkan sesuatu di sini! Akan memperbarui saat saya mempersingkat ini.
Uji saya di sini!
terima kasih kepada Jonathan Allan untuk save dua byte :)
sumber
1 <= i , j <= 10^6
,, jadi Anda perlu menggunakannyarandrange(1,1e6+1)
.k=lambda:r.randrange(1e6)+1
menghemat dua byteMathematica,
494851 byteMenyimpan satu byte dan memperbaiki satu bug berkat @ LegionMammal978 .
sumber
(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
1*^6
harus diganti dengan{1,1*^6}
untuk memastikan bahwa saya , j ≠ 0.R,
1039995999894 byteMungkin bisa bermain golf sedikit. Kurangi 4 byte karena @ antoine-sac, dan 4 byte lainnya dengan mendefinisikan alias untuk
sample
, menggunakan^.5
bukansqrt
, dan1e6
bukannya10^6
. Menambahkan 4 byte untuk memastikan bahwa pengambilan sampeli
danj
benar-benar seragam. Dihapus satu byte setelah saya menyadari bahwa6*N/sum(x)
itu sama dengan6/mean(x)
. Digunakanpryr::f
alih-alihfunction(x,y)
menyimpan 4 byte.Output sampel:
sumber
sample(10^6,N)
. Tidak hanya lebih pendek, tetapi juga jauh lebih efisien.sample(10,10)
dijamin untuk mengembalikan semua angka dalam 1:10, sedangkansample(10,10,T)
akan menghasilkan pemilihan acak di mana angka dapat diulang.Sebenarnya, 19 byte
Cobalah online!
Penjelasan:
sumber
MATL , 22 byte
Cobalah online!
sumber
Pyth, 21 byte
Cobalah online.
Penjelasan
sumber
Scala,
149126 bytePenjelasan:
sumber
6f
,Seq.fill
danmath.random
.Racket 92 byte
Tidak Disatukan:
Pengujian:
Keluaran:
sumber
JavaScript (ES7),
1079594 byteVersi ES6 tepat 99 byte, tetapi operator eksponensial ES7
**
menghemat lebih dari 5 byteMath.sqrt
.Tidak disatukan
sumber
gcd
memanggil fungsig
r=_=>
apakah itu kode atau gambar?n=>(n*6/(r=_=>Math.random()*1e6,g=(a,b)=>b?g(b,a%b):a>-2,q=n=>n&&g(~r(),~r())+q(n-1))(n))**.5
1B lebih pendekn=>(n*6/(q=_=>n--&&q(r=_=>Math.random()*1e6)+g(~r(),~r()))(g=(a,b)=>b?g(b,a%b):a>-2))**.5
PHP,
827774 byteJalankan seperti ini:
Penjelasan
Lakukan apa yang tertulis di kaleng. Membutuhkan PHP_GMP untuk
gcd
.Tweaks
$argn
sumber
Perl, 64 byte
Membutuhkan opsi baris perintah
-pMntheory=gcd
, dihitung sebagai 13. Input diambil dari stdin.Contoh Penggunaan
sumber
R, 94 byte
Relatif lambat tapi masih berfungsi. Gandakan N kali fungsi yang mengambil 2 angka acak (dari 1 hingga 1e6) dan memeriksa apakah gcdnya kurang dari 2 (menggunakan fungsi gcd lama milik saya ).
sumber
1:x
akan berhasil.PowerShell v2 +,
118114 byteMengambil input
$n
, memulaifor
loop hingga$k
sama dengan$n
(tersirat$k=0
saat pertama kali memasuki loop). Setiap iterasi, dapatkanRandom
nomor baru$i
dan$j
( flag-mi
nimum1
memastikan kami>=1
dan tidak ada flag maksimum[int]::MaxValue
yang diizinkan, yang diizinkan oleh OP karena lebih besar dari10e6
).Kami kemudian pergi ke loop GCD
while
. Lalu, selama GCD1
,$o
bertambah. Pada akhirfor
loop, kami melakukan[math]::Sqrt()
panggilan sederhana , yang dibiarkan pada pipa dan output tersirat.Butuh sekitar 15 menit untuk menjalankan dengan input
10000
pada laptop Core i5 saya ~ 1 tahun.Contohnya
sumber
Java 8,
164151 bytePenjelasan
Uji Harness
Memperbarui
sumber
n
,t+=1
bisa menjadit++
, Anda bisa menyingkatint
deklarasi Anda menjadi satu baris, yaituint c=n,t=0,x,y;
, dan!=0
(saya pikir) bisa menjadi>0
. Itu harus menyimpan 12 byte secara keseluruhan. Itu cara yang rapi untuk menemukan GCD x dan y.Perl 6 ,
5653 byteCobalah online!
sumber
Frink,
8489Saya beruntung: g = n = ... menyimpan byte lebih dari g = 0 n = ... ; dan 1% gcd () memberi (0,1) vs (1,0) sehingga saya bisa mengurangi. Dan sial: n sudah ditugaskan dan a digunakan karena variabel lingkaran dan batas mereka lokal dan terdefinisi luar loop.
Verbose
sumber
AWK , 109 byte
Cobalah online!
Saya terkejut bahwa itu berjalan dalam jumlah waktu yang wajar untuk 1000000.
sumber
Pyt ,
3735 bytePenjelasan:
sumber
J, 27 Bytes
Penjelasan:
Cukup beruntung dengan
3.14157
forN = 10000000
, yang butuh beberapa2.44
detik.sumber
Japt , 23 byte
Cobalah
sumber