El segundo esquema de tratamiento secuencial es el de búsqueda. Te permitirá buscar un elemento concreto dentro de una secuencia.
A diferencia del esquema de recorrido de una secuencia, en el cual, se recorría toda la secuencia siempre, en este esquema, se recorre la secuencia hasta encontrar el elemento que cumpla con una condición determinada.
Tabla de contenidos
Concepto de secuencia, cabezal y posición extra
La secuencia es el número de elementos que tenemos que tratar o comprovar.
El cabezal representa hacía qué elemento apunta o está tratando el algoritmo en cada una de las iteraciones.
La posición extra es cuando el cabezal está situado más allá de los elementos a tratar de la secuencia. En la imagen de abajo, la posición extra sería el número 9, la secuencia es del 1 al 8.
Plantilla del esquema de búsqueda
Primero te presento el esquema o plantilla del esquema de búsqueda, que deberás ir refinando en los pasos siguientes.
algoritmo esquemaBusqueda
var
encontrado: booleano;
fvar
preparar secuencia
encontrado := falso;
inicio tratamiento
{cabezal está al principio de la secuencia,
todavía no se ha tratado ningún elemento}
mientras no fin secuencia y no encontrado hacer
{tratado la parte izquierda del cabezal. El
elemento buscado no está en esta parte de la
secuencia y elcabezal no está en la posición
extra final}
actualizar encontrado
si no encontrado entonces
tratar elemento
avanzar secuencia
fsi
{tratado la parte izquierda secuencia,
el elemento buscado no está en esta parte
de la secuencia. Si encontrado es cierto,
se ha encontrado el elemento buscado}
fmientras
{secuencia tratada. cabezal final secuencia.
El elemento buscado no está en esta parte de la
secuencia. Si encontrado es cierto, el cabezal
apunta al elemento buscado. Y si es falso, el
cabezal estará en el final de la secuencia}
tratamiento final
falgoritmo
Este esquema está preparado para el caso que la secuencia recorrida no contenga el elemento buscado. En ese caso, la variable encontrado seguirá valiendo falso. En cada iteración, el condicional hace avanzar la secuencia y realizar cálculos según convenga.
Si la secuencia contiene el elemento buscado, el algoritmo no entra en el condicional, ya que la variable encontrado es cierta, por lo que no se actualiza el cabezal.
En la siguiente iteración, como ya no se cumple la condición…mientras no fin secuencia y no encontrado hacer se sale del bucle y el tratamiento final se aplica al elemento deseado.
Refinamiento del esquema
Ahora toca adaptar la plantilla a nuestras necesidades. Para ilustrar este esquema desarrollaremos un algoritmo que determine si un número es primo.
El algoritmo debe retornar cierto si sí lo es y falso en caso contrario. Si te fijas, vamos a desarrollar una función que realice esta «sencilla tarea» que después puedes reutilizar en cualquier programa para realizar tareas más complejas que necesiten comprobar si un número es primo.
Nota: Recuerda que un número es primo cuando tiene exactamente dos divisores; el 1 y él mismo. Por lo tanto, el número 1 no se considera primo porque sólo tiene un divisor.
Aquí te muestro la función, para después razonarla:
funcion esPrimo(n:entero): booleano
{Pre: n > 0}
var
encontrado, primo: booleano;
i: entero;
fvar
i:=2; // preparar secuencia
encontrado := falso;
mientras i < n y no encontrado hacer // fin secuencia
si n mod i = 0 entonces
encontrado := cierto; // actualizar encontrado
fsi
si no encontrado entonces
i := i + 1; // avanzar secuencia
fsi
fmientras
primo := no encontrado;
retorna primo;
{Post: primo es cierto si n es primo y
falso en caso contrario}
ffuncion
Preparación de secuencia
Como tenemos que recorrer la secuencia de número entre 1 y el número que queremos comprobar si es primo, la secuencia siempre empezará en 2, ya que como hemos dicho 1 no es primo y cualquier número es divisible entre 1. Por lo tanto, la preparación de la secuencia en este caso consiste en inicializar una variable a 2. La he llamado i.
i := 2;
Inicio tratamiento
En este caso concreto no hay tratamiento inicial.
Fin del tratamiento secuencia
El final de la secuencia corresponde cuando la variable i sea mayor o igual que n, es decir el número que hay que comprobar si es primo.
Nota: Observa que si queremos saber si el número 2 es primo, no llega a entrar en el bucle mientras, ya que la condición de fin de secuencia es i<n y 2<2 es falsa, por lo tanto daría un falso negativo. Pero, la última instrucción antes de devolver el valor niega la variable primo, por lo tanto salvamos la situación.
Actualizar variable encontrado
Si hacemos el módulo entre el número n y un número entre 1 y el número n-1 (sin contar estos dos) y como resultado da 0, quiere decir que es divisible. Por lo tanto ese número no es primo. En este caso hay que actualizar la variable encontrado al valor cierto, para que en la próxima iteración salga del bucle.
encontrado := cierto;
Avanzar secuencia
Aquí sencillamente incrementamos en 1 la variable i.
i := i + 1;
Tratamiento final
El retorno más lógico de esta función sería devolver falso si el número no es primo y cierto si sí lo es. Pero he planteado el problema de la forma que cuando encuentra un divisor la variable encontrado pasa a cierto (no es primo) y cuando no encuentra un divisor la varaible encontrado es falso ( es primo). Por eso en el tratamieno final tenemos que negar el resultado de la variable primo.
primo := no encontrado;
Metodología
Como te indiqué en la anterior entrada sobre el esquema de recorrido de una secuencia, en el último apartado, es muy importante seguir la misma metodología. Es una forma de centrase en el problema y no dejarse aspectos críticos, como bucles infinitos o que dejes valores de la secuencia sin contemplar.
Si te ha gustado o te ha aclarado conceptos el contenido de este artículo compártelo en redes sociales para que pueda crecer, ¡Muchas gracias!
Deja una respuesta