Cómo determinar eficazmente la fórmula de recursividad (la eficiencia no puede ser demasiado baja)
Los problemas manejados por programas recursivos se pueden dividir en dos categorías: La primera categoría son funciones recursivas en matemáticas, que deben calcularse.
Valores de funciones, como la función factorial y la función de Fibonacci; el segundo tipo de problema tiene características recursivas y su propósito puede ser encontrar
dada una secuencia de operaciones que satisfaga ciertas condiciones, Por ejemplo, la Torre de Hanoi y el problema de las Ocho Reinas. La programación para el primer tipo de problema es simple y mecánica, pero no para el segundo tipo de problema. Debido a que involucra una amplia gama de áreas y no hay reglas unificadas a seguir, el proceso de programación suele ser complicado.
Es más complicado y el programa no es fácil de entender. La razón es que existen fórmulas de funciones listas para usar para el primer tipo de problemas
pero no para el segundo tipo. Si también pudiéramos escribirlo como un segundo tipo de pregunta.
Volviendo a la fórmula, el proceso de codificación se simplificará enormemente y también se mejorará la legibilidad del programa. Este artículo analiza este enfoque utilizando dos ejemplos de un programa.
2 Método de formulación
La programación se puede dividir en dos etapas: etapa lógica y etapa de implementación. No es necesario determinar el algoritmo en la etapa lógica.
Considere el lenguaje de programación y el entorno de implementación. Por lo general, los algoritmos se pueden representar mediante lenguaje natural, diagramas de flujo, diagramas NS y otras herramientas.
Para el segundo tipo de problema, la fórmula recursiva se puede obtener en la etapa lógica, por lo que existen al menos varias ventajas:
1. etapa de implementación, lo que simplifica enormemente la programación.
2. Usar métodos matemáticos para derivar fórmulas recursivas es mucho más simple que usar otros métodos para diseñar algoritmos.
3. Debido a que las fórmulas son la descripción más precisa y concisa de los algoritmos, con fórmulas recursivas, el trabajo de codificación se vuelve anormal.
Simple, la legibilidad del programa será mejor.
El llamado método de formulación de planificación recursiva primero debe expresar el problema en una función recursiva en el sentido matemático, y luego
La clave es determinar el significado del valor de la función. , aunque el problema en sí no requiere necesariamente calcular ningún valor de función. La elección del valor de la función puede
La energía no es única, pero cuanto más pueda mostrar la esencia del problema, mejor.
El problema de la Torre de Hanoi requiere acción para mover varios tableros de una columna a otra. Podemos
usar el número de acciones como valor de la función. Luego se obtiene la función recursiva h(d, f, t, u) de cuatro variables independientes y su significado.
El disco D se mueve de la columna F (desde) a la columna T (hacia), y la columna U (usando) se utiliza como búfer. Fácil de conseguir
Vaya a la siguiente fórmula recursiva:
h(1, f, t, u)=1
H (d, f, t , u) = h (d-1, f, u, t) h (1, f, t, u) h (d-1, u, t, f), si d > 1
it El significado práctico es muy obvio: mover una placa requiere solo una acción; y mover la placa d en la columna F de la columna F a la columna T requiere mover la placa superior d-1 del pilar U. luego mueva la placa inferior del pilar F al pilar T. Finalmente,
Mueva la placa d-1 que ya está en el pilar U al pilar T para que el número total de acciones sea igual a la suma de los tres conjuntos de acciones.
Con fórmulas recursivas, la programación se vuelve extremadamente sencilla. La estructura del programa es una estructura de múltiples ramas, al igual que la recursividad.
Las fórmulas se corresponden una a una, y la programación se convierte casi en traducción mecánica. En el siguiente programa, la única diferencia entre la función recursiva y la fórmula recursiva es que cuando D es 1, no solo el número de acción V se establece en 1, sino que también se muestra la acción.
main()
{ int d, v, h (int, int, int, int
printf (" discos = "); ("d ", ampd);
v=h(d, 1, 2, 3
printf("\nd d operaciones para discos!\n " , v); , d);
}
int h(int d, int f, int t, int u)
{ int i, v;
if(d = = 1){ v = 1; printf(" d- gt; d", f, t }
else v=h(d-1, f, u, t) h(1, f, t, u) h(d-1, u, t, f
Regresión v
}
<); p>La sesión en ejecución de este programa es la siguiente:Disco = 3
1->;2 1->;32->;3 1->;23-> ; 13->2 1->2
¡7 movimientos para 3 discos!
3 Ejemplos: Problema de las Ocho Reinas
El Problema de las Ocho Reinas [2] es un ejemplo recursivo más representativo y complejo, que requiere colocarlo en un tablero de ajedrez de 8×8.
Coloca ocho reinas para que no se ataquen entre sí. El algoritmo que utilizamos sigue siendo colocar una reina en cada fila comenzando desde la primera fila del tablero de ajedrez. Para cada fila, comience desde la primera columna de la fila para determinar si es mutuamente excluyente con las reinas anteriores.
Ataque, si es así, cambie a la siguiente columna, de lo contrario continúe colocando la siguiente reina hasta colocar 8 reinas. Basándonos en esta idea,
Definimos una función con nueve variables independientes:
q(k, a1, a2, a3, a4, a5, a6, a7, a8)
p>
donde k representa el número de reinas colocadas y ai (aquí I
Estas nueve variables independientes pueden representar el estado en cualquier momento durante el proceso de solución, y el valor de la función se define como inicial a partir de este estado
Según esta idea, no es difícil obtener la siguiente fórmula de recursividad:
Q(k, a1,..., ak, 0, ... si hay 0, entonces 0) = 0
Q(k, a1, ..., a8) = 1 si para cualquier 0
q(k, a1, .. ., ak, 0, ... 0) = q (k 1, a1, ..., ak, 1, ... 0) ... q (k 1, a1, ..., ak, 8, ...,0)
Si k
"ai y a k son compatibles" en la fórmula significa que no se atacan entre sí, lo cual es una expresión lógica:
(ai-AK) amp; amp(I ai-k-AK) amp(i-ai-k ak)
Verdadero, es decir, ai≠ak y i ai≠ k aki y yo -ai≠k-ak.
La fórmula recursiva anterior se puede convertir fácilmente a la siguiente forma
Siguiente paso:
main()
{ int a[9], v, q( int, int *);
v=q(0, a);
printf("\n¡Hay d soluciones!\n", v);
}
int q(int k, int *a)
{ int i, u, v
for(i=1, u =; 1;iltk amp ampu;i)
u = u amp amp(a[I]-a[k]) amp(I a[I]-k-a[k]) amp(; I-a[I]-k a[k]);
si(u = = 0)v = 0;
si no(k==8)
{ v = 1; printf(" d d d d d d d d ",
a[1], a[2], a[3], a[4], a[5], a[6 ], a [7], a[8]);
}
Otros
for(i=1, v = 0; ilt=8 ;i ){ a[k 1]= I; v =q(k 1, a);}
Regresión v;
}
Fórmula recursiva Las variables independientes a1 ,...,a8 en son una secuencia relacionada, por lo que deben representarse mediante la matriz A en el programa. En q()
Primero calcule si ak es compatible con todos los ai anteriores, si la variable u no es cero. q() corresponde estrictamente a la fórmula recursiva y se expresa como
con tres estructuras de rama seleccionadas. Cuando u no es cero y k es 8, establezca el valor de la función V en 1 y muestre el resultado.
Solución. Obviamente, este programa es el más fácil de escribir y el más fácil de entender. La parte interactiva de este programa es la siguiente
Ahorra espacio. Sólo se enumeran 4 de 92 soluciones:
15863724 16837425 ...83162574 84136275
¡Hay 92 soluciones!
4 Conclusión
El método formulaico es una idea de diseño simple y eficaz que se centra en las dificultades del diseño y la comprensión del programa.
Fórmula recursiva. Como puede verse en el ejemplo anterior, esta idea puede simplificar el diseño del programa y el programa resultante es obviamente mejor que el programa habitual. Esta idea es general, al menos aplicable al diseño de la mayoría de programas recursivos. Los programas diseñados con fórmulas recursivas tienen una estructura de ramificación estándar y son mucho más sencillos de escribir y comprender.
Los dos ejemplos anteriores pueden obtener fácilmente la secuencia requerida mientras se obtiene el valor de la función, pero este no es siempre el caso en el
caso general. El autor ha proporcionado un método de secuencia adjunta, que se puede utilizar para obtener las secuencias necesarias para ciertos problemas (como mostrar todas las combinaciones de n números a partir de m números).