O conteúdo principal deste artigo é a implementação recursiva e não recursiva da distribuição binomial de programação Java, como segue.
Fonte do problema:
Exercício 27 da seção 1.1, 4ª edição do algoritmo, Seção 1.1: Retorno (1.0 - P) * Binomial (N - 1, K, P) + P * Binomial (N - 1, K - 1, P);
Calcule o número de chamadas recursivas. Como a fórmula recursiva veio daqui?
Distribuição binomial:
Definição: A distribuição de probabilidade discreta de N independente sim/não experiências dos tempos de sucesso K, a probabilidade de sucesso em cada experimento é p, que é denotada como B (N, P, K).
Fórmula de probabilidade: p (ξ = k) = c (n, k) * p^k * (1-p)^(nk)
Onde c (n, k) = (nk)!/(K! * (Nk)!), É indicado como ξ ~ b (n, p), expectativa: eξ = np, variação: dξ = npq, onde q = 1-p.
Há uma fórmula recursiva nas estatísticas de probabilidade:
Esta é a fonte da forma recursiva na questão.
A fórmula recursiva vem de: c (n, k) = c (n-1, k)+c (n-1, k-1). O cenário real é escolher K de n indivíduos. Quantas combinações existem? Organize n pessoas em ordem de 1 a n. Se o Kth One não for selecionado, você precisará selecionar K entre as pessoas N-1 restantes; Se o Kth One for selecionado, você precisará selecionar o K-1 entre as pessoas N-1 restantes.
Implementação recursiva da distribuição binomial no livro:
binomial duplo estático público (int n, int k, duplo p) {count ++; // Registre o número de chamadas recursivas se (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } retornar (1.0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); }Resultados experimentais:
NKP Número de chamadas 10 5 0,25 246720 10 0,25 243553830 15 0,25 2440764535
A partir dos resultados, podemos ver que o número de vezes que esse método recursivo precisa ser chamado é um desastre geométrico e mesmo que N a 50 não seja considerado.
Distribuição binomial aprimorada Implementação recursiva:
contagem longa estática privada = 0; dupla estática privada [] [] m; Binômio duplo estático privado (int n, int k, duplo p) {count ++; if (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } if (m [n] [k] == -1) {// salve o resultado do cálculo e use -o diretamente se você o calculou, não é necessário calcular recursivamente m [n] [k] = (1,0 - p) * binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); } retornar m [n] [k]; } binomial duplo estático público (int n, int k, duplo p) {m = novo duplo [n + 1] [k + 1]; for (int i = 0; i <= n; i ++) {for (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} retornar binomial (n, k, p); }Resultados experimentais:
NKP Número de chamadas 10 5 0,25 10120 10 0,25 45230 15 0,25 120350 25 0,25 3204100 50 0,25 5205
A partir dos resultados experimentais, podemos ver que o número de chamadas é bastante reduzido e o algoritmo pode ser usado.
Implementação não recursiva da distribuição binomial:
De fato, em vez de usar a recursão, calcular diretamente os números e fatoriais combinados é mais rápido.
// Calcule o número de combinações com combinação dupla estática pública (N, n, duplo k) {duplo min = k; duplo max = nk; duplo t = 0; duplo nn = 1; duplo kk = 1; if (min> max) {t = min; min = max; max = t; } while (n> max) {// O fatorial da parte maior do denominador não precisa ser calculado nn = nn*n; N--; } while (min> 0) {// Calcule o fatorial da parte menor kk = kk*min; min--; } retornar nn/kk; } // Calcule o valor da distribuição binomial public estático duplo estático binomial (int n, int k, duplo p) {duplo a = 1; duplo b = 1; duplo c = combinação (n, k); while ((nk)> 0) {// calcule a potência (nk) de (1-p) a = a*(1-p); N--; } while (k> 0) {// calcule a potência k de p b = b*p; k--; } retornar c*a*b; }Resultados experimentais:
NKP Binomial Distribution Value 10, 5, 0,25 0,05839920043945312520, 10, 0,25 0,00992227527967770650, 25, 0,25 8.44919469990397e -5
Comparando com o algoritmo anterior, os resultados do cálculo estão corretos e a velocidade de execução é muito rápida.
Resumir
O exposto acima é o conteúdo inteiro deste artigo sobre exemplos de código de implementação recursiva e não recursiva da distribuição binomial de programação Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!