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

Question

<p>Saya mahu melaksanakan kaedah yang mengembalikan <kod>benar</kod> dengan kebarangkalian <kod>n/m</kod> </p> <p>Sebagai contoh, saya ingin mendapatkan <code>true</code> dengan kebarangkalian 7/10000. </p> <p>Untuk mencapai ini, saya mula-mula mendapatkan integer rawak

P粉026665919531 hari yang lalu643

Answer 1

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
});

样本数：<span></span><br>
命中数：<span></span><br>
比例：<span></span>