¿Qué es la iteración? .

El algoritmo iterativo es un método básico para resolver problemas con ordenadores. Aprovecha la rápida velocidad de computación de la computadora y es adecuado para operaciones repetitivas, lo que permite que la computadora ejecute repetidamente un conjunto de instrucciones (o ciertos pasos). Cada vez que se ejecuta este conjunto de instrucciones (o estos pasos), el valor original. La variable se cambia. Empújela a un nuevo valor.

El uso de algoritmos iterativos para resolver problemas requiere realizar los siguientes tres aspectos:

1. Determinar las variables de iteración. En los problemas que pueden resolverse mediante algoritmos iterativos, hay al menos una variable que directa o indirectamente deriva continuamente nuevos valores a partir de valores antiguos. Esta variable es la variable de iteración.

2. Establecer una relación iterativa. La llamada relación iterativa se refiere a la fórmula (o relación) de cómo derivar el siguiente valor de una variable a partir de su valor anterior. El establecimiento de relaciones iterativas es la clave para resolver problemas iterativos, lo que normalmente se puede lograr mediante recursividad o razonamiento hacia atrás.

3. Controlar el proceso iterativo. ¿Cuándo termina el proceso iterativo? Esta es una cuestión que debe tenerse en cuenta al escribir programas iterativos. El proceso iterativo no se puede repetir infinitamente. El control del proceso iterativo generalmente se puede dividir en dos situaciones: una es que el número requerido de iteraciones es un valor determinado y se puede calcular; la otra es que el número requerido de iteraciones no se puede determinar; Para el primer caso, se puede construir un número fijo de bucles para controlar el proceso iterativo; para el segundo caso, es necesario analizar más a fondo las condiciones para finalizar el proceso iterativo.

Ejemplo 1: Una granja de cría introduce una nueva raza de conejo que recién nace. A partir del mes siguiente al nacimiento de este conejo, nace un conejo cada mes y los conejos recién nacidos también se reproducen. Por aquí. Si no mueren todos los conejos, ¿cuántos conejos habrá en la granja al mes 12?

Análisis: Este es un problema típico de recursividad. También podríamos suponer que el número de conejos en el primer mes es u 1, el número de conejos en el segundo mes es u 2, el número de conejos en el tercer mes es u 3,... Según el significado de la pregunta, "Esto "Los conejos reproductores darán a luz a un conejo cada mes a partir del mes siguiente al nacimiento", entonces u 1 = 1, u 2 = u 1 + u 1 × 1 = 2, u 3 = u 2 + u 2 × 1 = 4,...

Según esta regla, se puede resumir la siguiente fórmula recursiva:

u n = u n - 1 × 2 (n ≥ 2)

Correspondiente a u n y u n - 1, defina dos variables de iteración y y x. La fórmula de recursividad anterior se puede convertir en la siguiente relación de iteración:

y=x*2

x=y

Deje que la computadora repita esta relación iterativa 11 veces para calcular la cantidad de conejos en el duodécimo mes. El programa de referencia es el siguiente:

cls

x=1

para i=2 a 12

y=x*2

x=y

siguiente i

imprimir y

end

Ejemplo 2: Amoeba usa división simple La reproducción tarda 3 minutos cada vez que se divide. Coloque varias amebas en un recipiente lleno de líquido nutritivo de ginseng. Después de 45 minutos, el recipiente se llena con amebas. Se sabe que los contenedores contienen hasta 220 amebas. Déjame preguntarte ¿cuántas amebas se pusieron en el contenedor al principio? Por favor prográmelo y calcúlelo.

Análisis: Según el significado de la pregunta, la ameba se divide cada 3 minutos. Luego coloque la ameba en el recipiente desde el principio y llene el recipiente después de 45 minutos. Necesita dividirse 45/3 =. 15 De segunda categoría. Y "el contenedor puede contener hasta 2 20 amebas", es decir, el número de amebas que se obtienen después de dividir 15 veces es 2 20. La pregunta requiere que calculemos el número de amebas antes de la división. También podríamos usar el método hacia atrás Del 2 al 20 después de la 15.ª división, podemos trabajar hacia atrás para deducir el número antes de la 15.ª división (es decir, después). la 14.ª división), y luego trabaje hacia atrás para deducir el número después de la 13.ª división, después de la 12.ª división y... antes de la primera división.

Supongamos que el número antes de la primera división es x 0, el número después de la primera división es x 1, el número después de la segunda división es x 2,... la decimoquinta división El siguiente número es x 15 , entonces existen

x 14 =x 15 /2, x 13 =x 14 /2,... x n-1 =x n /2 (n ≥ 1)

Debido a que se conoce el número x 15 después de la división 15, si la variable de iteración se define como x, la fórmula hacia atrás anterior se puede convertir en la siguiente fórmula de iteración:

x=x/2 (El valor inicial del número de autobuses. Debido a que el número requerido de iteraciones es un valor determinado, podemos usar un número fijo de bucles para controlar el proceso de iteración. El programa de referencia es el siguiente:

cls

x=2^20

para i=1 a 15

x=x /2

siguiente i

imprimir x

end

Ejemplo 3: verificar la conjetura del ángulo del valle. El matemático japonés Shizuo Tanikaku descubrió un fenómeno extraño al estudiar los números naturales: para cualquier número natural n, si n es un número par, se divide por 2; si n es un número impar, se multiplica por 3 y luego se suma 1; Después de un número finito de operaciones, siempre se puede obtener el número natural 1. La gente llama a este descubrimiento de Shizuo Taniyakaku la "Conjetura de Tanikaku".

Requisitos: escriba un programa que ingrese un número natural n desde el teclado e imprima el proceso completo de conversión de n en un número natural 1 después de un número finito de operaciones.

Análisis: Defina la variable de iteración como n. Según el contenido de la conjetura de Gujiao, podemos obtener la relación de iteración en dos situaciones: cuando n es un número par, n = n/2; un número impar, n=n*3+1. Para describirlo en lenguaje QBASIC es:

si n es un número par entonces

n=n/2

si no

n = n*3+1

end if

Este es un proceso iterativo que requiere que la computadora se ejecute repetidamente. No podemos calcular cuántas veces es necesario repetir este proceso de iteración antes de que la variable de iteración n finalmente se convierta en un número natural 1. Por lo tanto, es necesario determinar más a fondo las condiciones para finalizar el proceso iterativo. Después de analizar cuidadosamente los requisitos de la pregunta, no es difícil ver que para cualquier número natural n dado, siempre que se pueda obtener el número natural 1 después de un número limitado de operaciones, el trabajo de verificación se ha completado. Por tanto, la condición utilizada para finalizar el proceso iterativo se puede definir como: n=1. El procedimiento de referencia es el siguiente:

cls

ingrese "Por favor ingrese n=";n

hacer hasta n=1

si n mod 2=0 entonces

rem Si n es un número par, llame a la fórmula de iteración n=n/2

n=n/2

imprimir "—"; n;

else

n=n*3+1

imprimir "—";n;

end if

bucle

end

Método iterativo

El método iterativo es un método de diseño de algoritmos comúnmente utilizado para encontrar raíces aproximadas de ecuaciones. o sistemas de ecuaciones. Supongamos que la ecuación es f(x)=0, utilice algún método matemático para derivar la forma equivalente x=g(x) y luego siga los siguientes pasos:

(1) Elija una raíz aproximada de la ecuación, asignar a la variable x0;

(2) Guarde el valor de x0 en la variable x1, luego calcule g(x1) y almacene el resultado en la variable x0;

(3 ) Cuando el valor absoluto de la diferencia entre x0 y x1 sea aún menor que el requisito de precisión especificado, repita el cálculo en el paso (2).

Si la ecuación tiene raíces y la secuencia de raíces aproximada calculada mediante el método anterior converge, entonces x0 obtenido mediante el método anterior se considera la raíz de la ecuación. El algoritmo anterior se expresa en forma de programa C como:

Método de iteración del algoritmo para encontrar las raíces de la ecuación

{ x0=raíz aproximada inicial;

do {

x1=x0;

x0=g(x1); /*Calcular nuevas raíces aproximadas según ecuaciones específicas*/

} while ( fabs(x0-x1 )>Epsilon);

printf("La raíz aproximada de la ecuación es %f\n", x0);

}

Los algoritmos iterativos también se usan comúnmente para encontrar las raíces del sistema de ecuaciones, sean

X=(x0, x1,…,xn-1)

Deje que el sistema de ecuaciones sean:

xi=gi(X ) (I=0, 1,..., n-1)

El algoritmo iterativo para encontrar las raíces del sistema de ecuaciones se puede describir de la siguiente manera:

El algoritmo iterativo para encontrar las raíces del sistema de ecuaciones

p>

{ for (i=0;i

x=raíz aproximada inicial;

hacer {

for (i=0;i

y=x;

for (i=0;i

x=gi(X);

para (delta=0.0,i=0;i

si (fabs(y-x )>delta) delta=fabs(y-x);

} while (delta>Epsilon);

for (i=0;i

printf(" La raíz aproximada de la variable x[%d] es %f", I, x);

printf("\n" );

}

Cuando utilice específicamente el método iterativo para encontrar raíces, debe prestar atención a las siguientes dos situaciones posibles:

(1) Si la ecuación no tiene solución, el algoritmo La secuencia de raíces aproximada obtenida no convergerá, y el proceso iterativo se convertirá en un bucle infinito. Por lo tanto, antes de utilizar el algoritmo iterativo, primero debe verificar si la ecuación tiene solución y limitar el número de iteraciones en el programa;

(2) Aunque el La ecuación tiene una solución, la selección inadecuada de la fórmula de iteración o la selección irrazonable de la raíz aproximada inicial de la iteración también hará que la iteración falle.

Recursión

La recursión es el diseño y Es una herramienta poderosa para describir algoritmos. Dado que se usa a menudo en la descripción de algoritmos complejos, lo discutiremos antes de presentar otros métodos de diseño de algoritmos.

Los algoritmos que generalmente se pueden describir de forma recursiva. Características: Para resolver un problema de tamaño N, intente descomponerlo en problemas de menor escala y luego construya fácilmente soluciones a problemas grandes a partir de las soluciones de estos problemas pequeños, y estos problemas de menor escala también pueden usar el mismo método. El método de descomposición y síntesis descompone el problema en problemas más pequeños y construye la solución al problema más grande a partir de las soluciones de estos problemas más pequeños. En particular, cuando la escala N = 1, la solución se puede obtener directamente.

Problema: Escribe la función fib(n) que calcula el enésimo término de la secuencia de Fibonacci.

Los números de Fibonacci son: 0, 1, 1, 2, 3,..., es decir:

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) (cuando n>1).

Escrito como una función recursiva:

int fib(int n)

{ if (n==0) return 0;

si (n==1) devuelve 1;

si (n>1) devuelve fib(n-1)+fib(n-2);

}

El proceso de ejecución del algoritmo recursivo se divide en dos etapas: recursividad y regresión. En la etapa recursiva, la solución de un problema más complejo (escala de n) se traslada a la solución de un problema que es más simple que el problema original (escala menor que n). Por ejemplo, en el ejemplo anterior, resuelva fib(n) y empújelo para resolver fib(n-1) y fib(n-2).

Es decir, para calcular fib(n), primero debes calcular fib(n-1) y fib(n-2), y para calcular fib(n-1) y fib(n-2), debes primero debe calcular fib (n-3) y fib (n-4). Por analogía, hasta que se calculen fib(1) y fib(0), los resultados 1 y 0 se pueden obtener inmediatamente respectivamente. En la fase recursiva, debe haber una situación para terminar la recursividad. Por ejemplo, en la función fib, cuando n es 1 y 0.

En la etapa de regresión, después de obtener la solución al caso más simple, regrese paso a paso para obtener soluciones a problemas un poco más complejos. Por ejemplo, después de obtener fib(1) y fib(0), regrese. para obtener fib(2),..., después de obtener los resultados de fib(n-1) y fib(n-2), devuelve el resultado de fib(n).

Al escribir funciones recursivas, tenga en cuenta que el conocimiento de las variables y parámetros locales en la función se limita a la capa de llamada actual. Cuando la recursividad ingresa a la capa de "problema simple", los parámetros y las variables locales están en. el nivel original estará oculto. A nivel de una serie de "preguntas simples", cada una tiene sus propios parámetros y variables locales.

Dado que la recursividad provoca una serie de llamadas a funciones y puede tener una serie de cálculos repetidos, la eficiencia de ejecución de los algoritmos recursivos es relativamente baja. Cuando un algoritmo recursivo se puede convertir fácilmente en un algoritmo recursivo, el programa generalmente se escribe de acuerdo con el algoritmo recursivo. Por ejemplo, la función fib(n) utilizada para calcular el enésimo término de la secuencia de Fibonacci en el ejemplo anterior debe usar un algoritmo recursivo, es decir, a partir de los dos primeros términos de la secuencia de Fibonacci, el siguiente término se calcula a partir del primeros dos términos uno por uno hasta Calcule el enésimo elemento requerido.

Problema Problema de combinación

Descripción del problema: Encuentra todas las combinaciones de r números de los números naturales 1, 2,..., n. Por ejemplo, todas las combinaciones de n=5 y r=3 son: (1) 5, 4, 3 (2) 5, 4, 2 (3) 5, 4, 1

(4) 5 , 3 , 2 (5) 5, 3, 1 (6) 5, 2, 1

(7) 4, 3, 2 (8) 4, 3, 1 (9) 4, 2, 1

(10) 3, 2, 1

Al analizar las 10 combinaciones enumeradas, puedes usar esta idea recursiva para considerar el algoritmo para encontrar la función de combinación. Supongamos que la función es void comb(int m, int k) para encontrar todas las combinaciones de k números cualesquiera de los números naturales 1, 2,..., m. Cuando se selecciona el primer número de la combinación, los números siguientes son combinaciones de k-1 números de los m-1 números restantes. Esto transforma el problema de encontrar la combinación de k números a partir de m números en el problema de encontrar la combinación de k-1 números a partir de m-1 números. Supongamos que la función introduce la matriz de trabajo a[ ] para almacenar los números de la combinación calculada. Se acuerda que la función colocará el primer número de las k combinaciones de números determinadas en a[k]. [] Una combinación de salidas. El primer número puede ser m, m-1,...,k. Después de que la función coloca el primer número de la combinación determinada en la matriz, hay dos opciones posibles ya que los elementos restantes de la combinación aún no se han eliminado. , la recursividad continúa para determinar; o debido a que se han determinado todos los elementos de la combinación, genera la combinación. Consulte la función peine en el siguiente programa para obtener más detalles.

Programa

# include

# define MAXN 100

int a[MAXN];

void comb (int m,int k)

{ int i,j;

for (i=m;i>=k;i--)

{ a[k]=i;

si (k>1)

comb(i-1,k-1);

else

{ para (j=a[0];j>0;j--)

printf(“%4d”,a[j]);

printf( "\n");

}

}

}

void main()

{ a [0]=3;

comb(5,3);

}

Problema Problema con la mochila

Descripción del problema: Diferente allí son n elementos de diferentes valores y pesos Encuentre un plan para seleccionar algunos elementos de estos n elementos de modo que el peso total de los elementos seleccionados no exceda el límite de peso especificado, sino la suma de los valores de los seleccionados. artículos es el más grande.

Supongamos que los pesos de n elementos son w0, w1,..., wn-1 respectivamente, y los valores de los elementos son v0, v1,..., vn-1 respectivamente. Utilice una opción recursiva para buscar elementos. Supongamos que hay varias opciones disponibles en el pasado, y la opción con el valor total más grande se conserva en la opción de matriz [], y el valor total de la opción se almacena en la variable maxv. Actualmente se está investigando un nuevo plan y el estado de selección de su elemento se almacena en la matriz cop[]. Supongamos que el plan actual ha considerado los primeros elementos i-1, y ahora debemos considerar el elemento i-ésimo, si es posible, la suma de los pesos de los elementos incluidos en el plan actual es tw; Para seleccionar los elementos restantes, qué se puede lograr con este plan. El valor esperado del valor total es tv. El algoritmo introduce tv cuando el valor esperado del valor total del plan actual también es menor que el valor total maxv del plan anterior, y continuar examinando el plan actual deja de tener sentido. El plan actual debe finalizarse y el siguiente plan. debe ser examinado inmediatamente. Porque cuando el valor total de la solución no es mayor que maxv, la solución no se volverá a examinar. Esto también garantiza que la solución encontrada después de la función será mejor que la solución anterior.

Existen dos posibilidades para la selección del artículo i:

(1) Considerar como seleccionado el artículo i. Esta posibilidad es sólo cuando su inclusión no exceda el peso total del mismo. solución. Sólo es factible bajo restricciones. Después de seleccionar, continúe recursivamente para considerar la selección de otros elementos.

(2) Considere que el ítem i no está seleccionado. Esta posibilidad sólo es posible cuando es posible encontrar una solución con mayor valor sin el ítem i.

Escriba el algoritmo recursivo basado en las ideas anteriores de la siguiente manera:

try (elemento i, la suma de los pesos seleccionados actualmente, el valor total tv que se puede lograr con este plan)

{ /*Considere la posibilidad de que el artículo i esté incluido en el plan actual*/

si (Incluir el artículo i es aceptable)

{ Incluir el artículo i en el plan actual en;

if (i

try(i+1,tw+peso del artículo i,tv);

else

/ *Otra solución completa, debido a que es mejor que la solución anterior, úsela como la mejor solución*/

Guarde la solución actual como la mejor solución temporal;

Restaurar el artículo i no tiene estado de inclusión

}

/*Considere la posibilidad de que el artículo i no esté incluido en el plan actual*/

if ( no incluir el elemento i solo es posible consideración masculina)

if (i

try(i+1,tw,tv-value of item i);

else

/*Otra solución completa, debido a que es mejor que la solución anterior, úsela como la mejor solución*/

Guarde la solución actual como la mejor solución temporal;

}

Para comprender el algoritmo anterior, se dan los siguientes ejemplos.

Son 4 ítems, sus pesos y valores se muestran en la tabla:

Artículo 0 1 2 3

Peso 5 3 2 1

Valor 4 4 ​​3 1

Y establece el límite de peso en 7. Según el algoritmo anterior, la siguiente figura muestra el proceso de encontrar la solución. Se puede ver en la figura que una vez que se encuentra una solución, el algoritmo busca una solución mejor. Si se puede determinar que no se encontrará una solución mejor en una determinada rama de búsqueda, el algoritmo no continuará buscando en esta rama, sino que terminará inmediatamente la rama y examinará la siguiente.

Escribe funciones y programas según el algoritmo anterior de la siguiente manera:

Programa

# include

# define N 100

doble límiteW,totV,maxV;

int opción[N],cop[N];

estructura { doble peso;

doble valor ;

}a[N];

int n;

void find(int i,double tw,double tv)

{ int k ;

/*Considere la posibilidad de que el artículo i esté incluido en el plan actual*/

if (tw+a.weight<=limitW)

{ cop =1;

if (i

else

{ para (k=0;k

opción [k]=policía[ k];

maxv=tv;

}

policía=0;

}

/* Considere la posibilidad de que el artículo i no esté incluido en el plan actual*/

if (tv-a.value>maxV)

if (i

else

{ para (k=0;k

opción[k]=cop[k];

maxv=tv-a .value;

}

}

void main()

{ int k;

doble w ,v;

printf("Ingrese el número de elementos\n");

scanf(("%d",&n);

printf( "Ingrese el peso y el valor de cada artículo \n”);

for (totv=0.0,k=0;k

{ scanf(“%1f%1f”,&w ,&v);

a[k].weight=w;

a[k].value=v;

totV+=V;

}

printf("Ingrese el peso límite\n");

scanf("%1f",&limitV);

maxv=0.0 ;

for (k=0;k find(0,0.0,totV);

for (k=0;k

si (opción[k ]) printf(“%4d”, k+1);

printf(“\nEl valor total es %.2f\n”,maxv);

}

A modo de comparación, lo siguiente es Con la misma idea de resolución de problemas, considere soluciones de programas no recursivos. Para mejorar la velocidad de búsqueda de soluciones, el programa no simplemente genera todas las soluciones candidatas una por una, sino que utiliza el impacto de cada elemento en las soluciones candidatas para formar soluciones candidatas que merezcan una mayor consideración. Se forma una solución candidata mediante examen. cada elemento por turno. Hay varias situaciones al examinar el elemento i: cuando el elemento está incluido en la solución candidata y aún cumple con el límite del peso total de la solución, el elemento debe continuar siendo considerado si está incluido en la solución candidata; El artículo no debe incluirse entre las soluciones candidatas que se están formando actualmente.

De manera similar, solo cuando el elemento no está incluido en la solución candidata y aún es posible encontrar una solución candidata que sea mejor que la mejor solución temporal actual, el elemento no se incluye en la solución candidata; Las soluciones incluidas en la solución candidata entre las soluciones candidatas actuales tampoco deben considerarse más a fondo. Para cualquier opción que merezca una mayor consideración, el programa pasa a considerar el siguiente elemento.

Programa

# incluir

# definir N 100

doble límiteW;

int cop[N] ;

estructura ele { doble peso;

doble valor;

} a[N];

int k,n;

estructura { int ;

doble tw;

doble tv;

}twv[N];

void next(int i,doble tw,doble tv)

{ twv.=1;

twv.tw=tw;

twv.tv=tv ;

}

doble buscar(struct ele *a,int n)

{ int i,k,f;

doble maxv,tw,tv,totv;

maxv=0;

for (totv=0.0,k=0;k

totv+=a[k] .value;

siguiente(0,0.0,totv);

i=0;

Mientras (i>=0)

{ f=twv.;

tw=twv.tw;

tv=twv.tv;

cambiar(f)

{ caso 1: twv.++;

if (tw+a.weight<=limitW)

if (i

{ siguiente(i+ 1 ,tw+a.weight,tv);

i++;

}

else

{ maxv=tv;

for (k=0;k

cop[k]=twv[k].!=0;

}

descanso;

caso 0: i--;

romper;

predeterminado: twv.=0;

if (tv-a. valor >maxv)

if (i

{ next(i+1,tw,tv-a.value);

i++;

}

else

{ maxv=tv-a.value;

for (k=0;k

poli [ k]=twv[k].!=0;

}

romper;

}

}

return maxv;

}

void main()

{ double maxv;

printf("Ingrese el número de elementos \n");

scanf(("%d",&n);

printf("Ingrese el peso límite\n");

scanf( "%1f",&limitW);

printf("Ingrese el peso y valor de cada artículo\n");

for (k=0;k

scanf(“%1f%1f”,&a[k].peso,&a[k].valor);

maxv=find(a,n);

printf ( "\nEl elemento seleccionado es\n");

for (k=0;k

if (opción[k]) printf("%4d",k+1 );

printf(“\nValor total

es %.2f\n”,maxv);

}

Conceptos básicos y características de la recursividad

La técnica de programación en la que un programa se llama a sí mismo se llama recursión ).

Un proceso o función se autodenomina directa o indirectamente método en su definición o descripción. Generalmente transforma un problema grande y complejo en un problema de mayor escala similar al problema original. problemas, la estrategia recursiva puede describir los múltiples cálculos repetidos requeridos en el proceso de resolución de problemas con solo una pequeña cantidad de programas, lo que reduce en gran medida la cantidad de código en el programa. La capacidad de la recursividad radica en el uso de declaraciones limitadas para definir infinitos objetos. Colección. Los programas escritos con pensamiento recursivo suelen ser muy simples y fáciles de entender.

En términos generales, la recursividad requiere condiciones de límite, secciones de avance recursivas y secciones de retorno recursivas.

Nota:

(1) La recursividad se llama a sí misma en un procedimiento o función.

(2) Cuando se utiliza una estrategia de recursión incremental, existe. Debe haber una condición de fin de recursión clara, llamada salida de recursión