EVAP 6

Matrices

Una matriz es una estructura de datos, o más técnicamente, un espacio de memoria que permite almacenar una colección de elementos, todos del mismo tipo. La diferencia con los arreglos está en que, en las matrices, los elementos no están organizados linealmente sino que su organización es bidimensional, es decir, en filas y columnas. Conviene imaginar una matriz como una organización de celdas de memoria, o casillas, en cada una de las cuales se puede guardar un elemento de la colección. Además, es usual dibujarla como lo ilustra la figura siguiente:

La numeración de las filas y las columnas determina que cada una de las casillas de una matriz tiene asociados dos números que la identifican de manera única. A estos números se les llama índice de fila e índice de columna, respectivamente. En el seudolenguaje, y también en C y C++, las filas y las columnas se numeran desde 0.

Los lenguajes como C y C++, permiten que el programador declare matrices de cualquier tipo y prácticamente de cualquier tamaño. En el seudolenguaje, un matriz se declara usando el siguiente formato:

<NOMBRE> : matriz [<N>][<M>] de <TIPO>

En este formato aparecen en mayúsculas y entre los caracteres < y > los componentes que el programador puede determinar. Así por ejemplo, si se quiere declarar una matriz con nombre mat, de dimensión 15x4 y que pueda almacenar datos de tipo caracter, se debe escribir la siguiente línea.

mat : matriz [15][4] de caracter

Según el formato anterior, el programador debe bautizar la matriz (ponerle un nombre significativo), debe decir cuál es su dimensión, y también debe decir de qué tipo son los elementos que almacenará.

Enseguida se dan algunos ejemplos de declaraciones de matrices.

• Si se necesita guardar la información relacionada con el tablero de un juego de tic tac toe (el tradicional triqui), se puede declarar la siguiente matriz:

tablero : matriz [3][3] de caracter

• Si se requiere guardar las notas que han sacado 35 estudiantes en los 5 talleres y en los 5 laboratorios del curso de Programación de Computadores se pueden declarar las siguientes matrices.

talleres : matriz [35][5] de real

laboratorios : matriz [35][5] de real

Note que, en ambas matrices, cada fila guarda las notas de un estudiante del curso.

• Si se quiere guardar las letras que conforman una sopa de letras, como aquellas que vienen en los pasatiempos, se puede declarar la siguiente matriz.

sopa : matriz [10][15] de caracter

Note que la sopa de letras más grande que se puede guardar es de 10 filas por 15 columnas.

Los índices se crearon para permitir que el programador se pueda referir, de forma específica y directa, a una cualquiera de las casillas de la matriz, tanto para guardar un dato en esa casilla, como para obtener el dato almacenado en ella. En el seudolenguaje, para referirse a una casilla particular de una matriz se debe seguir el siguiente formato:

<NOMBRE>[<INDICE-DE-FILA>][<INDICE-DE-COLUMNA>]

Es decir, se debe escribir el nombre de la matriz seguido por el índice de fila y por el índice de columna, ambos entre paréntesis cuadrados, de la casilla que se quiere consultar.

Ejemplo completo

Una matriz mágica es una matriz cuadrada (tiene igual número de filas que de columnas) que tiene como propiedad especial que la suma de las filas, las columnas y las diagonales es igual. Por ejemplo:

2 7 6

9 5 1

4 3 8

En esta matriz las sumas son 15.

Considere el problema de construir un algoritmo que compruebe si una matriz de datos es mágica o no, y en caso de que sea mágica escribir la suma. El usuario ingresa el tamaño de la matriz máximo hasta 10. Además debe guardar la suma de las filas, las columnas y las diagonales en un arreglo en el orden siguiente:



Las entradas (datos conocidos) para el algoritmo son:

􀂾 La dimensión de la matriz.
􀂾 Los números que contiene la matriz.

La salida esperada (datos desconocidos) es:

􀂾 La matriz es mágica o no, y si es mágica cuál es el valor de la suma.

En este problema, los arreglos son útiles para guardar los datos que conforman la matriz.
Los números que contiene la matriz se pueden guardar en una variable entera.

La siguiente gráfica resume las entradas y salidas del algoritmo que se pretende diseñar.
Además bautizan todas las variables mencionadas.

Las condiciones iniciales y finales se pueden expresar mediante las cláusulas REQUIERE y GARANTIZA:

REQUIERE:

La dimensión de la matriz que debe ser máximo 10x10
Cada elemento de la matriz debe ser un número entero.

GARANTIZA:

Muestra en pantalla si es mágica o no, y si lo es cual es el valor de la suma.
Una primera versión del algoritmo puede ser la siguiente:

Inicio
Paso 1: Leer el tamaño de la matriz
Paso 2: Leer los elementos de la matriz
Paso 3: Determinar si la matriz es mágica o no
Paso 4: Si la matriz es mágica mostrar el valor de la suma.
Fin

Los pasos 1 y 2 son interacciones con el usuario que permiten capturar los datos de entrada. La versión inicial se puede refinar detallando estos pasos y además defiendo las variables para hacerlos:

Procedimiento principal

variables
i, j, aux, tam, suma: enteros //i señala las filas
//j señala las columnas
magica: matriz [10][10] de enteros
Inicio
escribir(“Por favor digite el número de filas de la matriz (entre 2 y 10): ”)
leer(tam)

para (i=0 hasta tam-1) hacer
para(j=0 hasta tam-1) hacer
escribir(“Por favor digite el dato en la posición”)
escribir(i,j)

leer(magica[i][j])

fin_para
fin_para
Paso 3

Paso 4

Se puede observar que el primer ciclo para tiene como contador la variable i, esto indica que se llenará la matriz por filas, el segundo ciclo para que tiene como contador la variable j, recorrerá la fila columna a columna para ubicar allí el dato correspondiente.

La parte nuclear de la solución es el paso 3. En este problema en particular se sabe que el número de filas y de columnas es igual y que hay dos diagonales. Para el ejemplo mostrado al inicio sería 3 filas, 3 columnas y dos diagonales. Para almacenar las sumas en un arreglo este tendrá una dimensión de 2*tam+2. La     declaración del arreglo sumas es:

sumas: arreglo [22] de enteros


Ahora para calcular las sumas se puede hacer lo siguiente:

Paso 3.1: Inicializar el arreglo de sumas en cero.
Paso 3.2: Sumar fila por fila, columna por columna y las diagonales y guardar su valor en el arreglo.

para(i=0 hasta 2*tam+2) hacer
sumas[i]:=0
fin_para

//Sumas correspondientes a las filas

para(i=0 hasta tam-1) hacer
         para(j=0 hasta tam-1) hacer
         sumas[i]=magica[i][j]+sumas[i]
fin_para

fin_para

//Sumas correspondientes a las columnas

para(j=0 hasta tam-1) hacer
para(i=0 hasta tam-1) hacer
sumas[j+tam]=magica[i][j]+sumas[j+tam]
fin_para

fin_para

//Sumas correspondientes a las diagonales

para(i=0 hasta tam-1) hacer
sumas[2*tam]=magica[i][i]+sumas[2*tam]
fin_para
para(i=0 hasta tam-1) hacer
sumas[2*tam+1]=magica[i][(tam-1)-i]+sumas[2*tam+1];
fin_para