VECTORES Y MATRICES NOCIÓN DE VECTOR Nueva estructura de
objeto, frecuentemente utilizada en informática 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 sería ir
sumando cada elemento del vector. a) Total Venta(1) + Venta(2) +
Venta(3) + … + Venta(40) De esta forma se define el vector en
algorítmica a través de un nº índice
que va a indicar el elemento del vector con el cual estamos
haciendo operaciones. b) VENTA (I) TOTAL I [1..40] 0 Variable
donde vamos a almacenar la sumatoria. Para I de 1 hasta 40 hacer
TOTAL TOTAL + VENTA(I) Fin para Definición de Vector:
Conjunto ordenado que contiene un nº fijo de elementos (su
dimensión) de cualquier tipo válido definido con la
condición de que todos deben ser del mismo tipo. Forma de
declarar un vector: Vector tipo nombre [índice
mínimo .. índice máximo] Ejemplo: Para el
ejemplo anterior la declaración del vector quedaría
de esta forma: vector entero venta [1..40] 1.- OPERACIONES CON
VECTORES 31
a Asignación En general, los lenguajes de
programación 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 asignación directa entre
vectores de igual dimensión y tipo. La condición
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 asignación es a través
de la asignación de elemento en elemento. Este tipo de
asignación es la que se realiza de forma común en
programación, 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
características (tipo y longitud). Se pretende
intercambiar los datos entre dos vectores 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 número 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] b [i] a[i] b[i] c Obsérvese como se realiza el
proceso de intercambio. Necesitamos la variable de 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 declaración 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 número de datos escogido por
el usuario, tendremos que recurrir a un predimensionamiento por
exceso, considerando un tamaño superior al que éste
escogerá. Habitualmente se puede poner 100 como
dimensión por defecto, salvo casos en los que se vea claro
que sean necesarios más elementos. 2.- LECTURA Y ESCRITURA
Como hemos visto anteriormente, en algorítmica podemos
utilizar la asignación de forma directa o por medio de la
asignación 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 comprensión de los ejemplos aquí mostrados, se
“obviarán” las operaciones de lectura y
escritura realizándolas en forma directa, los algoritmos
de examen SIEMPRE deberán indicarse estas operaciones
desarrolladas, es decir, por elementos. 3.- OPERACIONES
ELEMENTALES CON VECTORES NUMÉRICOS Suma de vectores
Algoritmo suma_vectores Constante n= … Variable entera i Forma
de resolver el problema del predimensionamiento por exceso
Vectores reales a[1..n], b[1..n], c[1..n] Leer a,b Para i de 1 a
n hacer LECTURA DIRECTA, NO USAR! c(i) Fin para Escribir c
a(i)+b(i) ESCRITURA DIRECTA, NO USAR! Final Los vectores que se
suman han de ser del mismo tipo y dimensión. 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 34 c 0.0
1 Para i de 1 a n hacer c c+a(i)*b(i) Fin para Escribir c Final
Módulo de un vector Algoritmo modulo constante n= …
variable entera i real modulo, suma_cuadrados vector real a
(1..n) Leer a suma_cuadrados Para i de 1 a n hacer suma_cuadrados
Fin para 0.0 suma_cuadrados + a(i)*a(i) modulo sqr
(suma_cuadrados) Escribir módulo Final 4.4.-
IDENTIFICACIÓN DE POLINOMIOS CON VECTORES Sea un polinomio
de grado n: P( x) Pn x x Pn 1 x n … 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
r las Final Evaluación 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 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 operaciones comunes
en el tratamiento de vectores. Ordenación por
selección 36
y Supongamos un vector, donde parte de sus elementos están
ordenados y otros no. Los pasos a seguir para realizar la
ordenación son los siguientes: r a1 n a2 t … d ak-1 a ak
h … m … z … o ai k … s … c an Elementos desordenados a)
Para realizar la ordenación por selección se hacen
varios barridos del vector. Primeramente cogemos el primer
elemento del vector lo comparamos con todos los elementos
restantes buscando aquel elemento que posea el valor más
pequeño. r a1 n a2 t … d ak-1 a ak h … m … z … o
ai k … s … c an b) Una vez encontrado el elemento menor, se
coloca en la posición correspondiente, realizando un
intercambio de posiciones entre el elemento que hemos comparado y
el que hemos encontrado. a a1 n a2 t … d ak-1 r ak h … m …
z … o ai k … s … c an c) Una vez ordenado el primer
elemento, realizamos la misma operación con los restantes.
Finalmente el vector quedará ordenado. a a1 c a2 d … h
ak-1 k ak m … n … o … r ai s … t … z an El algoritmo de
ordenación por selección es el siguiente. 37
Algoritmo Selección 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 Finsi Fin para j Si aparece un
elemento de menor valor, fijamos “k” a su
índice x a(i) a(k) a(i) a(k) x Permutamos a[i] con a[k]
Fin para Escribir a Final Ejercicio Propuesto: Realizar la traza
para la ordenación por selección del vector
a=(75,63,8,15,26,12,2) Búsqueda 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 búsqueda_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 posición: ";i) sino escribir ("Dato no
encontrado") finsi Final Búsqueda Binaria Si el vector
está ordenado, existen métodos de búsqueda
mas eficientes. Uno de ellos es el de la búsqueda
dicotómica. Veamos un ejemplo donde el vector está
ordenado de forma ascendente (menor -> mayor). Algoritmo
Busqueda_Dicotómica constante n=… variable entera i,j,m
real x 39
vector a(1..n) Leer a Leer x i j 1 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 posición: ";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 análoga a la utilización
de un bucle, normalmente de tipo "para",en el tratamiento de los
elementos de un vector para el caso de una matriz,
lógicamente, se requerirán dos bucles compuestos.
Al igual que en el caso de vectores, todos los elementos de una
matriz deben ser del mismo tipo. Declaración: 40
Matriz tipo nombre (índice fila mín..índice
fila máx, índice col mín..índice col
máx) Los conceptos de vector y matriz no son sino casos
estructura general de "p" dimensiones que denominaremos tabla.
7.- OPERACIONES CON MATRICES. Asignación. Por ejemplo:
inicialización a cero : para i de 1 a m hacer para j de 1
a n hacer particulares de una a(i,j) 0.0 fin para fin para
Definición de matriz identidad para i de 1 a n hacer para
j de 1 a n hacer si i=j entonces I(i,j) sino I(i,j) 1 0 finsi fin
para fin para Asignación 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
x 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 NUMÉRICAS. 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) fin para fin para
escribir c Final a(i,j) + b(i,j) 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 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 42
b(i,j) fin para fin para x * a(i,j)
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 máximo y mínimo. 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) b.- El valor medio: a 1 n n i 1 ai c.- La
desviación típica: 1 n n i 1 (ai a) 2 43
a en d.- El coeficiente de variación: 4.- Modificar el
algoritmo de ordenación por selección, de forma que
opcionalmente la ordenación pueda ser ascendente o
descendente. 5.- Sean dos matrices de dimensiones m,n y l,k.
Diseñar un un algoritmo que detecte aquellos elementos
presentes ambas matrices y los escriba, indicando su
posición 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 están
repetidos, escribiendo el elemento y el número de veces
que se repite. 44