เนื้อหาหลักของบทความนี้คือการดำเนินการแบบเรียกซ้ำและไม่ซ้ำของการแจกแจงทวินามการเขียนโปรแกรม Java ดังต่อไปนี้
แหล่งที่มาของปัญหา:
แบบฝึกหัด 27 ของมาตรา 1.1, อัลกอริทึมรุ่นที่ 4, มาตรา 1.1: return (1.0 - P) * ทวินาม (N - 1, K, P) + P * binomial (N - 1, K - 1, P);
คำนวณจำนวนการโทรแบบเรียกซ้ำ สูตรการเรียกซ้ำมาจากที่นี่ได้อย่างไร?
การกระจายแบบทวินาม:
คำจำกัดความ: การกระจายความน่าจะเป็นแบบไม่ต่อเนื่องของ N อิสระใช่/ไม่ใช่การทดลองของเวลาความสำเร็จ K ความน่าจะเป็นของความสำเร็จในการทดลองแต่ละครั้งคือ P ซึ่งแสดงเป็น B (N, P, K)
สูตรความน่าจะเป็น: p (ξ = k) = c (n, k) * p^k * (1-p)^(nk)
โดยที่ c (n, k) = (nk)!/(k! * (nk)!) ถูกแสดงว่าเป็นξ ~ b (n, p), ความคาดหวัง: eξ = np, ความแปรปรวน: dξ = npq, โดยที่ q = 1-p
มีสูตรการเรียกซ้ำในสถิติความน่าจะเป็น:
นี่คือแหล่งที่มาของรูปแบบการเรียกซ้ำในคำถาม
สูตรการเรียกซ้ำมาจาก: C (N, K) = C (N-1, K)+C (N-1, K-1) สถานการณ์จริงคือการเลือก K จากบุคคล N มีกี่ชุด? จัดเรียง n คนตามลำดับจาก 1 ถึง n หากไม่ได้เลือก Kth หนึ่งคุณจะต้องเลือก K จากคน N-1 ที่เหลืออยู่ หากเลือก KTH หนึ่งคุณต้องเลือก K-1 จากคน N-1 ที่เหลือ
การใช้การกระจายแบบทวินามซ้ำในหนังสือ:
สาธารณะแบบสแตติกสองครั้ง (int n, int k, double p) {count ++; // บันทึกจำนวนการโทรแบบเรียกซ้ำถ้า (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } return (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); -ผลการทดลอง:
NKP จำนวนการโทร 10 5 0.25 246720 10 0.25 243553830 15 0.25 2440764535
จากผลลัพธ์เราจะเห็นว่าจำนวนครั้งที่วิธีการเรียกซ้ำนี้ต้องเรียกว่าเป็นหายนะทางเรขาคณิตและแม้ว่าจะไม่ได้รับการพิจารณา N ถึง 50
ปรับปรุงการกระจายแบบเรียกซ้ำแบบทวินาม:
นับยาวคงที่ส่วนตัว = 0; เอกชนคงที่สองเท่า [] [] M; ส่วนตัวแบบสแตติกสองครั้ง (int n, int k, double p) {count ++; if (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } if (m [n] [k] == -1) {// บันทึกผลการคำนวณและใช้สิ่งที่คำนวณได้โดยตรงโดยไม่ต้องคำนวณซ้ำ M [n] [k] = (1.0 - p) * ทวินาม (n - 1, k, p) + p * binomial (n - 1, k - 1, p); } return m [n] [k]; } public double binomial (int n, int k, double p) {m = ใหม่สองครั้ง [n + 1] [k + 1]; สำหรับ (int i = 0; i <= n; i ++) {สำหรับ (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} ส่งคืนทวินาม (n, k, p); -ผลการทดลอง:
NKP จำนวนการโทร 10 5 0.25 10120 10 0.25 45230 15 0.25 120350 25 0.25 3204100 50 0.25 5205
จากผลการทดลองเราจะเห็นว่าจำนวนการโทรลดลงอย่างมากและสามารถใช้อัลกอริทึมได้
การใช้งานแบบไม่ซ้ำของการกระจายแบบทวินาม:
ในความเป็นจริงแทนที่จะใช้การเรียกซ้ำการคำนวณตัวเลขรวมและแฟคทอเรียลโดยตรงจะเร็วขึ้น
// คำนวณจำนวนชุดค่าผสมแบบสแตติกแบบสแตติกสองครั้ง (double n, double k) {double min = k; double max = nk; double t = 0; double nn = 1; double kk = 1; if (min> max) {t = min; ขั้นต่ำ = สูงสุด; สูงสุด = t; } ในขณะที่ (n> max) {// แฟคทอเรียลของส่วนที่ใหญ่กว่าในตัวส่วนไม่จำเป็นต้องคำนวณ nn = nn*n; n--; } ในขณะที่ (ขั้นต่ำ> 0) {// คำนวณแฟกทอเรียลของส่วนเล็ก ๆ kk = kk*min; นาที--; } return nn/kk; } // คำนวณค่าการแจกแจงแบบทวินามแบบสแตติกสอง binomial (int n, int k, double p) {double a = 1; double b = 1; double c = การรวมกัน (n, k); ในขณะที่ ((nk)> 0) {// คำนวณกำลัง (nk) ของ (1-p) a = a*(1-p); n--; } ในขณะที่ (k> 0) {// คำนวณกำลัง k ของ p b = b*p; K--; } return c*a*b; -ผลการทดลอง:
NKP ค่าการกระจายตัวทวินาม 10, 5, 0.25 0.05839920043945312520, 10, 0.25 0.009922227527967770650, 25, 0.25 8.44919466990397E-5
เมื่อเปรียบเทียบกับอัลกอริทึมก่อนหน้าผลการคำนวณนั้นถูกต้องและความเร็วในการทำงานนั้นเร็วมาก
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับตัวอย่างรหัสการใช้งานแบบเรียกซ้ำและไม่ซ้ำซ้อนของการแจกแจงทวินามการเขียนโปรแกรม Java ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!