Explicación detallada del algoritmo de Pascal para retroceso y recursividad.
Cuando lidiamos con problemas de recursividad, a veces nos encontramos con situaciones en las que la relación de recursividad es obvia. Solo necesitamos escribir la relación de recursividad y podemos recurrir elemento por elemento, es decir, deducir el i-ésimo. elemento del i-ésimo elemento i 1 término, lo llamamos expresión recursiva que expresa la relación recursiva. Sin embargo, algunas relaciones recursivas sólo pueden verse mediante una observación cuidadosa e incluso con la ayuda de algunas técnicas. Las llamamos relaciones recursivas implícitas.
La clave de los algoritmos recursivos es analizar cuidadosamente el problema, encontrar la relación recursiva, escribir correctamente la fórmula recursiva, encontrar las condiciones de contorno y luego usar bucles para implementarla.
Resumen
1. La forma básica de un algoritmo recursivo es que el programador deja que la computadora recorra una serie de valores y el resultado de la Este último cálculo está determinado por el anterior o más derivados numéricamente. A veces, para encontrar un elemento en una secuencia, tenemos que comenzar desde el primer elemento y calcular el valor del elemento anterior uno por uno. Aunque esto no es eficiente, puede ayudarnos a resolver muchos problemas prácticos.
2. Ya sea recursividad directa o inversa, la clave radica en si la fórmula recursiva es correcta y si las condiciones de contorno son correctas. Ambos son indispensables. Entonces todos los resultados recursivos serán incorrectos.
Ejemplo 1: La secuencia 1, 2, 5, 10, 17, 26, 37... encuentra el enésimo término de la secuencia.
A través del análisis, podemos encontrar que el número al final de la secuencia tiene un patrón de crecimiento de 1, 3, 5, 7, 9 y 11 con base en el ítem anterior. expresión del patrón de crecimiento Fórmula 2*n-3, es decir, a(1)=1, a(n)=a(n-1) 2*n-3;
Hay otra. regla, podemos encontrar que cada elemento está en orden. Es el cuadrado de los números naturales a partir de 0 más el número natural 1 a partir de 0, es decir. Por ejemplo:
(n-1) 2 1, el primer término (1-1) 2 1, el segundo término (2-1) 2 1, el tercer término (3-1) 2 1 ....
Ejemplo 2: Problema de escalera: El significado de la pregunta es: Hay N escalones en la escalera. Puedes subir un escalón a la vez, o puedes subir. dos escalones a la vez. ¿Cuántos escalones puedes usar? Hay diferentes maneras de llegar desde la parte inferior de la escalera hasta la cima.
Esta es una relación recursiva implícita. Si el programador no puede resolverlo, es posible que no pueda resolver este problema. Analicémoslo: solo hay una forma de caminar en el primer nivel, pero hay dos formas de caminar en el segundo nivel (caminar un nivel dos veces o dos niveles a la vez), y solo hay una forma de caminar en el tercero. nivel, debe usarse junto con el método de caminar en el primer nivel y el método de caminar en el segundo nivel (porque desde el primer nivel y el segundo nivel, se puede llegar al tercer nivel a través de un paso, es decir. , aumentar Hay dos métodos de procesamiento para el tercer nivel, el primero es usarlo directamente como el primer nivel). El primero se usa directamente como un paso, luego es consistente con el método de dos niveles y el otro se combina con el segundo nivel como un paso, luego es consistente con el método de primer nivel y el total es el primero. La suma de los métodos del primer nivel y el método del segundo nivel, que se extiende hasta el nivel i-ésimo, es el método para llegar al nivel i-1 y el método para llegar al nivel i-2. Obviamente, esta es una secuencia de Fibonacci. En este punto, el lector debería poder escribir este programa de manera competente. En futuros ejercicios de programación, también podemos encontrarnos con los resultados de la deformación de la secuencia de Fibonacci: por ejemplo, f(i)=f(i-1) 2f(i-2), o f(i)=f( i- 1) f(i-2) f(i-3) etc.
Ejemplo 3: Problema del mono comiendo melocotón: Hay cinco monos viviendo en las montañas. Un día, el hijo mayor vio un montón de melocotones y quiso quedárselos, pero le preocupaba que el segundo y el tercer hijo supieran que era demasiado codicioso.
Entonces dividió los duraznos en dos partes iguales, pero descubrió que quedaba una parte, así que el jefe se comió esta parte y luego tomó otra mitad del durazno. Al día siguiente, el segundo niño también vio el montón de melocotones. Tuvo la misma idea que el hermano mayor. El tercer, cuarto y quinto hijo también tuvieron la misma idea que su hermano mayor. La quinta persona se comió uno y se llevó la mitad, dejando 11 melocotones en la pila. Planifica cuántas bolas habrá inicialmente en la pila de melocotones.
La siguiente pregunta es obvia Si invertimos el orden en que los hermanos comen melocotones, podemos saber el número total de melocotones al principio. La fórmula de recursividad es a[n-1]=a[n]*2 1. El valor inicial de la recursividad es a[5]=11 (también llamado condición de contorno), que se puede encontrar a partir del valor de a[0]. Creo que ahora puedes escribir fácilmente programas correctos. Esto es sólo para ilustrar que el algoritmo recursivo no sólo puede realizar un razonamiento directo sino también inverso.
El algoritmo de retroceso, también conocido como método de prueba y error, es un método para encontrar soluciones a problemas de forma sistemática. La idea básica del algoritmo de retroceso es: avance desde una carretera, si puede entrar, entre. Si no puede entrar, regrese a otra carretera e inténtelo de nuevo.
Los pasos generales para utilizar el algoritmo de retroceso para resolver problemas son:
1. Definir un espacio de solución que contenga la solución del problema.
2. Utilizar métodos adecuados de búsqueda para organizar el espacio de la solución.
3. Utilice el método de profundidad primero para buscar el espacio de solución.
IV. Utilizar funciones límite para evitar desplazarse a subespacios donde las soluciones son imposibles.
El espacio de solución de un problema generalmente se genera dinámicamente durante el proceso de búsqueda de una solución al problema, lo cual es una característica importante del algoritmo de retroceso.
El método de retroceso es un algoritmo de búsqueda sistemático y saltante. Utiliza una estrategia de profundidad para buscar en el árbol del espacio de soluciones que contiene todas las soluciones al problema comenzando desde el nodo raíz. Cuando el algoritmo busca cualquier nodo del árbol del espacio de soluciones, siempre determina primero si ese nodo definitivamente no contiene una solución al problema. Si definitivamente no se incluye, el algoritmo omitirá la búsqueda sistemática del subárbol enraizado en el nodo y retrocederá hasta sus nodos ancestros capa por capa. De lo contrario, ingrese al subárbol y continúe buscando con una estrategia de profundidad. Cuando se utiliza el método de retroceso para encontrar todas las soluciones a un problema, no finaliza hasta que se hayan buscado el nodo raíz y todos los subárboles del nodo raíz. Cuando se utiliza el método de búsqueda hacia atrás para encontrar cualquier solución al problema, se puede terminar encontrando una solución única al problema. Este algoritmo, que busca sistemáticamente una solución a un problema en profundidad, se llama retroceso y es adecuado para resolver problemas con un gran número de combinaciones.
[La recursión es material de aprendizaje, retroceder es la Enciclopedia Baidu]
Jiang Jing
El visitante respondió a las: 2010-8-29 15:05:18 p>
Jiang Jing
p>
Recursión
La recursividad es un concepto importante en informática. El método recursivo es un método eficaz para escribir programas. usando el método recursivo
Sé conciso y claro.
2.1 El concepto de recursividad
1. Concepto
Un proceso (o función) que se llama a sí mismo directa o indirectamente se llama proceso (o función) recursivo. .
Por ejemplo:
Procedimiento almacenado a;
comenzar
.
.
.
a
.
.
.
fin
Este método se llama directamente.
Otro ejemplo:
Procedimiento almacenado b;Procedimiento almacenado c;
comenzar comenzar
.
.
.
b;
.
.
.
end; end;
Este método es una llamada indirecta.
Ejemplo 1 Calcular n! Esto se puede lograr con la siguiente fórmula recursiva:
1 cuando n=0
fac(n)={n*fac(n-1) cuando ngt;0
p>El programa se puede escribir así:
Programa fac2;
var
n: integer;< readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
Ejemplo 2 Una escalera tiene n escalones. Puedes subir un escalón a la vez, un escalón a la vez o dos escalones a la vez.
Supongamos que el número de formas de subir n escalones es f(n)
Obviamente hay
1 n=1
f( n)={2 n=2
f(n-1) f(n-2) ngt; 2
El proceso de programación del programa es el siguiente:
Programa loudi;
var n: entero;
función f(x: entero): entero;
comenzar
si x= 1 entonces f:=1 más
si x=2 entonces f:=2 más f:=f(x-1) f(x-2);
fin;
comenzar
escribir('n=');leer(n);
escribirn('f(',n,' )=',f( n))
end.
2.2 Cómo diseñar un algoritmo recursivo
1 Determinar la fórmula recursiva
2. Determine las condiciones de límite (finales)
Ejercicio:
Utilice la recursividad para completar los siguientes problemas
1.
2. Encuentra n enteros El producto de
4 Encuentra el promedio de n enteros
5. números naturales
6. Hay una pareja de macho y hembra. Los conejos crían una pareja cada dos meses. Dada la sucesión 1, 1, 2, 4, 7, 13, 24, 44,..., encuentra el enésimo término de la sucesión. Encuentra el enésimo término de una secuencia.
2.3 Ejemplos típicos
Ejemplo 3 Problema de Fanta
Como se muestra en la figura: Se sabe que hay tres agujas representadas por 1, 2 y 3. respectivamente, hay n placas colocadas en la aguja No. 1 de pequeña a grande. Ahora es necesario mover todas las placas de la aguja No. 1 a la aguja No. 3. La regla de movimiento es: use la aguja No. 2. Aguja como aguja redundante. Mueva solo una placa a la vez, en cada pasador.
No utilice la placa grande para presionar la placa pequeña. >El gran mercado no puede abrumar al pequeño mercado. Encuentra el programa con la menor cantidad de movimientos.
El programa es el siguiente:
Programa fanta;
var
n: entero
procedimiento; move(n, a, b, c. integer); while (b[j]gt; =x) y (jgt; i) hacen j: = j-1; comenzar t1: =b[i]; b[i]:=b[j]; b[j]:=t1;
mientras (b[i]lt;=x) y ( ilt;j ) hacer i:=i 1;
si ilt;j entonces comienza t1:=b[j];b[j]:=b[i];b[i]:=t1 ; fin
Hasta i=j
b[i]:=x
i:=i 1; /p>
si s?lt;j entonces Quicksort(b,s,j);
si ilt;t entonces Quicksort(b,i,t);
fin;
comenzar
escribir('datos de entrada: ');
para i:=1 a n leer(a[i]);
writeln;
quicksort(a, 1, n);
write('datos de salida: '); =1 a n escribir(a[i]:6);
writeln;
end.
Ejercicio:
1 Calcular A El valor de la función de Kmann:
n 1 m=0
ack(m, n)={ ack(m-1, 1) mlt; , n=0
ack(m-1, ack(m, n-1)) mlt; 0, nlt; 0
ack(5, 4)
Retroceder
Retroceder es el acto de buscar hacia adelante bajo ciertas condiciones. Si la búsqueda hacia adelante no tiene éxito, puede retroceder y continuar la búsqueda de otra manera.
3.1 Diseño de retroceso
1. Utilice la pila para guardar parte del estado de avance.
2. Establecer restricciones
Ejemplo 1 Ingrese n símbolos desde el teclado; genere el arreglo completo.
programa hh;
const n=4;
var i, k: entero
x: matriz[1.n; ] de entero;
st: cadena[n];
t: cadena[n];
entrada de procedimiento; i: entero;
comenzar
escribir('Ingresar cadena=');
t:=st;
end;
función lugar(k: inicio;
lugar:=true;
para i:=1 a k-1 hacer
si x[i]=x[k] entonces
comenzar lugar:=false; romper final
Fin
Proceso de impresión;
var i:integer;
comenzar
for i:=1 to n escribir(t[x[i]]
);escribir;
fin
comenzar
entrada
k:=1; ;
while kgt; 0 hacer
comenzar
x[k]:=x[k] 1;
while (x [k]lt;=n) y (no lugar(k)) hacer x[k]:=x[k] 1;
si x[k]gt;n entonces k:=k- 1
si no k=n entonces imprime
si no comienza k:=k 1;x[k]:= 0 fin
fin;
fin.
Ejemplo 2. Problema de n reinas:
Programa hh
const n=8
var; i, j, k: entero;
x: matriz[1..n] de entero;
x: matriz[1.n] de entero
<; p>funciónfunción lugar(k: entero): booleano;
var i: entero
comenzar
lugar: = true;
para i:=1 a k-1 hacer
si (x[i]=x[k ]) o (abs(x[i]-x[ k ])=abs(i-k)) entonces
lugar:=false;
fin;
impresión del procedimiento
var i: entero;
comenzar
para i.=1 a n escribir(x[i]: 4
escribir
< p); > fin;comenzar
k:=1; x[k]:=0;
mientras kgt 0 hacer
comenzar
x[k]:=x[k] 1;
> while (x[k]lt;=n) y (not place(k)) hacen x[k]:=x[k] 1;
si x[k]gt;n entonces k :=k-1
si no k=n entonces imprimir
si no comenzar k:=k 1 x[k]:=0 terminar
terminar; ;
fin.
La fórmula del algoritmo de seguimiento inverso es la siguiente:
3.2 Implementación recursiva del algoritmo de seguimiento inverso
Debido a lo contrario, el algoritmo de seguimiento se implementa a través de una matriz de pila, por lo que el uso de pilas generalmente se puede implementar de forma recursiva.
El método recursivo en el Ejemplo 1 se implementa de la siguiente manera:
Programa hh
const n=4
var i, k: entero;
x: matriz[1...n] de entero;
st: cadena[n]; /p >
comenzar
intentar(1);
finalizar.
Programa 2:
Instrucciones:
Cuando n=8, hay 30 diagonales, que están controladas por las matrices l y r,
y las columnas están controladas por la matriz c.
El programa recursivo es el siguiente:
Programa nhh;
const n=8
var s, i: integer
a: matriz [1..n]matriz de bytes;
c.matriz booleana[1...n];
l: matriz booleana[1-n..n- 1] ;
r: matriz booleana [2.2*n] de salida del procedimiento booleano;
var i: entero
incluye lo siguiente
begin
for i:=1 to n do write(a[i]:4
inc(s);writeln); (' total=', s);
fin;
procedimiento try(i. entero);
r: matriz[2: entero); /p >
var j:integer;
comenzar
for j:=1 to n do
comenzar
if c[ j] y l[i-j] y r[i j] entonces
comenzar
a[i]:=j; c[j]:=false; := false.l[i-j]:=false; r[i j]:=false;
si ilt;n entonces intente(i 1) otra salida;
c[j ]: =verdadero; l[i-j]:=verdadero; r[i j]:=verdadero;
fin
fin
p>
comenzar
para i: para i: = 1 a n hacer c[i]: = verdadero
para i: = 1-n a n-1; do l [i]:=true;
para i:=2 a 2*n do r[i]:=true;
s:=0; ;
escribir;
fin.
Ejercicio:
1 Desde Encuentra todas las combinaciones de n(nlt;=m) elementos entre m elementos.
2. Hay 5 personas A, B, C, D y E dedicadas a 5 trabajos j1, j2, j3, j4 y j5 respectivamente. Cada persona solo puede desempeñar un tipo, su <. /p>
La cuenta de resultados es la siguiente:
j1j2j3j4j5A13111047B13101085C59774D151210115E1011884
Encuentre el mejor acuerdo con el mayor ingreso.
3. Encuentre M números entre N números (ingrese los enteros positivos N y M desde el teclado y luego ingrese N números positivos) y solicite M números de N números.
Buscar varios números para que su suma sea M, encuentre los arreglos que cumplan las condiciones y cuente el número de grupos.
4. Coloración de mapas. Como se muestra en la siguiente figura, 12 áreas están coloreadas con 4 colores, lo que requiere que las áreas adyacentes sean de diferentes colores
5. Descomponga cualquier número entero positivo (1lt; nlt; 100) en varias sumas de enteros positivos. .
Por ejemplo: 4=1 1 1 1
=2 1 1
=2 2
=3 1. p >
6.