El contenido principal de este documento es la implementación recursiva y no recursiva de la distribución binomial de programación Java, como sigue.
Fuente del problema:
Ejercicio 27 de la Sección 1.1, 4ª edición del algoritmo, Sección 1.1: retorno (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p);
Calcule el número de llamadas recursivas. ¿Cómo vino la fórmula recursiva de aquí?
Distribución binomial:
Definición: La distribución de probabilidad discreta de n SÍ independiente/no experimentos de los tiempos de éxito K, la probabilidad de éxito en cada experimento es P, que se denota como B (N, P, K).
Fórmula de probabilidad: P (ξ = k) = c (n, k) * p^k * (1-p)^(nk)
Donde c (n, k) = (nk)!/(K! * (Nk)!), Se denota como ξ ~ b (n, p), expectativa: eξ = np, varianza: dξ = npq, donde q = 1-p.
Hay una fórmula recursiva en las estadísticas de probabilidad:
Esta es la fuente de la forma recursiva en la pregunta.
La fórmula recursiva proviene de: C (N, K) = C (N-1, K)+C (N-1, K-1). El escenario real es elegir k de n individuos. ¿Cuántas combinaciones hay? Organizar a las personas en orden de 1 a n. Si el KTH no está seleccionado, debe seleccionar K de las personas N-1 restantes; Si el KTH se selecciona, debe seleccionar K-1 de las personas N-1 restantes.
Implementación recursiva de la distribución binomial en el libro:
Public static doble binomial (int n, int k, doble p) {count ++; // Registre el número de llamadas recursivas si (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); }Resultados experimentales:
NKP Número de llamadas 10 5 0.25 246720 10 0.25 243553830 15 0.25 2440764535
A partir de los resultados, podemos ver que el número de veces que se debe llamar a este método recursivo es un desastre geométrico, e incluso si no se considera N a 50.
Implementación recursiva de distribución binomial mejorada:
Conteo largo estático privado = 0; Doble estático privado [] [] m; binomial doble estático privado (int n, int k, doble p) {count ++; if (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } if (m [n] [k] == -1) {// Guarde el resultado del cálculo y use los calculados directamente, sin cálculo recursivo m [n] [k] = (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); } return m [n] [k]; } public static static doble binomial (int n, int k, doble p) {m = new double [n + 1] [k + 1]; for (int i = 0; i <= n; i ++) {for (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} binomial de retorno (n, k, p); }Resultados experimentales:
NKP Número de llamadas 10 5 0.25 10120 10 0.25 45230 15 0.25 120350 25 0.25 3204100 50 0.25 5205
A partir de los resultados experimentales, podemos ver que el número de llamadas se reduce considerablemente y se puede usar el algoritmo.
Implementación no recursiva de la distribución binomial:
De hecho, en lugar de usar la recursión, calcular directamente los números combinados y los factorales es más rápido.
// Calcule el número de combinaciones de combinación de doble estática pública (doble n, doble k) {doble min = k; doble max = nk; doble t = 0; doble nn = 1; doble kk = 1; if (min> max) {t = min; min = max; max = t; } while (n> max) {// El factorial de la parte más grande en el denominador no necesita calcularse nn = nn*n; NORTE--; } while (min> 0) {// Calcule el factorial de la parte más pequeña kk = kk*min; min--; } return nn/kk; } // Calcule el valor de distribución binomial binomial doble estático (int n, int k, doble p) {doble a = 1; doble b = 1; doble c = combinación (n, k); while ((nk)> 0) {// calcule la potencia (nk) de (1-p) a = a*(1-p); NORTE--; } while (k> 0) {// Calcule la potencia k de p b = b*p; K--; } return c*a*b; }Resultados experimentales:
Valor de distribución binomial de NKP 10, 5, 0.25 0.05839920043945312520, 10, 0.25 0.00992227527967770650, 25, 0.25 8.44919466990397e-5
En comparación con el algoritmo anterior, los resultados del cálculo son correctos y la velocidad de ejecución es muy rápida.
Resumir
Lo anterior es todo el contenido de este artículo sobre los ejemplos de código de implementación recursivo y no recursivo de la distribución binomial de programación Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!