Explicación detallada del algoritmo de Pascal para retroceso y recursividad.

En el proceso de edición del programa, podemos encontrarnos con este tipo de problemas. El creador de la pregunta le dice los primeros números de la secuencia u obtiene los primeros números de la secuencia a través de la computadora y requiere que el programador encuentre el enésimo. número o secuencia de todos los elementos de (si son enumerables), o la suma de los primeros N elementos. Los algoritmos que comienzan con datos conocidos, encuentran reglas y derivan números posteriores se denominan algoritmos recursivos.

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

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ón

funció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.

6.