Bab ACM lokal saya memberikan hadiah langsung kepada orang-orang yang datang ke pertemuan. Namun, Anda mendapat peluang menang yang lebih besar jika Anda memecahkan teka-teki pemrograman (tapi saya selalu memecahkan teka-teki itu). Jadi, beberapa orang memiliki 1 entri, sementara yang lain memiliki 2. Tapi tunggu! Cara kerja program undian tidak dengan menambahkan entri lain ketika seseorang memecahkan teka-teki. Alih-alih, ia melacak jumlah "nyawa" yang dimiliki seseorang, menyatakan bahwa jika orang itu dipilih di setiap pass dari algoritma pengambilan sampel acaknya. Jadi kerjanya seperti ini:

Doorknob: 1.  xnor: 2.  Justin: 2.  Alex: 1.  Dennis: 2.

Kemudian program secara acak memilih salah satu dari [Doorknob, xnor, Justin, Alex, Dennis], mengurangi nomornya (katakan itu pilih Justin):

Doorknob: 1.  xnor: 2.  Justin: 1.  Alex: 1. Dennis: 2.

Dan berulang. Jika jumlah "kehidupan" seseorang masuk ke 0(mari kita pilih Justinlagi), mereka dihapus dari daftar:

Doorknob: 1.  xnor: 2.  Alex: 1.  Dennis: 2.

Ini berlanjut sampai ada satu orang yang tersisa; orang itu adalah pemenangnya.

Sekarang pertanyaan sebenarnya adalah, berapa probabilitas saya akan menang?

Anda akan diberikan dua input:

• n. Ini adalah jumlah orang yang ikut tantangan
• k. Ini adalah jumlah orang (dari mereka n) yang memiliki 2 nyawa. Nomor ini selalu termasuk Anda.

Jadi jika saya memiliki fungsi pdan menelepon p(10, 5), itu akan menjadi probabilitas untuk memenangkan hadiah di mana ada total 10 orang, 5 di antaranya hanya memiliki 1 kehidupan, sedangkan 5 (termasuk Anda) memiliki 2 kehidupan.

Anda diharapkan menghasilkan probabilitas untuk menang tepat, atau sebagai desimal. Bagaimanapun, jawaban harus akurat hingga dan termasuk tempat desimal ^ke- 4 setelah titik desimal. Apakah Anda membulatkan ke angka itu terserah Anda.

Solusi Anda mungkin menjadi solusi acak yang output jawaban untuk 4 ^th tempat desimal dengan probabilitas tinggi . Anda dapat berasumsi bahwa RNG bawaan yang Anda gunakan benar-benar acak, dan harus menghasilkan jawaban yang benar dengan setidaknya 90% probabilitas.

Selain itu, kode Anda hanya perlu berfungsi n, k <= 1000, meskipun saya memang memberikan kasus uji lebih besar dari itu untuk mereka yang penasaran.

Uji Kasus

Catatan: beberapa di antaranya adalah rumus umum.

n,    k   |  output
----------+---------
1,    1   |  1
2,    2   |  0.5
2,    1   |  0.75
3,    1   |  11/18 = 0.611111111
1000, 1   |  0.007485470860550352
4,    3   |  0.3052662037037037
k,    k   |  1/k
n,    1   |  (EulerGamma + PolyGamma[1 + n])/n    (* Mathematica code *)
          |  (γ + ψ(1 + n))/n
10,   6   |  0.14424629234373537
300,  100 |  0.007871966408910648
500,  200 |  0.004218184180294532
1000, 500 |  0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 |  0.0009518052922680399
5000, 901 |  0.0007632938197806958

Untuk beberapa cek lainnya, lakukan hal p(n, 1) * nberikut:

n     |  output
------+---------
1     | 1
2     | 1.5 
3     | 1.8333333333333335
10    | 2.928968253968254
100   | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305

MATL , 42 byte

:<~QXJx`J`tf1Zry0*1b(-tzq]f1=vts3e8<]6L)Ym

Ini menggunakan pendekatan probabilistik (Monte Carlo). Percobaan dijalankan sejumlah besar kali, dari mana probabilitas diperkirakan. Jumlah realisasi dipilih untuk memastikan bahwa hasilnya benar hingga desimal keempat dengan probabilitas setidaknya 90%. Namun, ini membutuhkan waktu yang sangat lama dan banyak memori. Dalam tautan di bawah ini, jumlah realisasi telah dikurangi dengan faktor 10 ⁶ sehingga program berakhir dengan waktu yang wajar; dan hanya desimal pertama yang dijamin akurat dengan probabilitas setidaknya 90%.

EDIT (29 Juli 2016): karena perubahan bahasa, 6Lperlu diganti oleh 3L. Tautan di bawah ini memasukkan modifikasi itu.

Cobalah online!

Latar Belakang

Biarkan p menyatakan probabilitas untuk dihitung. Percobaan yang dijelaskan dalam tantangan akan dijalankan untuk sejumlah n kali. Setiap kali, Anda memenangkan hadiah (" sukses ") atau tidak. Biarkan N menjadi jumlah keberhasilan. Probabilitas yang diinginkan dapat diperkirakan dari N dan n . Semakin besar n , semakin akurat perkiraannya. Pertanyaan kuncinya adalah bagaimana memilih n untuk memenuhi keakuratan yang diinginkan, yaitu, untuk memastikan bahwa setidaknya 90% dari kesalahan akan kurang dari 10 ⁻⁴ .

Metode Monte Carlo bisa

• Ukuran tetap : nilai n diperbaiki sebelumnya (dan kemudian N acak);
• Variabel-ukuran : n ditentukan dengan cepat oleh hasil simulasi.

Di antara kategori kedua, metode yang umum digunakan adalah untuk memperbaiki N (jumlah keberhasilan yang diinginkan) dan terus mensimulasikan sampai jumlah keberhasilan tersebut tercapai . Jadi n adalah acak. Teknik ini, yang disebut pengambilan sampel binomial terbalik atau negatif-binomial Monte Carlo , memiliki keuntungan bahwa keakuratan estimator dapat dibatasi. Untuk alasan ini akan digunakan di sini.

Secara khusus, dengan Monte Carlo binomial-negatif x = ( N −1) / ( n −1) adalah penduga yang tidak bias dari p ; dan probabilitas bahwa x menyimpang dari p dengan lebih dari rasio yang diberikan dapat dibatasi. Menurut persamaan (1) dalam makalah ini (perhatikan juga bahwa kondisi (2) terpenuhi), mengambil N = 2.75 · 10 ⁸ atau lebih besar memastikan bahwa p / x termasuk dalam interval [1.0001, 0.9999] dengan setidaknya 90% kemungkinan. Secara khusus, ini menyiratkan bahwa x adalah benar hingga ke tempat desimal ke-4 dengan probabilitas setidaknya 90%, seperti yang diinginkan.

Kode dijelaskan

Kode menggunakan N = 3e8untuk menyimpan satu byte. Perhatikan bahwa melakukan banyak simulasi ini akan memakan waktu lama. Kode dalam tautan menggunakan N = 300, yang berjalan dalam jumlah waktu yang lebih masuk akal (kurang dari 1 menit dalam kompiler online untuk kasus uji pertama); tetapi ini hanya memastikan bahwa desimal pertama benar dengan probabilitas setidaknya 90%.

:        % Take k implicitly. Range [1 ... k]
<~       % Take n implicitly. Determine if each element in the previous array is
         % less than or equal than n
Q        % Add 1. This gives an array [2 ... 2 1 ... 1]
XJx      % Copy to clipboard J. Delete from stack
`        % Do...while. Each iteration is a Monte Carlo realization, until the 
         % desired nunber of successes is reached
  J      %   Push previously computed array [2 ... 2 1 ... 1]
  `      %   Do...while. Each iteration picks one door and decrements it, until
         %   there is only one
    t    %     Duplicate
    f    %     Indices of non-zero elements of array
    1Zr  %     Choose one of them randomly with uniform distribution
    y0*  %     Copy of array with all values set to 0
    1b(  %     Assign 1 to chosen index
    -    %     Subtract
    tzq  %     Duplicate. Number of nonzero elements minus 1. This is falsy if
         %     there was only one nonzero value; in this case the loop is exited
  ]      %   End do...while
  f1=    %   Index of chosen door. True if it was 1 (success), 0 otherwise
  v      %   Concatenate vertically to results from previous realizations
  ts3e8< %   Duplicate. Is the sum less than 3e8? If so, the loop is exited
]        % End do...while
6L)      % Remove last value (which is always 1)
Ym       % Compute mean. This gives (N-1)/(n-1). Implicitly display

Pyth, 34 byte

Mc|!*HJ-GHch*J+*tHgGtH*gtGHKh-GHKG

Suite uji

Menentukan fungsi rekursif memoized deterministik dengan gmengambil n , k sebagai argumen. g 1000 500kembali 0.0018008560286627952dalam waktu sekitar 18 detik (tidak termasuk dalam test suite di atas karena waktu habis penerjemah online).

Perkiraan terjemahan Python 3 akan menjadi

@memoized
def g(n,k):
    return (not k*(n-k) or (1+(n-k)*((k-1)*g(n,k-1)+g(n-1,k)*(n-k+1)))/(n-k+1))/n

JavaScript (ES6), 65 byte

f=(n,k,d=n-k)=>(!d||(f(n-1,k)*++d*--d+1+(--k&&f(n,k)*k*d))/++d)/n

Jangan mencobanya dengan angka besar; bahkan f (30, 10) membutuhkan banyak waktu.