Kandungan utama dari makalah ini adalah implementasi rekursif dan non-rekursif dari distribusi binomial pemrograman Java, sebagai berikut.
Sumber masalahnya:
Latihan 27 dari Bagian 1.1, edisi ke -4 algoritma, Bagian 1.1: Return (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p);
Hitung jumlah panggilan rekursif. Bagaimana formula rekursif dari sini?
Distribusi binomial:
Definisi: Distribusi probabilitas diskrit N independen ya/non-eksperimen waktu keberhasilan k, probabilitas keberhasilan dalam setiap percobaan adalah p, yang dilambangkan sebagai b (n, p, k).
Formula probabilitas: p (ξ = k) = c (n, k) * p^k * (1-p)^(nk)
Di mana c (n, k) = (nk)!/(K! * (Nk)!), Dilambangkan sebagai ξ ~ b (n, p), ekspektasi: eξ = np, varian: dξ = npq, di mana q = 1-p.
Ada formula rekursif dalam statistik probabilitas:
Ini adalah sumber bentuk rekursif dalam pertanyaan.
Formula rekursif berasal dari: c (n, k) = c (n-1, k)+c (n-1, k-1). Skenario sebenarnya adalah memilih k dari n individu. Ada berapa kombinasi? Mengatur dan orang berurutan dari 1 hingga n. Jika KTH tidak dipilih, Anda harus memilih K dari N-1 yang tersisa; Jika KTH dipilih, Anda harus memilih K-1 dari N-1 yang tersisa.
Implementasi rekursif distribusi binomial dalam buku:
binomial ganda statis publik (int n, int k, double p) {count ++; // Catat jumlah panggilan rekursif jika (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); }Hasil Eksperimen:
NKP Jumlah Panggilan 10 5 0.25 246720 10 0.25 243553830 15 0.25 2440764535
Dari hasilnya, kita dapat melihat bahwa berapa kali metode rekursif ini perlu dipanggil adalah bencana geometris, dan bahkan jika n hingga 50 tidak dipertimbangkan.
Implementasi rekursif distribusi binomial yang ditingkatkan:
Jumlah panjang statis pribadi = 0; private static double [] [] m; private static double binomial (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) {// Simpan hasil perhitungan dan gunakan yang dihitung secara langsung, tanpa perhitungan rekursif m [n] [k] = (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); } return m [n] [k]; } public static double binomial (int n, int k, double p) {m = double baru [n + 1] [k + 1]; untuk (int i = 0; i <= n; i ++) {for (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} return binomial (n, k, p); }Hasil Eksperimen:
NKP Jumlah panggilan 10 5 0,25 10120 10 0,25 45230 15 0,25 120350 25 0,25 3204100 50 0,25 5205
Dari hasil eksperimen, kita dapat melihat bahwa jumlah panggilan sangat berkurang dan algoritma dapat digunakan.
Implementasi Distribusi Binomial yang Tidak Maha Rekursif:
Faktanya, alih -alih menggunakan rekursi, secara langsung menghitung angka gabungan dan faktorial lebih cepat.
// Hitung jumlah kombinasi kombinasi ganda statis publik (ganda N, kouble k) {double min = k; double max = nk; t ganda t = 0; Double nn = 1; KK ganda = 1; if (min> max) {t = min; min = maks; max = t; } while (n> max) {// faktorial bagian yang lebih besar dalam penyebut tidak perlu dihitung nn = nn*n; N--; } while (min> 0) {// Hitung faktorial bagian yang lebih kecil kk = kk*min; min--; } return nn/kk; } // Hitung nilai distribusi binomial binomial ganda statis publik (int n, int k, double p) {ganda A = 1; Double B = 1; ganda C = kombinasi (n, k); while ((nk)> 0) {// Hitung kekuatan (nk) dari (1-p) a = a*(1-p); N--; } while (k> 0) {// Hitung kekuatan k p b = b*p; K--; } return c*a*b; }Hasil Eksperimen:
NKP Nilai Distribusi Binomial 10, 5, 0,25 0,05839920043945312520, 10, 0,25 0,0092227527967770650, 25, 0,25 8.4491946690397E-5
Dibandingkan dengan algoritma sebelumnya, hasil perhitungannya benar dan kecepatan berjalan sangat cepat.
Meringkaskan
Di atas adalah seluruh konten artikel ini tentang contoh kode implementasi rekursif dan non-rekursif dari distribusi binomial pemrograman Java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!