Le contenu principal de cet article est la mise en œuvre récursive et non réécursive de la distribution binomiale de programmation Java, comme suit.
Source du problème:
Exercice 27 de la section 1.1, 4e édition de l'algorithme, section 1.1: retour (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p);
Calculez le nombre d'appels récursifs. Comment la formule récursive est-elle venue d'ici?
Distribution binomiale:
Définition: La distribution de probabilité discrète de N indépendant oui / non-expériences des temps de réussite K, la probabilité de succès dans chaque expérience est P, qui est désignée comme B (N, P, K).
Formule de probabilité: P (ξ = k) = c (n, k) * p ^ k * (1-p) ^ (nk)
Où C (n, k) = (nk)! / (K! * (Nk)!), Est désigné comme ξ ~ b (n, p), attente: eξ = np, variance: dξ = npq, où q = 1-p.
Il existe une formule récursive dans les statistiques de probabilité:
C'est la source de la forme récursive dans la question.
La formule récursive vient de: c (n, k) = c (n-1, k) + c (n-1, k-1). Le scénario réel est de choisir K parmi n individus. Combien de combinaisons y a-t-il? Organiser n personnes dans l'ordre de 1 à n. Si le Kth n'est pas sélectionné, vous devez sélectionner K parmi les personnes N-1 restantes; Si le Kth est sélectionné, vous devez sélectionner K-1 parmi les personnes N-1 restantes.
Mise en œuvre récursive de la distribution binomiale dans le livre:
Double binomial statique public (int n, int k, double p) {count ++; // Enregistrez le nombre d'appels récursifs 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); }Résultats expérimentaux:
NKP Nombre d'appels 10 5 0,25 246720 10 0,25 243553830 15 0,25 2440764535
D'après les résultats, nous pouvons voir que le nombre de fois que cette méthode récursive doit être appelée est une catastrophe géométrique, et même si n à 50 n'est pas considéré.
Amélioration de la distribution binomiale Implémentation récursive:
Count long statique privé = 0; double statique privé [] [] m; double binomial statique privé (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) {// Enregistrer le résultat du calcul et utiliser les calculés directement, sans calcul récursif m [n] [k] = (1,0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); } return m [n] [k]; } public statique double binomial (int n, int k, double p) {m = nouveau double [n + 1] [k + 1]; for (int i = 0; i <= n; i ++) {for (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} return binomial (n, k, p); }Résultats expérimentaux:
NKP Nombre d'appels 10 5 0,25 10120 10 0,25 45230 15 0,25 120350 25 0,25 3204100 50 0,25 5205
D'après les résultats expérimentaux, nous pouvons voir que le nombre d'appels est considérablement réduit et que l'algorithme peut être utilisé.
Mise en œuvre non réécursive de la distribution binomiale:
En fait, au lieu d'utiliser la récursivité, le calcul directement des nombres combinés et des factoriels est plus rapide.
// Calculez le nombre de combinaisons combinaison double statique publique (double n, double k) {double min = k; double max = nk; double t = 0; double nn = 1; double kk = 1; if (min> max) {t = min; min = max; max = t; } tandis que (n> max) {// La partie factorielle de la plus grande partie du dénominateur n'a pas besoin d'être calculée nn = nn * n; N--; } while (min> 0) {// Calculez le factoriel de la partie plus petite kk = kk * min; min--; } return nn / kk; } // Calculez la valeur de distribution binomiale publique double binomial (int n, int k, double p) {double a = 1; double b = 1; Double C = combinaison (n, k); while ((nk)> 0) {// Calculez la puissance (nk) de (1-p) a = a * (1-p); N--; } while (k> 0) {// Calculez la puissance k de p b = b * p; K--; } return c * a * b; }Résultats expérimentaux:
Valeur de distribution binomiale NKP 10, 5, 0,25 0,05839920043945312520, 10, 0,25 0,00992227527967770650, 25, 0,25 8,44919466990397E-5
En comparant avec l'algorithme précédent, les résultats du calcul sont corrects et la vitesse d'exécution est très rapide.
Résumer
Ce qui précède est l'intégralité du contenu de cet article sur les exemples de code d'implémentation récursif et non réécursif de la distribution binomiale de programmation Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!