ความน่าจะเป็นของการได้หัวอย่างน้อย K ครั้งในการทอยเหรียญ N ครั้งใน C++

โจทย์

ความน่าจะเป็นคือโอกาสในการได้ผลลัพธ์ที่ต้องการจากชุดข้อมูลที่มีอยู่ ช่วงของความน่าจะเป็นอยู่ระหว่าง 0 ถึง 1 โดยจำนวนเต็ม 0 แสดงความเป็นไปไม่ได้ และ 1 แสดงความแน่นอน

ความน่าจะเป็นคืออะไร?

ความน่าจะเป็นในคณิตศาสตร์ให้เครื่องมือที่บอกความไม่แน่นอนของเหตุการณ์และเหตุผล กล่าวอีกนัยหนึ่ง ความน่าจะเป็นเกี่ยวกับการคำนวณความเป็นไปได้ของเหตุการณ์ที่กำหนด ซึ่งสามารถแสดงเป็นตัวเลขระหว่าง 1 ถึง 0 ตัวอย่างเช่น: ความน่าจะเป็นของการได้หัวเมื่อทอยเหรียญที่ไม่ล่วงลับ หรือได้ 3 เมื่อทอยลูกเต๋า

ตอนนี้ กลับมาที่โจทย์ เราต้องหาความน่าจะเป็นของการได้หัวอย่างน้อย k ครั้งในการทอยเหรียญ N ครั้ง

เช่น เรามีเหรียญ 3 เหรียญ และ k เป็น 2 ดังนั้นมี 2^3 = 8 วิธีในการทอยเหรียญ คือ -

HHH, HTH, HHT, HTT, THH, THT, TTT, TTH

ชุดที่มีหัวอย่างน้อย 2 ครั้งคือ -

HHH, HTH, HHT, THH

ดังนั้นความน่าจะเป็นจะเป็น 4/8 หรือ 0.5

ตัวอย่าง

Input: k = 1, n = 3 Output: 0.875
Input: k = 3, n = 6 Output: 0.65625

แนวทางแก้ปัญหา

• รับ n และ k เป็นอินพุต
• เก็บค่าแฟกทอเรียลในอาเรย์ และเรียกใช้เมื่อจำเป็น
• คำนวณ
• คืนค่าผลลัพธ์

อัลกอริทึม

ขั้นตอน 1 → ประกาศฟังก์ชันคำนวณความน่าจะเป็นของการได้หัวอย่างน้อย k ใน n ครั้ง
  double probability(int k, int n)
  ประกาศและตั้งค่า double check = 0
  วนลูป For i = k ถึง n และ ++i
    ตั้งค่า check += temp[n] / (temp[i] * temp[n - i])
  จบวน
  เรียก check = check / (1LL << n)
  คืนค่า check
ขั้นตอน 2 → ประกาศฟังก์ชันคำนวณค่าล่วงหน้า
  void precompute()
  ตั้งค่า temp[0] = temp[1] = 1
  วนลูป For i = 2 ถึง 19 และ ++i
    ตั้งค่า temp[i] = temp[i - 1] * i
ขั้นตอน 3 → ใน main
  เรียก precompute()
  เรียก probability(1, 3)
หยุด

ตัวอย่างโค้ด C++

#include<bits/stdc++.h>
using namespace std;
#define size 21
double temp[size];
// คำนวณความน่าจะเป็นของการได้หัวอย่างน้อย k ใน n ครั้ง
double probability(int k, int n) {
  double check = 0;
  for (int i = k; i <= n; ++i)
    check += temp[n] / (temp[i] * temp[n - i]);
  check = check / (1LL << n);
  return check;
}
void precompute() {
  temp[0] = temp[1] = 1;
  for (int i = 2; i < 20; ++i)
    temp[i] = temp[i - 1] * i;
}
int main() {
  precompute();
  // ความน่าจะเป็นของการได้ 1 หัวจาก 3 เหรียญ
  cout<<"probability is : "<<probability(1, 3) << "\n";
  // ความน่าจะเป็นของการได้ 3 หัวจาก 6 เหรียญ
  cout<<"probability is : "<<probability(3, 6) << "\n";
  return 0;
}

ผลลัพธ์

probability is : 0.875
probability is : 0.65625