Interviewstreet memiliki CodeSprint kedua pada bulan Januari yang mencakup pertanyaan di bawah ini. Jawaban terprogram diposting tetapi tidak termasuk penjelasan statistik.
(Anda dapat melihat masalah asli dan memposting solusi dengan masuk ke situs web Interviewstreet dengan kredibilitas Google dan kemudian membuka masalah Coin Tosses dari halaman ini .)
Tosses Koin
Anda memiliki koin yang tidak bias yang ingin Anda terus lempar sampai Anda mendapatkan N kepala berturut-turut. Anda telah melemparkan koin M kali dan secara mengejutkan, semua lemparan menghasilkan kepala.
Berapa jumlah lemparan tambahan yang diharapkan yang dibutuhkan sampai Anda mendapatkan N kepala berturut-turut?
Input:
Baris pertama berisi jumlah kasus T. Masing-masing baris T berikutnya berisi dua angka N dan M.
Keluaran:
Garis T keluaran yang berisi jawaban untuk test case yang sesuai. Cetak jawaban dibulatkan hingga tepat 2 angka desimal.
Input Sampel:
4
2 0
2 1
3 3
3 2
Contoh Hasil:
6.00
4.00
0.00
8.00
Contoh Penjelasan:
Jika N = 2 dan M = 0, Anda harus terus melempar koin sampai Anda mendapatkan 2 kepala berturut-turut. Tidak sulit untuk menunjukkan bahwa rata-rata, 6 lemparan koin diperlukan.
Jika N = 2 dan M = 1, Anda perlu 2 kepala berturut-turut dan sudah memiliki 1. Anda harus melemparkan sekali lagi apa pun yang terjadi. Dalam lemparan pertama itu, jika Anda mendapatkan kepala, Anda selesai. Jika tidak, Anda harus memulai dari awal, karena penghitung ulang berurutan mereset, dan Anda harus terus melempar koin sampai Anda mendapatkan N = 2 kepala berturut-turut. Jumlah lemparan koin yang diharapkan adalah 1 + (0,5 * 0 + 0,5 * 6) = 4,0 Jika N = 3 dan M = 3, Anda sudah mendapatkan 3 kepala, jadi Anda tidak perlu lagi melemparkan.
Semua persamaan matematika yang saya buat memiliki jawaban yang tepat untuk data input sampel yang tercantum di atas, tetapi salah untuk semua set input lainnya (yang tidak diketahui). Solusi terprogram mereka tampaknya memecahkan masalah jauh berbeda dari metode coba-untuk-datang-dengan-persamaan-saya. Bisakah seseorang tolong jelaskan bagaimana menghasilkan persamaan yang akan menyelesaikan ini?
sumber
Jawaban:
Ini adalah latihan komputasi, jadi pikirkanlah secara rekursif . Keadaan membalik koin saat ini ditentukan oleh pasangan yang dipesan dengan . Biarkan jumlah flips yang diharapkan untuk mencapai head berturut-turut menjadi :(N,M) N≥M≥0 N e(N,M)
(1) Ada kemungkinan 50% flip berikutnya akan menjadi kepala, membawa Anda ke negara , dan 50% kemungkinan flip berikutnya akan menjadi ekor, membawa Anda ke negara . Ini biaya satu flip. Oleh karena itu harapan (secara rekursif) diberikan oleh(N,M+1) (N,0)
(2) Kondisi dasar: Anda telah menetapkan itu
dan jelas
(tidak perlu membalik lagi).
Inilah program Mathematica yang sesuai (termasuk caching hasil antara untuk mempercepat rekursi, yang secara efektif menjadikannya solusi pemrograman dinamis):
Program akan terlihat serupa dalam bahasa pemrograman lain yang mendukung rekursi. Secara matematis, kita dapat memverifikasi bahwa hanya dengan memeriksa rekursi, karena jelas berlaku untuk kasus dasar:e(N,M)=2N+1−2M+1
yang berlaku untuk setiap dan , QED.M N
Secara lebih umum , pendekatan yang sama akan menetapkan bahwa ketika koin memiliki probabilitas kepala. Bagian yang sulit adalah mengusahakan kondisi dasar . Itu dilakukan dengan mengejar rekursi keluar langkah sampai akhirnya dinyatakan dalam hal itu sendiri dan menyelesaikan:e(N,M)=p−N−p−M1−p p e(N,0) N e(N,0)
sumber
find_x(n)
rekursif jika ia mengatakan sesuatu sepertiif n=0 return 1 else return 2*find_x(n-1)
yangfind_x
menyebut dirinya kali, sedangkan program berulang akan mengatakan sesuatu sepertiy = 1; while n > 0 do begin y=2*y; n=n-1 end; return y
R
) mereka hampir tidak berbeda sama sekali. (Dalam satu kasus Anda membuat dan kemudian memproses vektor1:n
dan di lain Anda akan menemukan bahwan:1
telah ditempatkan pada tumpukan dan diproses secara terbalik.) Tetapi sebagian dari poin saya adalah konseptual : komentar awal Anda berbicara tentang "bekerja secara iteratif." Itu merujuk pada analisis dan bukan pada program komputer mana pun. Tetapi ini adalah hal-hal sepele dan tangensial yang pembahasannya tidak menjamin perpanjangan utas komentar ini.Untuk mengatasi masalah ini, saya akan menggunakan proses stokastik, waktu berhenti, dan pemrograman dinamis.
Pertama, beberapa definisi:
X 0 X 0 = 0 X X 0 = M
Kemudian tentukan waktu berhenti berikut:
Nilai yang kami cari adalah nilai yang diharapkan dari , jumlah flips yang diperlukan untuk mengamati N flips berurutan , mengingat bahwa kami telah mengamati flips beruntun M . Asumsikan sebagai jawabannya sepele 0 sebaliknya. Kami menghitung:τN (XτN=N) (X0=M) M≤N
Yang pertama sesuai dengan jumlah flips yang diharapkan sebelum mendapatkan ekor dengan asumsi ekor terbalik sebelum N kepala berturut-turut diamati dengan asumsi kita mulai dengan M kepala berturut-turut. Tidak terlalu sulit untuk melihatnya
Sekarang yang harus kita lakukan adalah menghitung ekspektasi kondisional kedua yang sesuai dengan jumlah flips yang diharapkan untuk mengamati N head berturut-turut mulai dari 0. Dengan perhitungan yang sama, kita melihat bahwa
Ini memberikan jawaban terakhir:
Ini setuju dengan empat kasus uji yang Anda daftarkan. Dengan jawaban yang begitu sederhana, mungkin ada cara yang lebih mudah untuk menghitung ini.
sumber
Peringatan: yang berikut ini mungkin tidak dianggap sebagai jawaban yang tepat karena tidak memberikan solusi bentuk tertutup untuk pertanyaan, esp. bila dibandingkan dengan jawaban sebelumnya . Namun saya menemukan pendekatan yang cukup menarik untuk mengerjakan distribusi bersyarat.
Pertimbangkan pertanyaan awal untuk mendapatkan urutan head dari throws, dengan probabilitas . Ini diberikan oleh rumus pengulangan Memang, alasan saya adalah bahwa tidak ada head berturut-turut dari draw dapat diuraikan berdasarkan pada kemunculan pertama tail dari yang pertama melempar. Pendingin pada apakah ekor pertama ini terjadi pada pertama, kedua, ..., th menarik mengarah ke hubungan pengulangan ini.N k 1−p(N,k)
Berikutnya, probabilitas mendapatkan N head pertama berturut-turut di throws adalah $$ q (N, m) = \ begin {cases} \ dfrac {1} {2 ^ N} & \ text {jika} m = N \m≥N
$$ Kasus pertama cukup jelas. case kedua sesuai dengan ekor yang terjadi pada undian , diikuti oleh head, dan case terakhir melarang head berturut-turut sebelum undian . (Dua kasus terakhir bisa diringkas menjadi satu, diberikan!)m−N−1 N N m−N−1
Sekarang, probabilitas untuk mendapatkan head pertama dan head berturut-turut pertama tepat di melempar (dan tidak kurang) adalah $$ r (M, N, m) = \ begin {cases} 1/2 ^ N & \ text {if} m = N \M N m≥N
\ end {cases} s (M, N, m) = \ begin {cases} 1 / {2 ^ {NM}} & \ text {if} m = N \ 0 & \ text {if} N \ sum_ {r = M + 1} ^ {N} \ dfrac {q (N, mr)} {2 ^ {rM }} & \ teks {jika} N + M
\ end {cases} \ mathfrak {E} (M, N) = \ sum_ {m = N} ^ \ infty m \, s (M, N, m) $$ atau untuk jumlah langkah tambahan ...
sumber