Tugas ini adalah tentang menulis kode untuk menghitung probabilitas dengan tepat. 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 digabungkan A
dengan nilai pertama. Itu A[1] = A[n+1]
jika pengindeksan dari 1. A
sekarang memiliki panjang n+1
. 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.
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 adalah 0
dan 2
.
Sekarang perhatikan produk dalam A[1,...,n]
dan B
dan produk dalam A[2,...,n+1]
dan B
.
Kode Anda harus menampilkan probabilitas bahwa kedua produk dalam adalah nol.
Untuk n=1
probabilitas ini jelas 1/2
.
Saya tidak keberatan bagaimana n
ditentukan dalam kode tetapi itu harus sangat sederhana dan jelas cara mengubahnya.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan perpustakaan apa saja yang Anda suka. Saya ingin menjalankan kode Anda jadi harap sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di linux jika memungkinkan.
n
akan sangat membantu. Mungkin juga contoh eksplisit dari A, B dan dua produk dalam mungkin membantu.n=4
dihitung sebagai nol, dua atau tiga byte? Apakah hasilnya harus persisa/b
atau akan[a b]
, mis., Diizinkan?n
? Kalau tidak, saya pikir itu tidak diperbolehkan.Jawaban:
Pyth,
48474644 byteCobalah online: Peragaan
Versi online mungkin tidak menghitung
n=6
. Di laptop saya (versi offline) dibutuhkan sekitar 45 detik.Pendekatan kekerasan.
Penjelasan:
sumber
+0r1_2
lebih pendek dari/R2r2_2
.Mathematica,
159100878685 byteUntuk mengubah,
n
cukup ubah definisi variabel di awal.Karena ini kekuatan kasar, ini cukup lambat, tetapi inilah delapan hasil pertama:
Yang terakhir sudah mengambil 231 detik dan runtime sangat eksponensial.
Penjelasan
Seperti yang saya katakan itu brute force. Pada dasarnya, saya hanya menghitung semua yang mungkin
A
danB
, menghitung dua produk titik untuk setiap pasangan yang memungkinkan dan kemudian menemukan sebagian kecil dari pasangan yang menghasilkan{0, 0}
. Combinatorics dan fungsi aljabar linear matematika cukup membantu dalam bermain golf ini:Ini menghasilkan semua n-tupel yang mengandung
1
atau-1
, yaitu semua yang mungkinA
. Untukn = 3
itu adalah:Untuk menghitung,
B
kami melakukan hal yang hampir sama:Dengan mengulangi
0
, kami duplikat setiap tupel untuk setiap0
mengandung, sehingga membuat0
dua kali lebih mungkin sebagai1
atau-1
. Sekali lagi menggunakann = 3
sebagai contoh:Sekarang, untuk setiap kemungkinan
A
, kami ingin produk titik dari masing-masing yang mungkinB
, baik denganA[1 .. n]
danA[2 .. n+1]
. Misalnya jika saat ini kamiA
adalah{1, 1, -1}
, kami ingin dot produk dengan baik{1, 1, -1}
dan dengan{1, -1, 1}
. Karena semua kitaB
sudah dengan nyaman baris dari matriks, kami ingin dua sublistsA
sebagai kolom dari matriks lain, sehingga kami dapat menghitung produk titik sederhana di antara mereka. Tetapi transposing{{1, 1, -1}, {1, -1, 1}}
hanya memberikan{{1, 1}, {1, -1}, {-1, 1}}
yang hanya daftar semua sub-siklik 2-elemen dariA
. Itulah yang dilakukan:Jadi kami menghitungnya dan mengambil produk titik dengan daftar kami
B
. Karena sekarang kami mendapatkan daftar bersarang (karena setiap kemungkinanA
menghasilkan vektor terpisah), kami meratakannya dengan##&@@
.Untuk mengetahui apakah suatu pasangan
{x, y}
adalah{0, 0}
kita menghitung diSign[Norm[{x,y}]]
manaNorm
memberi√(x²+y²)
. Ini memberi0
atau1
.Akhirnya, karena kita sekarang hanya ingin mengetahui fraksi
1
s dalam daftar0
s dan1
s semua yang kita butuhkan adalah rata-rata aritmatika dari daftar. Namun, ini menghasilkan probabilitas kedua produk setidaknya satu titik menjadi nol, jadi kami kurangi dari itu1
untuk mendapatkan hasil yang diinginkan.sumber
Pyth -
6555 byteBug diperbaiki dengan pengurangan fraksi dengan biaya satu byte.
Menggunakan pendekatan brute force, dan bisa bermain golf sangat, tetapi hanya ingin mendapatkan sesuatu di luar sana. Sangat lambat
Menggunakan produk Cartesian untuk menghasilkan keduanya
A
danB
, melakukan probabilitas variabel dengan membuat0
muncul dua kali dalam daftar sumber dan kemudian menghitung yang produk dalam nol. Produk dalam dipermudah olehV
gula sintaksis ectorization. Menyederhanakan fraksi membuat saya takut pada awalnya, tetapi cukup mudah denganP
fungsi Factorization rime dan kesadaran bahwa kita hanya perlu mengurangi dengan kekuatan 2.Cobalah online di sini .
sumber
n
?CJam,
5857545146 byteUntuk menjalankannya, masukkan bilangan bulat yang diinginkan antara
WX]
danm*
.Terima kasih kepada @ jimmy23013 untuk bit magic dan untuk bermain golf 5 byte!
Cobalah online di penerjemah CJam .
Ide
Sebagian besar jawaban ini mudah, tetapi menggunakan dua trik:
Alih-alih memasangkan semua vektor {-1, 1} n dengan semua vektor {-1, 0, 1} n dengan probabilitas yang diinginkan, ia menghitung jumlah triplet vektor dalam {-1, 1} n yang memenuhi suatu kondisi tertentu.
Jika kita menambahkan dua vektor terakhir dari triplet, hasilnya akan menjadi vektor {-2, 0, 2} n .
Karena (-1) + 1 = 0 = 1 + (-1) , 0 s akan muncul dua kali lebih sering dari -2 s dan 2 s.
Membagi setiap komponen dengan 2 akan menghasilkan vektor {-1, 0, 1} n dengan probabilitas yang diinginkan.
Karena kami hanya tertarik jika produk skalar 0 atau tidak, kami dapat melewati divisi dengan 2 .
Setelah menghitung semua kembar tiga yang memenuhi kondisi pertanyaan dan jumlah total kembar tiga, kita harus mengurangi fraksi yang dihasilkan.
Alih-alih menghitung GCD dari kedua angka, karena penyebut akan selalu menjadi kekuatan 2, cukup untuk membagi kedua angka dengan kekuatan tertinggi 2 yang membagi pembilang.
Untuk mendapatkan kekuatan tertinggi 2 yang membagi x , kita dapat mengambil bitwise AND dari x dan ~ x + 1 .
~ x membalikkan semua bit x , jadi semua trailing 0 s menjadi 1 s. Dengan menambahkan 1 ke ~ x , mereka 1 s akan kembali menjadi 0 dan yang terakhir 1 di ~ x + 1 akan cocok terakhir 1 di x .
Semua bit lainnya baik baik 0 dari yang berbeda, sehingga bitwise DAN mengembalikan bilangan bulat yang terdiri dari yang terakhir 1 dari x dan semua 0 s yang mengikutinya. Ini adalah kekuatan tertinggi 2 yang membagi x .
Kode
sumber
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__W*&:T/'/@,T/
.