Software

Introducción

El objetivo de este apartado es elaborar los fundamentos informáticos que formalizan la idea de acceso secuencial. Realizaremos este desarrollo sobre las sucesiones finitas, representadas por una estructura de datos que llamaremos secuencia. Una secuencia se define como un conjunto finito de objetos, del mismo tipo, que tienen asociadas las operaciones primer elemento y siguiente elemento que permiten, respectivamente, acceder a su primer elemento y avanzar a través de ella, elemento tras elemento. Además debemos disponer de algún mecanismo para determinar cuándo se accede al último elemento de la secuencia.

Simplificando, podemos ver una secuencia como los datos que se tratan dentro de uno mientras.

Leer y escribir secuencias

Inicialmente supondremos que las secuencias terminan en un centinela, que será un elemento del tipos en cuestión. Este elemento puede ser un ‘.’ en una secuencia de caracteres, un número negativo en una de números positivos, etc. En cualquier caso, el centinela debe aparecer sólo una vez en toda la secuencia. Con este convenio sabemos que hemos llegado a su fin.

Por ejemplo si estamos leyendo los datos desde el teclado nos tendrán que introducir algún valor para que nosotros sepamos que debemos finalizar la lectura. Si estamos leyendo los datos de un archivo, habrá un carácter de final de archivo, etc. Si los datos los generamos nosotros (por ejemplo sumar los 100 primeros números enteros), como en centinela podemos considerar el último valor entrado.

• No siempre necesitaremos un centinela. Si desde un principio sabemos la cantidad de datos que tendremos, nos servirá un contador.

Para disponer en nuestro lenguaje algorítmico de instrucciones que formalicen las operaciones sobre secuencias debemos definir dos grupos de instrucciones. El primero está formado, entre otros por dos instrucciones de lectura:

leer_primero(Seq, s)
leer_siguiente(Seq,s)

Las cuales posibilitan el acceso al primer elemento y al resto leyendo los elementos de uno en uno. Hay que entender que lo que hacen estas instrucciones es leer de la secuencia Seq y guardar el valor leído en la variable s.

El segundo grupo de instrucciones, compuesto por las que nos permiten crear secuencias y escribir en ellas, contendrá:

preparar(Sec)
escribir(Sec., s)
marca(secuencia)

Que preparan, añaden elementos y marcan secuencias, respectivamente. No permitiremos escribir elementos en secuencias inicializadas por lectura y viceversa.

Esquemas de recorrido y búsqueda: introducción

Veamos algunos problemas sencillo que permiten esquematizar los modelos fundamentales de algoritmos que actúan sobre secuencias:

Ejemplo 1.a Dado un texto terminado en punto

• a) Calcular el número de caracteres que tiene
• b) Contar el número de apariciones de la letra 'a'
• c) Comprobar si sale la letra w

Ejemplo 1.b Dada una secuencia de enteros no negativos terminada en -1

• a) Sumar todos los valores
• b) Contar el número de unos
• c) Indicar si todos los términos son pares

Si comparamos las soluciones de cada apartado de cada uno de estos ejemplos con las correspondientes del otro podemos ver ciertas semejanzas:

• Para resolver el apartado a) del primer ejemplo debemos ir contando los caracteres según recorremos la secuencia de principio a fin, mientras que en el del segundo ejemplo hemos de ir sumando todos los elementos que vayan apareciendo
• Para resolver el apartado b) también recorremos toda la secuencia aunque únicamente contamos las as en el primer caso y unos en el segundo
• Por el contrario en el último apartado la estrategia correcta debe considerar que si se encuentra el elemento deseado ( la letra ‘w’ en el primer caso, un número impar en el segundo) ya no ha de continuarse la búsqueda, de forma que sólo se llega al final si este elemento no aparece.

La aplicación de un esquema o de otro viene determinada por la necesidad, o no, de recorrer toda la secuencia. Así no se considera buena una solución basada en un esquema de recorrido si la estrategia adecuada por el problema no exige acceder a todos los elementos de la secuencia.

Esquema de recorrido

Ejemplo 1.a.b Contar las apariciones de la letra ‘a’ en un texto terminado en un punto

La condición del problema indica que al final del programa habrá una variable que contendrá el número de apariciones de la letra 'a' en la secuencia. La forma intuitiva de conseguirlo consiste en plantear una iteración donde se compruebe si el elemento en curso es una 'a' y en caso afirmativo se actualice la variable contadora y se avance en la secuencia.

Planteamos el problema y supongamos que tenemos una variable llamada num_a:

1. Condición invariante del bucle : num_a contendrá el número de a aparecido hasta el momento
2. Condición de continuación del bucle: el proceso terminará al final de la secuencia y por tanto la condición será Æ carácter en curso ≠ ‘.’
3. Inicialización : Dado que la primera instrucción será leer el primer elemento de la secuencia, la única posibilidad es asignarle a num_a el valor 0.
4. Cuerpo del bucle: Dado que debemos visitar todas las letras, deberemos comprobar si la letra actual es una ‘a’, incrementar num_a si así es y pasar al siguiente elemento.

Con lo cual el algoritmo quedaría así:

var c : carácter;num_a:entero; fvar
leer_primero (Seq, c);
num_a := 0;
mientras c ≠ '.' hacer
si c = ' a' entonces
  num_a := num_a + 1;
fsi
  leer_siguiente (Seq, c);
fmientras

Ejemplo 1.b.a Sumar los términos de una secuencia de enteros positivos terminada en cero

La misma discusión del ejemplo anterior sirve ahí. Recorremos la secuencia y almacenamos en la variable suma la suma de la parte visitada. Por tanto:

var x, suma:entero; fvar
leer_primero (Seq, x);
suma:=0;
mientras x ≠ 0 hacer
  suma := suma + x;
  leer_siguiente (Seq,x);
fmientras

Podemos abstraer los elementos básicos de un algoritmo de recorrido a partir de estos dos ejemplos:

declaración de variables
  acceder al primer elemento
  inicializar tratamiento
mientras no último elemento hacer
  tratar elemento
  obtener siguiente elemento
fmientras
  tratamiento final

Aquí hemos añadido un tratamiento final que en estos dos ejemplos no ha sido necesario pero que en algún otro problema puede ser necesario. Nótese que esto no es un algoritmo sino un esquema con instrucciones comprensibles.

Tweet

Whatsapp