Der Hauptinhalt dieses Papiers ist die rekursive und nicht rekursive Implementierung der Java-Programmierverteilung wie folgt.
Quelle des Problems:
Übung 27 von Abschnitt 1.1, 4. Ausgabe des Algorithmus, Abschnitt 1.1: Rückgabe (1.0 - p) * Binomial (n - 1, k, p) + p * Binomial (n - 1, k - 1, p);
Berechnen Sie die Anzahl der rekursiven Anrufe. Wie kam die rekursive Formel von hier?
Binomialverteilung:
Definition: Die diskrete Wahrscheinlichkeitsverteilung von n unabhängigen Ja/Nicht-Experimenten der Erfolgszeiten k ist die Erfolgswahrscheinlichkeit in jedem Experiment P, das als B (n, p, k) bezeichnet wird.
Wahrscheinlichkeitsformel: p (ξ = k) = c (n, k) * p^k * (1-p)^(nk)
Wobei c (n, k) = (nk)!/(K! * (Nk)!), Kenntnis als ξ ~ b (n, p), Erwartung: echte = np, Varianz: dξ = npq, wobei q = 1-p.
In der Wahrscheinlichkeitsstatistik gibt es eine rekursive Formel:
Dies ist die Quelle der rekursiven Form in der Frage.
Die rekursive Formel stammt aus: C (n, k) = c (n-1, k)+c (n-1, k-1). Das tatsächliche Szenario besteht darin, K aus N -Individuen zu wählen. Wie viele Kombinationen gibt es? Arrangieren Sie N -Personen in Ordnung von 1 bis n. Wenn der KTH nicht ausgewählt ist, müssen Sie K aus den verbleibenden N-1-Personen auswählen. Wenn der KTH ausgewählt ist, müssen Sie K-1 aus den verbleibenden N-1-Personen auswählen.
Rekursive Implementierung der Binomialverteilung im Buch:
public static double binomial (int n, int k, double p) {count ++; // Die Anzahl der rekursiven Anrufe aufzeichnen if (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); }Experimentelle Ergebnisse:
NKP -Anzahl der Anrufe 10 5 0,25 246720 10 0,25 243553830 15 0,25 2440764535
Aus den Ergebnissen können wir erkennen, dass die Häufigkeit, mit der diese rekursive Methode aufgerufen werden muss, eine geometrische Katastrophe ist und selbst wenn N bis 50 nicht berücksichtigt wird.
Verbesserte Binomialverteilung Rekursive Implementierung:
private statische Langzahl = 0; privates statisches Doppel [] [] m; private statische Doppel -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) {// das Berechnungsergebnis speichern und die berechneten direkt, ohne rekursive Berechnung m [n] [k] = (1,0 - p) * Binomial (n - 1, k, p) + p * Binomial (n - 1, k - 1, p) verwenden; } return m [n] [k]; } public static double binomial (int n, int k, double p) {m = neues double [n + 1] [k + 1]; für (int i = 0; i <= n; i ++) {für (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} return binomial (n, k, p); }Experimentelle Ergebnisse:
NKP -Anzahl der Anrufe 10 5 0,25 10120 10 0,25 45230 15 0,25 120350 25 0,25 3204100 50 0,25 5205
Aus den experimentellen Ergebnissen können wir feststellen, dass die Anzahl der Anrufe stark reduziert und der Algorithmus verwendet werden kann.
Nicht rekursive Implementierung der Binomialverteilung:
Anstatt Rekursion zu verwenden, ist die direkte Berechnung der kombinierten Zahlen und Faktorien schneller.
// Berechnen Sie die Anzahl der Kombinationen öffentliche statische Doppelkombination (Double N, Double K) {double min = k; doppelt max = nk; double t = 0; doppelt nn = 1; DoppelkK = 1; if (min> max) {t = min; min = max; max = t; } while (n> max) {// Das Fakultät des größeren Teils im Nenner muss nicht berechnet werden nn = nn*n; N--; } while (min> 0) {// Berechnen Sie das Faktor des kleineren Teils kk = kk*min; min--; } return nn/kk; } // Berechnen Sie den Binomialverteilungswert öffentlich statische doppelte Binomial (int n, int k, double p) {double a = 1; doppelte B = 1; Double C = Kombination (n, k); while ((nk)> 0) {// Berechnen Sie die (nk) Leistung von (1-p) a = a*(1-p); N--; } while (k> 0) {// Berechnen Sie die k -Leistung von p b = b*p; k--; } return c*a*b; }Experimentelle Ergebnisse:
NKP-Binomialverteilungswert 10, 5, 0,25 0,05839920043945312520, 10, 0,25 0,00992227527967770650, 25, 0,25 8.449194690397e-5e-5
Im Vergleich zum vorherigen Algorithmus sind die Berechnungsergebnisse korrekt und die Laufgeschwindigkeit ist sehr schnell.
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels über rekursive und nicht recursive Implementierungscode-Beispiele für Java-Programmierverteilung. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!