Saya sebelumnya menanyakan pertanyaan bagaimana menghitung probabilitas dengan cepat dan akurat. Namun, ternyata itu terlalu mudah karena diberikan solusi bentuk tertutup! Ini versi yang lebih sulit.
Tugas ini adalah tentang menulis kode untuk menghitung probabilitas secara tepat dan cepat . Outputnya harus berupa probabilitas tepat yang ditulis sebagai pecahan dalam bentuk yang paling dikurangi. Itu seharusnya tidak pernah output 4/8
melainkan 1/2
.
Untuk beberapa bilangan bulat positif n
, pertimbangkan string acak seragam panjang 1s dan -1s n
dan menyebutnya A. Sekarang gabungkan ke A
salinan itu sendiri. Itu A[1] = A[n+1]
jika pengindeksan dari 1, A[2] = A[n+2]
dan sebagainya. A
sekarang memiliki panjang 2n
. Sekarang juga pertimbangkan string acak kedua panjang n
dengan n
nilai pertama -1, 0, atau 1 dengan probabilitas 1 / 4,1 / 2, masing-masing 1/4 dan menyebutnya B.
Sekarang pertimbangkan produk dalam B
dengan A[1+j,...,n+j]
untuk yang berbeda j =0,1,2,...
.
Sebagai contoh, pertimbangkan n=3
. Nilai yang mungkin untuk A
dan B
bisa A = [-1,1,1,-1,...]
dan B=[0,1,-1]
. Dalam hal ini dua produk dalam yang pertama adalah 0
dan 2
.
Tugas
Untuk masing-masing j
, dimulai dengan j=1
, kode Anda harus menampilkan probabilitas bahwa semua j+1
produk dalam pertama adalah nol untuk setiap n=j,...,50
.
Menyalin tabel yang diproduksi oleh Martin Büttner untuk j=1
kami memiliki hasil sampel berikut.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Skor
Skor Anda adalah j
kode terbesar yang Anda selesaikan dalam 1 menit di komputer saya. Untuk menjelaskan sedikit, masing j
- masing mendapat satu menit. Perhatikan bahwa kode pemrograman dinamis dalam pertanyaan terkait sebelumnya akan melakukan ini dengan mudah j=1
.
Pemutus dasi
Jika dua entri mendapatkan j
skor yang sama maka entri yang menang akan menjadi yang tertinggi n
dalam satu menit pada mesin saya untuk itu j
. Jika dua entri terbaik sama pada kriteria ini juga maka pemenangnya adalah jawaban yang dikirimkan terlebih dahulu.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan perpustakaan yang tersedia secara bebas yang Anda suka. Saya harus dapat menjalankan kode Anda jadi tolong sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di linux jika memungkinkan.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda.
Entri yang menang
j=2
dalam Python oleh Mitch Schwartz.j=2
dalam Python oleh feersum. Saat ini entri tercepat.
sumber
Jawaban:
Python 2, j = 2
Saya mencoba menemukan semacam 'bentuk tertutup' untuk j = 2. Mungkin saya bisa membuat gambar MathJax tentang itu, meskipun itu akan sangat jelek dengan semua indeks mengutak-atik. Saya menulis kode yang tidak dioptimalkan ini hanya untuk menguji formula. Diperlukan sekitar 1 detik untuk menyelesaikannya. Hasilnya sesuai dengan kode Mitch Schwartz.
Pertimbangkan urutan di mana anggota ke-i adalah
e
jika A [i] == A [i + 1] ataun
jika A [i]! = A [i + 1].i
dalam program ini adalah jumlahn
s. Jikai
genap, urutannya harus dimulai dan diakhiri dengane
. Jikai
ganjil, urutannya harus dimulai dan diakhiri dengann
. Urutan selanjutnya diklasifikasikan berdasarkan jumlah run berturut-turute
s ataun
s. Adaj
+1 dari satu danj
lainnya.Ketika ide random walk diperpanjang untuk 3 dimensi, ada masalah disayangkan bahwa ada 4 kemungkinan arah untuk berjalan di (satu untuk masing-masing
ee
,en
,ne
, ataunn
) yang berarti mereka tidak bergantung linear. Jadik
indeks merangkum jumlah langkah yang diambil di salah satu arah (1, 1, 1). Kemudian akan ada jumlah langkah yang tepat yang harus diambil di 3 arah lainnya untuk membatalkannya.P (n, p) memberikan jumlah partisi n objek yang terurut menjadi p bagian. W (l, d) memberikan sejumlah cara untuk berjalan acak
l
langkah - langkah untuk menempuh jarak yang tepatd
. Seperti sebelumnya ada 1 kesempatan untuk bergerak ke kiri, 1 peluang untuk bergerak ke kanan dan 2 untuk tetap di tempat.sumber
j=3
. Itu akan luar biasa!Python, j = 2
Pendekatan pemrograman dinamis
j = 1
dalam jawaban saya untuk pertanyaan sebelumnya tidak perlu banyak modifikasi untuk bekerja lebih tinggij
, tetapi menjadi lambat dengan cepat. Tabel untuk referensi:Dan kodenya:
Di sini kita melacak dua elemen pertama
A
, dua elemen terakhir dariB
(di manab2
adalah elemen terakhir), dan produk-produk batin(A[:n], B)
,(A[1:n], B[:-1])
dan(A[2:n], B[:-2])
.sumber