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