El coeficiente binomial [matemáticas] {N \ elegir k} [/ matemáticas] se puede definir de forma recursiva como [matemáticas] {N \ elegir 0} = 1 [/ matemáticas], [matemáticas] {N \ elegir N} = 1 [/ matemáticas] y para 0 <k <N, [matemáticas] {N \ elegir k} = {N-1 \ elegir k} + {N-1 \ elegir k-1} [/ matemática]. ¿Cómo escribo un método Java eficiente para calcular el coeficiente binomial sin usar recursividad?

Answer 1

Aquí está la técnica:

BigInteger ncr (BigInteger n, BigInteger r)
{
Numerador BigInteger = 1, denominador = 1;
BigInteger j = 1;
para (int i = n-r + 1; i <= n; i ++, j ++)
{
numerador * = i;
denominador * = j;
}
numerador de retorno Divide (denominador);
}

(No soy un codificador de JAVA, pero he hecho todo lo posible para convertir mi código de Python en JAVA. Solo mire el algoritmo en lugar del estilo de código / codificación).

Aquí está el código de Python para referencia:

def ncr (n, r):
nume, deno, j = 1,1,1
para i en xrange (n-r + 1, n + 1):
nume = Karatsubamul (nume, i)
deno = Karatsubamul (deno, j)
j + = 1
retorno (nume / deno)

Y aquí vamos por la prueba:
C (n, r) = n! / (R! (Nr)!)

= 1.2.3… n / ((1.2.3… r) (1.2.3… (nr))

= (n-r + 1) (n-r + 2) … n / (1.2.3 … r) (Eliminar todo (nr)! del numerador y denominador)

Answer 2

Una solución de dos punteros debería funcionar en [math] \ mathcal {O} (N + k) [/ math] (que es más rápida que la fórmula recursiva, pero lenta si quieres muchas). La idea es simple, tomamos dos índices [matemática] i_1 [/ matemática] y [matemática] i_2 [/ matemática]

[matemáticas] (N-k + 1) \ leq i_1 \ leq N \ quad 1 \ leq i_2 \ leq k [/ matemáticas]

Inicialice su variable de resultado [math] s [/ math] en 1. Luego el pseudocódigo se ve así:

i_2 = 1
s = 1
Para i_1 = N-k + 1 a i_1 = N do {
s = s * i_1
while (s% i_2 == 0 e i_2 <= k) {
s = s / i_2
i_2 = i_2 + 1
}
}
devoluciones

Esta implementación evita el desbordamiento de la variable en la mayoría de los casos (si el resultado no es demasiado grande) y no sufre la limitación de calcular los factoriales de forma independiente. Si necesita números combinatorios [matemáticos] M [/ matemáticos], la complejidad se escala como [matemática] \ matemática {O} (MN) [/ matemática], y la fórmula recursiva que recuerda los resultados anteriores (programación dinámica) es más eficiente ([matemática ] \ mathcal {O} (N ^ 2) [/ math]).