Analisis teori algoritma yang mengembalikan benar atau salah, berdasarkan kajian kebarangkalian yang diberikan

Question

Saya ingin melaksanakan kaedah yang mengembalikan benar dengan kebarangkalian n/m dan palsu dengan kebarangkalian (m-n)/m. Sebagai contoh, saya mahu menjadi benar dengan kebarangkalian 7/10000. Untuk mencapai matlamat ini, saya mula-mula mendapat integer rawak n kurang daripada 10000 daripada fungsi getRandomIntUnderN. Kemudian, saya tentukan sama ada n kurang daripada (7+1), dan jika ya, kembalikan benar, jika tidak pulangkan palsu. Berikut ialah pelaksanaan saya: //0isincludedwhilenisnotconstgetRand

P粉616383625 · Answer

Ini bukan cara anda melakukannya. Kod anda menyemak jika n kurang daripada 7, yang merupakan cara yang betul.

Dari mana kenyataan ini datang? Anda pasti boleh menguji premis ini...dan lihat sejauh mana kemungkinannya.

Memang benar.

Cara menguji

Anda boleh menguji pengedaran pelaksanaan anda dengan mudah. Anda boleh memanggil fungsi ini berulang kali dan merekodkan hasil yang anda perolehi dan melihat bagaimana ia berubah dari semasa ke semasa. Dalam statistik, lebih besar saiz sampel, lebih dipercayai hasilnya.

Ini ialah coretan kod yang secara berterusan melaksanakan nisbah goAtChance函数并记录调用的总次数和true结果的数量。每隔10毫秒，结果会在页面上更新，包括truenombor kepada jumlah. Jika semuanya berjalan lancar, nisbah ini akan menghampiri 0.0007 dari semasa ke semasa.

const getRandomIntUnderN = (n) => Math.floor(Math.random() * n);
const goAtChance = (n, m) => getRandomIntUnderN(m) < n; 

let [outTotal, outHits, outRatio] = document.querySelectorAll("span");

let hits = 0; // Number of results that are true
let total = 0; // Total number of results

requestAnimationFrame(function loop() {
   let deadline = performance.now() + 10;
   do {
     hits += goAtChance(7, 10000); // boolean coerces to 0 or 1
     total++;
   } while (performance.now() < deadline);
   // Show the accumulated results
   outTotal.textContent = total;
   outHits.textContent = hits;
   outRatio.textContent = (hits / total).toFixed(8);
   requestAnimationFrame(loop); // Allow screen to update and then continue
});

样本数：

命中数：

比例：