VECTORES Y MATRICES

NOCIN DE VECTOR

Nueva estructura de objeto, frecuentemente utilizada en informtica y a la que

se aplican numerosos tratamientos iterativos. Por ejemplo, supongamos una empresa
con 40 sucursales y que deseamos calcular el total de rentas.

El procedimiento a seguir sera ir sumando cada elemento del vector.

a) Total Venta(1) + Venta(2) + Venta(3) + ... + Venta(40)

De esta forma se define el vector en algortmica a travs de un n ndice que va a

indicar el elemento del vector con el cual estamos haciendo operaciones.

b) VENTA (I) I [1..40]

TOTAL 0 Variable donde vamos a almacenar la sumatoria.

Para I de 1 hasta 40 hacer
TOTAL TOTAL + VENTA(I)
Fin para

Definicin de Vector:

Conjunto ordenado que contiene un n fijo de elementos (su dimensin) de

cualquier tipo vlido definido con la condicin de que todos deben ser del mismo tipo.

Forma de declarar un vector:

Vector tipo nombre [ndice mnimo .. ndice mximo]

Ejemplo: Para el ejemplo anterior la declaracin del vector quedara de esta forma:

vector entero venta [1..40]

1.- OPERACIONES CON VECTORES

31
Asignacin

En general, los lenguajes de programacin incluyen como muchas instrucciones de

lectura/escritura de vectores completos, siendo muy pocos la que tienen definidas otras
operaciones primitivas con el vector tomado como dato nico.

La estructura de control asociada de manera natural con los vectores es la estructura de

tipo "PARA"

Ejemplo:

Algoritmo Inicializar_Vector

Vector de reales V [1 .. 100]

Para i de 1 hasta 100 hacer
V(i) 0.0
Fin para

Final

En algunos lenguajes se permite la asignacin directa entre vectores de igual

dimensin y tipo.

La condicin principal para poder realizar este tipo de asignaciones es que

debe cumplirse que los dos vectores sean del mismo tipo y de la misma longitud.

u v el vector 'u' pasa a contener los datos de 'v'

Otra forma de hacer esta asignacin es a travs de la asignacin de elemento en

elemento. Este tipo de asignacin es la que se realiza de forma comn en
programacin, y la que utilizaremos en nuestros algoritmos.

Para i de 1 hasta n hacer

u(i) v(j)
Fin para

De este modo veamos un ejemplo: Tenemos dos vectores con las mismas
caractersticas (tipo y longitud). Se pretende intercambiar los datos entre dos vectores
a b. Para ello utilizaremos un elemento de apoyo c.

32
 Algoritmo Intercambio de vectores
Variables enteras i, n, c
Vectores de enteros a [1..100], b[1..100]
Escribir Introduzca el nmero de elementos de los vectores
Leer n
- Para i de 1 a n
Escribir Introduzca el elemento a[,i,]
Leer a[i]
Escribir Introduzca el elemento b[,i,]
Leer b[i]
- Fin_Para
- Para i de 1 a n
c a[i] Obsrvese como se realiza el proceso de
a [i] b[i] intercambio. Necesitamos la variable de
b [i] c apoyo para no perder por sobrescritura los datos de un vector.
- Fin_Para
- Para i de 1 a n
Escribir a[,i,]=,a[i]
Escribir b[,i,]=,b[i]
- Fin_Para

Final

1.1.- NECESIDAD DEL PREDIMENSIONAMIENTO POR EXCESO

Es muy importante entender que la zona de declaracin de variables de un

algoritmo SIEMPRE SE EJECUTA ANTES QUE LAS SENTENCIAS DEL MISMO. Debido
a esto, ES IMPOSIBLE COLOCAR UNA VARIABLE COMO DIMENSION DE UN
VECTOR O MATRIZ. Por ello, siempre que pretendamos manipular un nmero de datos
escogido por el usuario, tendremos que recurrir a un predimensionamiento por exceso,
considerando un tamao superior al que ste escoger. Habitualmente se puede poner
100 como dimensin por defecto, salvo casos en los que se vea claro que sean
necesarios ms elementos.

2.- LECTURA Y ESCRITURA

Como hemos visto anteriormente, en algortmica podemos utilizar la

asignacin de forma directa o por medio de la asignacin de los elementos. De igual
forma a la hora de leer podemos utilizar la lectura directa o lectura por elementos.

Ejemplo de lectura / escritura por elementos:

Para i de 1 a n hacer
Leer v(i)
Fin para

Para i de 1 a n hacer
33
 Escribir v(i)
Fin para

Finalmente, decir que aunque por facilitar la comprensin de los ejemplos aqu
mostrados, se obviarn las operaciones de lectura y escritura realizndolas en forma
directa, los algoritmos de examen SIEMPRE debern indicarse estas operaciones
desarrolladas, es decir, por elementos.

3.- OPERACIONES ELEMENTALES CON VECTORES NUMRICOS

Suma de vectores

Algoritmo suma_vectores
Constante n= ... Forma de resolver el problema del
Variable entera i predimensionamiento por exceso
Vectores reales a[1..n], b[1..n], c[1..n]
Leer a,b LECTURA DIRECTA, NO USAR!
Para i de 1 a n hacer
c(i) a(i)+b(i)
Fin para
Escribir c ESCRITURA DIRECTA, NO USAR!
Final

Los vectores que se suman han de ser del mismo tipo y dimensin.

Producto por un escalar

Algoritmo producto por escalar
Constante n= ...
Variable real x
entera i
vectores reales a(1..n),b(1..n)
Leer a
Leer x
Para i de 1 a n hacer
b(i) x*a(i)
Fin para
Escribir b
Final

Producto escalar de dos vectores

Algoritmo producto escalar

constante n= ...
variable entera i
real c
vectores reales a(1..n), b(1..n)
Leer a,b
c 0.0
34
 Para i de 1 a n hacer
c c+a(i)*b(i)
Fin para
Escribir c
Final

Mdulo de un vector

Algoritmo modulo
constante n= ...
variable entera i
real modulo, suma_cuadrados
vector real a (1..n)
Leer a
suma_cuadrados 0.0
Para i de 1 a n hacer
suma_cuadrados suma_cuadrados + a(i)*a(i)
Fin para
modulo sqr (suma_cuadrados)
Escribir mdulo
Final

4.4.- IDENTIFICACIN DE POLINOMIOS CON VECTORES

Sea un polinomio de grado n:

P( x ) Pn x x Pn 1 x n 1
... P1 x P0

Pude representarse mediante un vector donde sus elementos son los coeficientes
del polinomio.

vector real P(0..n)

Suma de polinomios

Algoritmo suma_polinomios
constante n=...
vectores reales p(0..n),q(0..n),r(0..n)
variable entera i

Leer p,q
Para i de 1 a n hacer
r(i) p(i) + q(i)
Fin para
Escribir r
35
 Final

Evaluacin de un polinomio

Regla de Ruffini: valor p(x) para x=a . Se basa en dividir el polinomio p[0..n] por (x-a),
obteniendo el polinomio cociente, q[0..n-1]

qn-1 = pn
qn-2 = pn-1 +a qn-1
...
q0 = p1 + aq1
r = p0 + aq0

Veamos ahora el algoritmo.

Algoritmo Ruffini
constante n=...
Variable real a
entera i
Vectores reales p(0..n), q(0..n-1)

Leer p
Leer a
q(n-1) p(n)
Para i de n-1 a 1 incremento -1 hacer
q(i-1) p(i) + a*q(i)
Fin para
r p(0)+a*q(0)
Escribir Polinomio cociente = q
Escribir Resto (valor de p(a) = , r

Final

5.- ORDENACION Y BUSQUEDA

Veamos en este apartado las operaciones comunes en el tratamiento de

vectores.

Ordenacin por seleccin

36
 Supongamos un vector, donde parte de sus elementos estn ordenados y
otros no. Los pasos a seguir para realizar la ordenacin son los siguientes:

r n t d a h m z o k s c
a1 a2 ... ak-1 ak ... ... ... ai ... ... an

Elementos desordenados

a) Para realizar la ordenacin por seleccin se hacen varios barridos del

vector. Primeramente cogemos el primer elemento del vector y lo
comparamos con todos los elementos restantes buscando aquel elemento que
posea el valor ms pequeo.

r n t d a h m z o k s c
a1 a2 ... ak-1 ak ... ... ... ai ... ... an

b) Una vez encontrado el elemento menor, se coloca en la posicin

correspondiente, realizando un intercambio de posiciones entre el elemento
que hemos comparado y el que hemos encontrado.

a n t d r h m z o k s c
a1 a2 ... ak-1 ak ... ... ... ai ... ... an

c) Una vez ordenado el primer elemento, realizamos la misma operacin con

los restantes. Finalmente el vector quedar ordenado.

a c d h k m n o r s t z
a1 a2 ... ak-1 ak ... ... ... ai ... ... an

El algoritmo de ordenacin por seleccin es el siguiente.

37
 Algoritmo Seleccin
constante n=...
variable entera i,j,k
real x variable de apoyo
vector de reales a(1..n)

Leer a

Para i de 1 a n-1 hacer el ultimo 'n' ya estar ordenado.

k i k es el ndice del elemento menor a permutar
con a[i], inicialmente lo ponemos igual que i
Para j de i+1 a n hacer
si a(j) < a(k) entones
k j Si aparece un elemento de menor valor, fijamos
Finsi k a su ndice
Fin para

x a(i) Permutamos a[i] con a[k]

a(i) a(k)
a(k) x
Fin para

Escribir a
Final

Ejercicio Propuesto: Realizar la traza para la ordenacin por seleccin del vector
a=(75,63,8,15,26,12,2)

Bsqueda Lineal

Dado un vector que suponemos desordenado, localizar un elemento que tenga

un valor determinado requerir un barrido a lo largo del mismo hasta encontrar dicho
elemento.

Algoritmo bsqueda_lineal
constante n= ...
variable entera i
real x
38
 vector de reales a(1..n)

Leer a
Leer x
y 1

mientras (a(i) x and i n) hacer

i i+1
fin mientras

si i n entonces
escribir ("Dato ";x;" Encontrado en la posicin: ";i)
sino escribir ("Dato no encontrado")
finsi

Final

Bsqueda Binaria

Si el vector est ordenado, existen mtodos de bsqueda mas eficientes. Uno

de ellos es el de la bsqueda dicotmica. Veamos un ejemplo donde el vector est
ordenado de forma ascendente (menor -> mayor).

Algoritmo Busqueda_Dicotmica
constante n=...
variable entera i,j,m
real x

39
 vector a(1..n)

Leer a
Leer x
i 1
j n

repetir
m (i+j)/2
si x < a(m) entonces
j m-1
finsi
si x > a(m) entonces
i m+1
finsi
hasta que (a(m)=x or i>j)

si a(m) = x entonces
escribir ("Dato ";x;" Encontrado en la posicin: ";m)
sino escribir ("Dato no encontrado")
finsi

Final

6.- MATRICES.

Podemos extender el concepto de vector a estructuras con dos ndices, es decir,

matrices.

De forma anloga a la utilizacin de un bucle, normalmente de tipo "para",en el

tratamiento de los elementos de un vector para el caso de una matriz, lgicamente,
se requerirn dos bucles compuestos.

Al igual que en el caso de vectores, todos los elementos de una matriz deben ser
del mismo tipo. Declaracin:

40
 Matriz tipo nombre (ndice fila mn..ndice fila mx, ndice col mn..ndice col mx)

Los conceptos de vector y matriz no son sino casos particulares de una

estructura general de "p" dimensiones que denominaremos tabla.

7.- OPERACIONES CON MATRICES.

Asignacin.

Por ejemplo: inicializacin a cero :

para i de 1 a m hacer
para j de 1 a n hacer
a(i,j) 0.0
fin para
fin para

Definicin de matriz identidad

para i de 1 a n hacer
para j de 1 a n hacer
si i=j entonces
I(i,j) 1
sino I(i,j) 0
finsi
fin para
fin para

Asignacin de valores introducidos por el usuario:

para i de 1 a m hacer
para j de 1 a n hacer
leer a(i,j)
fin para
fin para

41
 Al igual que con los vectores, a efectos de simplificar los algoritmos de ejemplo,
expresaremos en ocasiones la lectura y escritura de forma abreviada (NO PERMITIDO
EL EJERCICIOS DE EXAMEN):

leer a
escribir a

8.- OPERACIONES ELEMENTALES CON MATRICES NUMRICAS. SUMA DE

MATRICES.

Algoritmo suma de matrices

constantes m=..., n=...
variables enteras i, j
matrices reales a(1..m,1..n), b(1..m,1..n), c(1..m,1..n)
leer a, b
para j de 1 a m hacer
para j de 1 a n hacer
c(i,j) a(i,j) + b(i,j)
fin para
fin para

escribir c
Final

Ejercicio Propuesto: Hallar la traza para: a(2,3,-1,4,5,10) y b(1,7,6,18,-3,27)

Evidentemente, las matrices han de ser del mismo tipo y deben tener las mismas
dimensiones.

Producto de una matriz por un escalar

Algoritmo producto por un escalar

constantes m=..., n=...
variables enteras i, j
variable real x
matrices reales a(1..m,1..n), b(1..m,1..n)

leer a
leer x

para i de 1 a m hacer
para j de 1 a n hacer
b(i,j) x * a(i,j)
fin para
fin para

42
 escribir b
Final

Producto matricial

Algoritmo producto matricial

constantes m=..., n=..., q=...
variables enteras i, j, k
matrices reales a(1..m,1..n), b(1..n,1..q), c(1..m,1..q)

leer a, b
para i de 1 a m hacer
para j de 1 a q hacer
c(i,j) 0.0
para k de 1 a n hacer
c(i,j) c(i,j) + a(i,k)*b(k,j)
fin para
fin para
fin para

escribir c
Final

Ejercicios Propuestos

1.- Dado un vector "a" de n componentes reales, formular un algoritmo para determinar
los componentes mximo y mnimo.

2.- Escribir un algoritmo para obtener la traspuesta de una matriz A(m,n).

3.- Obtener un algoritmo que lea un conjunto de n datos reales, los almacene en un
vector "a" y determine:

a.- El recorrido, r = max(aj) - min(aj)

n
1
b.- El valor medio: a ai
n i 1

n
1
c.- La desviacin tpica: (ai a) 2
n i 1

43
 d.- El coeficiente de variacin:
a

4.- Modificar el algoritmo de ordenacin por seleccin, de forma que opcionalmente la

ordenacin pueda ser ascendente o descendente.

5.- Sean dos matrices de dimensiones m,n y l,k. Disear un un algoritmo que detecte
aquellos elementos presentes en ambas matrices y los escriba, indicando su
posicin en las dos matrices (suponiendo que no hay valores repetidos dentro de
ninguna de las dos matrices).

6.- Dado un vector de n elementos enteros desordenado, escribir un algoritmo que

detecte aquellos elementos que estn repetidos, escribiendo el elemento y el nmero de
veces que se repite.

44