Diseño de Algotirmos mediante Arreglos

Estructuras de datos

Hasta ahora se han usado datos que representan valores de tipo simple como un número entero, real ó carácter.

Sin embargo, en muchas situaciones se necesita procesar un conjunto de valores que están relacionados entre sí por algún método, por ejemplo, una lista de calificaciones, una serie de temperaturas.

En este caso, el procesamiento con datos simples se hace muy difícil, por lo que la mayoría de los lenguajes de programación incluyen características de estructuras de datos

En computación, una estructura de datos es una manera de almacenar información (datos) en un computador de manera que puedan ser usados de una manera eficiente. Una selección cuidadosa de la estructura permitirá usar un algoritmo más eficiente. Una estructura bien diseñada permitirá efectuar una variedad de operaciones, usando un mínimo de tiempo de ejecución y espacio de memoria.

Los tipos de datos mas utilizados son:

Las estructuras de datos estáticas son aquellas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no puede modificarse dicho tamaño durante la ejecución del programa.

Las estructuras dinámicas pueden ser definidas en tiempo de ejecución y la limitación seria el tamaño de la memoria disponible.

1.1. Arreglos Unidimensionales – NDimensionales.

Un arreglo es una secuencia de posiciones consecutivas de memoria que almacenan datos del mismo tipo.Estos datos comparten un nombre común.

En cuanto a su dimensión ,los arreglos se pueden clasificar como :

Unidimensionales:

Vector, lista, matriz de una dimensión.

Ej : Un vector denominado ventas, de 10 elementos, se puede representar como :

El subíndice de cada elemento designa su posición en la ordenación del vector. Se observa que todos los elementos comparten el nombre y que cada elemento se referencia por su subíndice o sea su posición relativa en el vector.

Declaración de un arreglo Unidimensional :

Estático :

tipo nombre [dimensión]

Ej : la instrucción entero x[8] declara un arreglo de nombre x, de 8 elementos de tipo entero.

Bidimensionales (Tabla, Matriz ) :

Se pueden considerar como un vector de vectores. En este caso se necesita especificar dos subíndices para identificar cada elemento del arreglo : El primer subíndice se refiere a las filas ( i ) y el segundo a las columnas ( j ) .

Declaración de un arreglo de dos dimensiones :

Estático :

tipo nombre [filas, coumnas]

Ej : entero A [3,3] declara un arreglo de datos tipo entero de 3 filas y tres columnas.

Almacenamiento de arreglos en memoria

Arreglos de Una y dos dimensiones se representan como se muestra:

La memoria de la computadora es unidimensional, por lo que el almacenamiento de los arreglos de más de una dimensión requiere que la posición de los elementos del arreglo sea "linealizada".

La forma mas común de almacenamiento de vectores de dos dimensiones es por filas, así un vector A[3,4] se almacenaría de la manera siguiente:

La posición de un elemento A[i,j] del arreglo A[3,4] de dimensiones [m,n] con relación al primer elemento es: Posición = n*(i -1) + j

Así la posición dentro del arreglo del elemento A[2,3] del ejemplo anterior sería:

m = 3, n = 4, i = 2, j = 3 Posición = 4 * (2 – 1) + 3 = 7

Operaciones sobre arreglos

Las operaciones que se pueden realizar con arreglos durante el proceso de resolución de un problema son:

• Asignación

• Lectura / Escritura

• Recorrido

• Búsqueda

• Ordenamiento.

Asignación :

La asignación de valores a un elemento de un arreglo se representa con la instrucción:

A[10] = 3 / asigna el valor 3 al elemento 10 del vector A

ventas[2,2] = 1500

Si se desea asignar valores a todos los elementos de un vector, se debe usar estructuras de repetición.

• Caso Unidimensional: Asignar el valor 6 a todos los elementos de un vector A[5]

repetir_desde ( i = 1; i <= 5 ; i=i+1)

A[i] = 6

fin_repetir_desde

• Caso Bidimensional: Inicializar un vector B[2,3] con el valor cero.

repetir_desde ( i = 1; i <= 2 ; i=i+1)

repetir_desde ( j = 1; j <= 3 ; j=j+1)

B[i,j] = 0

fin_repetir_desde

fin_repetir_desde

Lectura / Escritura :

La lectura/escritura de datos en arreglos u operaciones de entrada/salida, normalmente se realizan con estructuras repetitivas o selectivas. Las instrucciones simples de lectura/escritura se representan como:

leer(Nombre_del_arreglo[Indice])

mostrar(Nombre_del_arreglo[Indice])

Ej : leer(X[3]) / Lee el elemento 3 del vector X

Recorrido :

A la operación de efectuar alguna acción sobre todos los elementos del vector se le llama recorrido. Estas operaciones se realizan usando estructuras de repetición, cuyas variables de control se usan como índices del vector. Se puede realizar esta operación para introducir datos al vector (leer) o para ver su contenido (mostrar).

Ejemplo 1: Lectura de los 10 valores de un vector P.

Ejemplo 2: El siguiente algoritmo lee las notas del primer examen de Computación de una sección de 40 alumnos , a fin de calcular el promedio.

Si se deseara mostrar la cantidad de alumnos con notas superiores al promedio se agregan las siguientes líneas al algoritmo anterior:

Ejemplo 3: Leer una matriz de dos dimensiones A[5,4].

Dado que es una matriz de dos dimensiones, se necesitan dos bucles anidados para recorrer todos sus elementos.

Ejemplo 4: Inicializar una matriz de dos dimensiones con valor constante 0.

El algoritmo debe asignar la constante 0 a todos los elementos de la matriz A[5,4].

Dado que es una matriz de dos dimensiones, se necesitan dos bucles anidados para recorrer todos sus elementos:

Ejemplo 5: Realizar la suma de dos matrices bidimensionales.

Para sumar dos matrices es preciso que las dos matrices tengan las mismas dimensiones. La matriz suma[I,J] tendrá las mismas dimensiones de las matrices sumandos y cada elemento será la suma de los mismos elementos correspondientes en las matrices sumandos: suma[I,J] = A[I,J] + B[I,J].

Dado que las matrices son de dos dimensiones se requieren dos bucles anidados:

Ejemplo 6: Diseñar un algoritmo que genere una matriz identidad de orden n.

• La matriz identidad tiene todos los elementos de la diagonal principal igual a uno (1), todos los demás elementos son igual a cero (0).

• En los elementos de la diagonal principal I = J.

Algoritmos Básicos de Búsqueda y Ordenamiento

Búsqueda :

La operación de búsqueda es una de las tareas más comunes en computación y básicamente consiste en encontrar la posición de un elemento específico en un conjunto de elementos dados.

Búsqueda secuencial :

Suponemos una lista (vector) de elementos, donde no hay elementos repetidos ; la forma mas sencilla de buscar un elemento específico es recorriendo la lista y verificando si existe alguna coincidencia entre los elementos de la lista y el elemento buscado.

Ejemplo: Suponemos se desea buscar un nombre en una lista de n elementos. El algoritmo debe mostrar los mensajes :

– nombre encontrado, si el nombre está en la lista.

– nombre no existe, si no se encuentra el nombre.

Se supone que no hay elementos repetidos.

Análisis : Se requiere leer el número de elementos ( n ) y el elemento a buscar. Se debe recorrer toda la lista y preguntar si cada elemento de la lista es el que estamos buscando, para lo cual se requiere un ciclo con contador (i – desde 1 hasta n) y una estructura de decisión para confirmar la condición del elemento buscado.

Se usa además una variable tipo interruptor (sw) , la cual se incializa en cero antes de comenzar el ciclo de búsqueda y se cambia a uno cuando se encuentra el nombre buscado.

Diseño del algoritmo :

Búsqueda Menor / Mayor :

El problema consiste en buscar el elemento menor/mayor de un conjunto de elementos almacenados en un arreglo. Por ejemplo, buscar el elemento mayor del vector A mostrado:

Análisis :

La estrategia a seguir consiste en asignar la condición deseada (MAYOR) al primer elemento de la lista (A[1]) y se empieza a comparar con todos los elementos de la lista. Si alguno de los elementos resulta mayor que el elemento al cual se le ha asignado la condición, se cambia la condición al nuevo elemento. Al terminar de recorrer todo el vector, el valor que mantiene la condición deseada es el mayor.

Los resultados sobre el ejemplo se podrían ver como sigue:

Diseño del algoritmo:

Ordenamiento

El ordenamiento es una labor común que realizamos continuamente y es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente organizar información de una manera especificada (criterio de ordenamiento).

El ordenamiento puede ser:

Interno : La operación se realiza en memoria central. (Arreglos)

Externo: La operación se realiza sobre un soporte externo (Archivos).

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás.

Método de Intercambio o de burbuja:

El algoritmo se basa en el principio de comparar pares de elementos e intercambiarlos entre sí hasta que estén todos ordenados.

Para intercambiar dos elementos A[i] y A[i+1], es necesario considerar una variable auxiliar, usando el siguiente procedimiento:

aux = A[i]

A[i] = A[i+1]

A[i+1] = aux

Ejemplo:

Aplicaciones sobre Arreglos

1.- Dados tres arreglos A, B, C de n elementos enteros cada uno, generar un cuarto arreglo D de tres elementos, donde el contenido de cada elemento sea la suma de los elementos de A , B y C, es decir : D[1] = A[1]+ A[2]+ A[3]+…A[n]…..

Diseño del Algoritmo :

Algoritmo Creación de Arreglo

Inicio

2.- Un vendedor que hizo 20 ventas en el día desea calcular su comisión total sobre las ventas diarias, sabiendo que le corresponde un 5% de comisión sobre artículos cuyo precio es menor de 10000 Bs.y el 10% de comisión por artículos cuyo precio = 10000 Bs. ó mas.Además,el vendedor desea saber cuantas ventas hizo menores de 10000 y cuántas de 10000 ó mas.

El algoritmo debe permitir realizar los diferentes procesos como opciones a escoger por el usuario, como un dato de entrada.

Diseño del Algoritmo:

Algoritmo Cálculo de comisión

Inicio

entero i,cont_menor, cont_mayor, opción

real precio[20], comisión, comisión_total

caracter respuesta

cont_menor = 0, cont_mayor = 0,comisión_total = 0

respuesta = "s"

Repetir mientras (respuesta == "s")

Mostrar ("Introduzca su opción : 1.- Leer arreglo de precios

2.- Calcular comisión

3.- Mostrar resultados " )

Leer (opción)

En caso de (opcion)

caso 1 :

Repetir desde ( i= 1; i <=20) ; i=i+1)

Mostrar ( " Introduzca el precio del artículo ", i )

Leer ( precio[i] )

Fin Repetir desde

caso 2 :

Repetir desde ( i= 1; i <=20) ; i=i+1)

Si ( Precio [i]< 10000)

comisión = 0.05*precio[i]

cont_menor = cont_menor + 1

sino

comisión = 0.10*precio[i]

cont_mayor = cont_mayor + 1

Fin Si

comisión_total = comisión_total + comisión

Fin Repetir desde

caso 3 :

Mostrar ( "Artículos vendidos con precio inferior a 10000 :",

cont_menor )

Mostrar ( "Artículos vendidos con precio superior a 10000 :",

cont_mayor )

Mostrar (" Comisión total del vendedor = ", comisión_total )

Fin En caso de

Mostrar (" Desea continuar : s/n ")

Leer (respuesta )

Fin Repetir mientras

Fin

3.- Un tablero de damas se puede representar con un arreglo de 8 filas por 8 columnas, donde un 1 representa la presencia de una ficha roja en el tablero, un 2 representa la presencia de una ficha negra y un tres representa ausencia de ficha.

Se requiere calcular y mostrar :

El número de fichas rojas , el número de fichas negras y el número total de fichas.

4.- Se tiene el monto de cada una de 100 ventas realizadas por una vendedora de un establecimiento comercial. Por cada venta calcule : el IVA de 15.5 %, calcule y muestre el monto a pagar incluyendo el IVA, calcule y muestre el monto total en ventas y monto total en impuesto por todas las 100 ventas.

Análisis:

• EL dato sería un vector VENTAS[100], el cual contiene los montos de las 100 ventas.

• Se debe generar un vector IVA[100],haciendo IVA[I] = VENTAS[I]*0.155.

• El monto a pagar de cada venta se guarda en un vector MONTO[100]. Este vector se calcula haciendo MONTO[I] = Ventas[I] + IVA[I].

• El monto total en ventas (T_VENTAS) se obtiene sumando los elementos del vector MONTO[100].

• El monto total de impuesto (T_IMP) se obtiene sumando los elementos del vector IVA[100].

Diseño del algoritmo:

• Se requiere calcular el vector IVA para lo cual es necesario recorrer el vector ventas y multiplicar cada elemento por el 15.5 %.

• Dentro del mismo ciclo se puede calcular el vector MONTO.

5.-Llenar un vector de n elementos con los primeros n valores enteros y primos.

Análisis:

• Un número primo es aquel que es divisible únicamente por el mismo y la unidad. Para chequear si un numero es divisible por otro se usa la función mod, la cual devuelve el resto de la división : si (A mod B = 0 ),el número A es divisible por B.

• Para verificar si un número es primo se comprueba la división del número por todos los valores enteros que están por debajo de el, excluyendo la unidad y el número mismo.

• Los números 1,2 y 3 son primos.

Diseño del algoritmo:

6.-Generar la siguientes matrices:

Análisis:

• las matrices se almacenan como se muestra:

• La matriz A se recorre por filas y se asigna a cada elemento un valor que puede ser un contador inicializado en 1.

• La matriz B se recorre por columnas y se asigna a cada elemento un valor que puede ser el contador inicializado en 1.

• La matriz C se crea utilizando un criterio (i == j) para llenarla.

Diseño del algoritmo:

Ejercicios propuestos

ESTRUCTURAS DE DATOS (ARREGLOS)

1. Escriba un algoritmo que lea una lista de N números reales y calcule el promedio de estos números.

2. Si XPR representa la media de los numero X1, X2, X3,….XN, la varianza es la media de los cuadrados de las desviaciones de los números de la media y la desviación estándar es la raíz cuadrada de la varianza:

Escriba un algoritmo que lea una secuencia de números reales y a continuación calcule y muestre su media, varianza y desviación estándar.

3. Escriba un algoritmo que lea un vector de números enteros y determine el valor máximo y el valor mínimo.

4. Diseñe un algoritmo que lea una lista de números reales y calcule la media de los números de posiciones pares y la media de los números de posiciones impares.

5. Escriba un algoritmo que lea una matriz NxN de números enteros y determine la posición de la matriz en la que se encuentra el valor máximo.

6. Escriba un algoritmo que efectúe la suma y la resta de dos matrices NxM de números reales.

7. Una agencia de ventas de vehículos distribuye 10 modelos y tiene contratados 15 vendedores. Escribir un algoritmo que calcule y muestre una tabla resumen donde se muestre:

a. Cuantos autos colocó cada vendedor.

b. Cuantos autos se vendieron, por modelo.

c. Cual modelo se vendió menos.

d. Organizar la información de manera que se muestre en forma creciente las ventas totales por vendedor.

8. Diseñe un algoritmo que lea un vector de 500 elementos enteros y a partir de ese vector genere un nuevo vector con un máximo de 30 elementos, donde cada elemento es primo.

Autor:

Pablo Turmero