Encuentra la fórmula de esta ecuación de recurrencia binaria? f (m, n) = f (m-1, n) + f (m, n-1)

¡LO SENTIMOS! ¡MI ERROR! Gracias por su recordatorio, descubrí f (0, k) == f (k, 0) == 1. Esta pregunta es acerca de cómo contar el número de caminos más cortos de la cuadrícula (0,0) a (m, n)Encuentra la fórmula de esta ecuación de recurrencia binaria? f (m, n) = f (m-1, n) + f (m, n-1)

Tengo que resolver la siguiente ecuación ahora, descubrir exactamente qué es f (m, n) igual a.

1) f(m,n) = 0 : when (m,n) = (0,0) 
**2) f(m,n) = 1 : when f(0,k) or f(k,0)** 
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else

por ejemplo:

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3

recuerdo que es una forma estándar para resolver ese tipo de ecuación de recurrencia binario como aprendí en mi clase de algoritmo hace varios años, pero simplemente no puedo recordar por ahora .

¿Alguien podría dar alguna pista? O una palabra clave cómo encontrar la respuesta?

Fuente

2012-01-26 JXITC

¿Quiere decir que usted necesita para encontrar la fórmula que no utiliza la recursividad? ¿O solo un algoritmo que calcula la recurrencia de manera eficiente? – svick

¿Estás seguro de que f (2,1) = 3? Leo f (2,1) = f (1,1) + f (2,0) = (f (0,1) + f (1,0)) + f (2,0) = (1 + 1) + 2 = 2 + 2 = 4 –

Estás buscando la solución de forma cerrada ¿no? – ElKamina

Ugh, solo me estaba divirtiendo al revisar mis viejos libros de texto sobre funciones de generación, ¡y cambiaste la pregunta de nuevo!

Esta pregunta se trata de cómo contar la cantidad de ruta más corta desde la cuadrícula (0,0) a (m, n).

Esta es una pregunta básica de combinatoria: no requiere saber nada sobre la generación de funciones o incluso las relaciones recurrentes.

Para resolverlo, imagina las rutas que se escriben como una secuencia de U (para "arriba") y R (para "derecha"). Si nos movemos de (0,0) a, digamos, (5, 8), debe haber 5 R y 8 U's. Solo un ejemplo:

RRUURURUUURUU

Siempre habrá, en este ejemplo, 8 U's y 5 R's; diferentes caminos los tendrán en diferentes órdenes. Entonces, podemos elegir 8 posiciones para nuestras U, y el resto debe ser R's. Por lo tanto, la respuesta es

(8+5) choose (8)

o, en general,

(m+n) choose (m)

Fuente

2012-01-26 23:27:23

¡GUAU! Bonita explicación! ¡Te amo! – JXITC

Intente buscar "generar funciones" en la literatura. Un enfoque sería imaginar una función P (x, y) donde el coeficiente de x^m y^n es f (m, n). La línea de recurrencia (línea 3) te dice que P (x, y) - xP (x, y) - yP (x, y) = (1-xy) P (x, y) debería ser bastante simple, excepto por aquellos molestos valores de borde. Luego resuelve para P (x, y).

¿Estás seguro f(k,0) = f(0,k) = k, y no 1, tal vez? Si lo fuera, diría que la mejor opción sería escribir algunos valores, adivinar qué son y luego probarlo.

Fuente

2012-01-26 23:14:27

= =! Cometí un error otra vez. Sí, es 1 ... Dios mío, qué tonto fui. Estoy a punto de reescribir la pregunta. – JXITC

Y gracias por su respuesta, estoy buscando generar funciones ahora. :) – JXITC

Es una gran noticia ... el problema original era muy feo. La revisada es muy bonita. Escriba algunos valores en una tabla y gire la cabeza 45 grados. ;) –

Esto es simplemente el coeficiente binomial

f(m,n) = (m+n choose m) = (m+n choose n)

Puede probar esto observando que satisfacen la misma relación de recurrencia.

Para derivar la fórmula (si no podía simplemente adivinar y luego verificar), utilice las funciones de generación como Chris Nash sugiere correctamente.

Fuente

2012-01-26 23:25:50 PengOne

muchas gracias :) – JXITC

Encuentra la fórmula de esta ecuación de recurrencia binaria? f (m, n) = f (m-1, n) + f (m, n-1)

Respuesta

Cuestiones relacionadas