Tujuan
Hasilkan ( N
) segmen garis acak dengan panjang seragam ( l
), periksa apakah mereka melintasi t
garis paralel yang sama ( ).
Simulasi
Apa yang kita simulasikan? Jarum Buffon . Menghaluskan pasir di kotak pasir Anda, menggambar satu set garis paralel sama spasi (panggilan jarak di antara t
). Ambil tongkat panjang lurus l
dan jatuhkan N
kali ke dalam kotak pasir. Biarkan berapa kali melewati batas c
. Lalu Pi = (2 * l * n) / (t * c)
!
Bagaimana kita mensimulasikan ini?
- Ambil input
N,t,l
- Dengan
N, t, l
semua bilangan bulat positif - Lakukan waktu berikut
N
:- Hasilkan koordinat bilangan bulat acak yang seragam
x,y
- Dengan
1 <= x, y <= 10^6
x,y
adalah pusat segmen garis panjangl
- Hasilkan bilangan bulat acak seragam
a
- Dengan
1 <= a <= 180
- Membiarkan
P
menjadi titik di mana segmen garis akan melintasi sumbu x - Lalu
a
adalah sudutnya(x,y), P, (inf,0)
- Hasilkan koordinat bilangan bulat acak yang seragam
- Hitung jumlah,
c
segmen segmen yang melewati garisx = i*t
untuk bilangan bulat apa puni
- Kembali
(2 * l * N) / (t * c)
Spesifikasi
- Memasukkan
- Fleksibel, mengambil input dengan cara standar apa pun (misalnya 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, t, l
.
Input (N,t,l) -> Output
----------- ------
10,10,5 -> ?.????
10,100,50 -> ?.????
1000,1000,600 -> 3.????
10000,1000,700 -> 3.1???
100000,1000,700 -> 3.14??
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 sembilan tantangan total.
a
juga dibuat dengan metode lain, jika seragam? (memikirkan Bubble Gauss 2D)t > l
? Dua solusi di bawah ini membuat asumsi ini, yang menyederhanakan pemeriksaan untuk persimpangan cukup sedikit.Jawaban:
R,
1131007570686765596357 byteSebagai bahasa pemrograman statistik dan fungsional, tidak mengherankan bahwa R cukup cocok untuk tugas semacam ini. Fakta bahwa sebagian besar fungsi dapat mengambil input vektor sangat membantu untuk masalah ini, karena alih-alih mengulangi
N
iterasi, kami hanya membagikan vektor ukuranN
. Terima kasih kepada @Billywob untuk beberapa saran yang mengarah pada pemotongan 4 byte Banyak terima kasih kepada @Primo karena dengan sabar menjelaskan kepada saya bagaimana kode saya tidak berfungsi untuk kasus-kasus di manat > l
, yang sekarang sudah diperbaiki.Cobalah online!
Output sampel:
Penjelasan
Masalahnya adalah untuk menentukan apakah dua
x
nilai jarum berada di kedua sisi garis paralel. Ini memiliki beberapa konsekuensi penting:y
-nilai tidak relevanx
-axis tidak relevan, hanya posisi relatif terhadap garis paralel terdekat.Pada dasarnya ini adalah tugas dalam ruang 1-dimensi, di mana kami menghasilkan garis dengan panjang dalam [0,
l
] (suduta
menentukan panjang ini), dan kemudian kami memeriksa untuk melihat berapa kali panjang ini melebihit
. Algoritma kasarnya adalah:x1
Nilai sampel dari [0, 1000000]. Karena garis paralel terjadi pada setiapt
titik sepanjangx
-axis, posisi relatifnyax
adalahx
modulot
.a
.x2
posisi berdasarkana
.x1+x2
cocokt
, yaitu mengambil lantai(x1+x2)/t
.Pengambilan
N
angka angka dalam [0, 1e6] modulot
setara dengan hanya pengambilan sampelN
angka dalam [0,t
]. Karena(x1+x2)/t
sama denganx1/t + x2/t
, langkah pertama menjadi pengambilan sampel dari [0,t
] /t
, yaitu [0, 1]. Beruntung bagi kami, itu adalah rentang default untukrunif
fungsi R , yang mengembalikanN
bilangan real dari 0 ke 1 dari distribusi yang seragam.Kami ulangi langkah ini untuk menghasilkan
a
, sudut jarum.Angka-angka ini ditafsirkan sebagai setengah putaran (yaitu
.5
90 derajat). (OP meminta derajat dari 1 hingga 180, tetapi dalam komentar itu diklarifikasi bahwa metode apa pun diperbolehkan jika itu sebagai atau lebih tepat.) Untuk sudutθ
,sin(θ)
memberi kita jarak sumbu x antara ujung-ujung jarum. (Biasanya Anda akan menggunakan cosinus untuk sesuatu seperti ini; tetapi dalam kasus kami, kami mempertimbangkan sudutθ
sebagai relatif terhadap sumbu y, bukan sumbu x (yaitu, nilai 0 derajat naik , bukan kanan ), dan oleh karena itu kami menggunakan sinus, yang pada dasarnya fase-menggeser angka.) Dikalikan denganl
ini memberi kitax
lokasi ujung jarum.Sekarang kita bagi
t
dan tambahkanx1
nilainya. Ini menghasilkan(x1+x2)/t
, yang sejauh mana jarum menonjol darix1
, dalam hal jumlah garis paralel. Untuk mendapatkan bilangan bulat dari berapa banyak garis yang dilintasi, kita ambilfloor
.Kami menghitung jumlahnya, memberi kami hitungan
c
berapa banyak garis yang dilintasi oleh jarum.Sisa kode hanya mengimplementasikan rumus untuk perkiraan pi, yaitu
(2*l*N)/(t*c)
,. Kami menyimpan beberapa byte pada tanda kurung dengan mengambil keuntungan dari kenyataan bahwa(2*l*N)/(t*c) == 2*l*N/t/c
:Dan semuanya dibungkus menjadi fungsi anonim:
sumber
(2*l*N) => 2*l*N
?(2*l*N)/(t*c) = 2*l*N/t/c
jadi Anda bisa menyimpan dua byte lagi dengan melewatkan tanda kurung di bagian terakhir juga.Perl, 97 byte
Menghitung shebang sebagai satu, input diambil dari stdin, dipisahkan oleh ruang. Jika nilai acak non-integer diizinkan, ini bisa menjadi lebih pendek.
Saya telah mengambil satu kebebasan, kira-kira π / 180 sebagai 71/4068 , yang akurat dalam 1,48 · 10 -9 .
Contoh Penggunaan
Pergantian matematis yang kurang lebih setara
Dengan asumsi koordinat x mewakili titik paling kiri dari jarum, bukan di tengahnya, seperti yang ditentukan dalam deskripsi masalah:
89 byte
Masalahnya menentukan bahwa
x
yang akan dijadikan sampel sebagai integer acak. Jika kita memproyeksikan garis spasi untuk jeda satu, ini akan meninggalkan kita dengan nilai-nilai dari bentukn/t
dengan0 <= n < t
, belum tentu seragam, jikat
tidak merata membagi1e6
. Dengan asumsi bahwa distribusi seragam tetap dapat diterima:76 byte
Perhatikan bahwa karena
rand
akan selalu kurang dari satu (dan karena itu terpotong ke nol), maka tidak perlu pada awal rentang:70 byte
Dengan asumsi bahwa sudut jarum tidak harus berupa bilangan bulat, tetapi hanya acak acak:
59 byte
Dengan asumsi sudut dapat berupa distribusi yang seragam:
52 byte
Di atas adalah simulasi yang tepat secara matematis dari Jarum Buffon. Namun, pada titik ini saya pikir kebanyakan orang akan setuju bahwa ini sebenarnya bukan pertanyaan yang ditanyakan.
Benar-benar mendorongnya
Kita bisa membuang setengah dari kasus uji, setiap kali titik akhir kedua adalah di sebelah kiri yang pertama (daripada menukar mereka):
47 byte
Perhatikan bahwa nilai-nilai
t
danl
tidak penting untuk hasil percobaan. Kita bisa mengabaikannya (secara implisit menganggapnya sama):28 byte
Jelas tidak bersaing, tetapi Anda harus mengakui, itu memang memiliki keanggunan tertentu untuk itu.
sumber
Python 2, 141 byte
pelabuhan rtumbull yang tak tahu malu, sudah terlewati
y
karena sama sekali tidak diperlukan.Masalahnya hanya, pi itu sudah dikenal dalam program.
Ini dia (golf) dengan pi yang tidak diketahui dan tidak ada fungsi trigonometri
x,y
dig
hanya untuk arah.sumber
from random import randint;from math import cos,pi
. Gagal untukt < l
, mis1000000,1000,70000
.