Saya baru-baru mengambil tes HackerRank untuk posisi Ilmu Data dan mendapatkan pertanyaan ini salah. Saya datang ke 1/200
. Begini caranya:
Ada 50 kombinasi yang akan membuat ini benar. (yaitu {1,2}, {2,4}, {3,6} ... {50.100}). Kemungkinan nomor tertentu yang dipilih adalah 1/100
. Kemungkinan bahwa himpunan spesifik akan dipilih adalah (1/100 * 1/100)
.
Karena ada 50 set,
P=50*(1/100)*(1/100)=1/200
Saya tentu saja dengan asumsi bahwa 1 dan 100 sudah termasuk. Tapi ini jawaban yang salah. Adakah yang bisa membantu saya memahami kesalahan saya?
probability
combinatorics
Jo Bennet
sumber
sumber
Jawaban:
Kesalahan pertama Anda adalah bahwa ada 50 hasil, sebenarnya ada 100 (Edit: Lihat komentar di bawah untuk klarifikasi). Ini karena mendapatkan (1,2) dan (2,1) adalah hasil dari dua hasil yang terpisah, tetapi dalam setiap kasus jumlah yang lebih besar persis dua kali jumlah yang lebih kecil.
Jadi total cara yang mungkin untuk mendapatkan ini sebenarnya diberikan oleh set:
{(1,2), (2,1), (2,4), (4,2), ..., (50,100), (100,50)}
Yang merupakan daftar 100 hasil yang mungkin.
Jumlah total hasil yang mungkin adalah100×99
Karena ada 100 angka yang mungkin untuk dipilih pertama kali, dan kemudian 99 untuk yang kedua karena mereka harus berbeda.
Karenanya jawabannya diberikan oleh:
Dengan menggunakan argumen yang sama, sangat mudah untuk membuktikan bahwa probabilitas untuk kasus yang lebih umum dalam memilih angka dari mana adalah beberapa bilangan positif diberikan oleh:1,2,...,n n
sumber
"Peretas" atas nama pengujian menyarankan agar kami mencoba menemukan solusi berorientasi komputasi.
Karena itu, mari kita mulai dengan program untuk penghitungan kasar (a) kasus "menguntungkan" di mana satu bilangan bulat dua kali lainnya dan (b) semua kasus yang mungkin. Jawabannya kemudian akan menjadi rasio mereka. Saya telah mengkodekan solusi umum. Inputnya adalah bilangan bulat positif
n
dan hasilnya adalah probabilitas.(Bukti kebenaran bergantung pada fakta bahwa untuk angka positif .)i≠2i i
Program ini membutuhkan tes dan hingga peningkatan untuk setiap iterasi loop dalam. Oleh karena itu diperlukan perhitungan antara dan setiap kali loop dalam dilakukan, atau keseluruhan hingga . Itu kinerja : OK untuk kecil seperti , tapi mengerikan sekali melebihi atau lebih.3 3 3n 6n 3n2 6n2 O(n2) n n=100 n 10000
Sebagai seorang hacker, salah satu hal pertama yang ingin Anda lakukan adalah menghilangkan kinerja kuadratik dengan menyederhanakan loop dalam (jika mungkin). Untuk tujuan ini, secara sistematis melalui garis-garis di loop dalam (seperti bernomor) dan perhatikan hal berikut:
Baris 1 dieksekusi semua kecuali satu kali untuk setiap nilain−1
i
dan karenanyaall
bertambah kali. Akibatnya, untuk perhitungan , loop over dapat diganti dengan bertambahnya oleh .all
j
all
n-1
Baris 2 dieksekusi tepat sekali ketika dan sebaliknya tidak sama sekali. Oleh karena itu dapat diganti dengan incrementing oleh setiap kali .2i≤n 1 2i≤n
all
Baris 3 dijalankan setelah disediakan
i
bahkan.Berikut adalah program yang diubah.
Bisakah kita melangkah lebih jauh dan menghilangkan lingkarannya?
Baris 1 'dijalankan kali. Oleh karena itu ditambahkan oleh .n
all
n*(n-1)
Baris 2 'dieksekusi hanya ketika . Salah satu cara untuk menghitung ini adalah (bilangan bulat terbesar kurang dari atau sama dengan ).2i≤n ⌊n/2⌋ n/2
Baris 3 'dijalankan hanya untuk nilai genap . Sekali lagi, itu terjadi kali.i ⌊n/2⌋
Transformasi kedua dari program ini adalah:
Ini sudah merupakan prestasi yang luar biasa: a algoritma telah direduksi menjadi algoritma (yang dapat dianggap sebagai "formula tertutup" untuk jawabannya).O(n2) O(1)
Akhirnya, ada beberapa transformasi aljabar sederhana yang dapat kita lakukan dengan menggulir inisialisasi (baris 0) menjadi penggunaan pertama dari setiap variabel dan menggabungkan garis 2 '' dan 3 '':
Pada titik ini manusia dapat menjalankan program. Mari kita lakukan dengan :n=100
Outputnya adalah .1/99
Untuk meringkas, algoritma brute-force dapat ditransformasikan secara sistematis menggunakan aturan penulisan ulang program sederhana menjadi program ramping, anggun .O(1)
sumber
Pertama-tama, Anda mengambil sampel tanpa penggantian. Dengan demikian, ada 100 * 99 hasil yang berbeda, misalnya (1,1) bukan hasil yang valid.
Kedua, ketertiban tidak masalah. Yang lebih besar harus tepat dua kali, bukan yang kedua. Dengan demikian, hilangkan pasangan simetris.
Jadi, 50 dari (100) * 99/2 positif, atau 1/99
sumber