introduccion a la programacion con matlab 46 ejercicios resueltos con varias soluciones todas...

Introducción a la programación con MATLAB

46 ejercicios resueltos con varias soluciones, todas claramente explicadas

Macario Polo Usaola Profesor Titular de Lenguajes y Sistemas Informáticos en la

Universidad de Castilla-‐La Mancha

1

© Macario Polo Usaola, 2012

[email protected]

1

ÍNDICE DE EJERCICIOS

Ejercicio 1. Factorial iterativo ........................................................................................................ 1

Ejercicio 2. Número combinatorio ............................................................................................... 7

Ejercicio 3. ex por Taylor .................................................................................................................. 9

Ejercicio 4. seno(x) por Taylor .................................................................................................... 13

Ejercicio 5. Factorial recursivo ................................................................................................... 14

Ejercicio 6. Fibonacci ...................................................................................................................... 16

Ejercicio 7. La divina proporción ............................................................................................... 19

Ejercicio 8. Conversión de entero a binario .......................................................................... 20

Ejercicio 9. Contador de apariciones ....................................................................................... 25

Ejercicio 10. Producto escalar .................................................................................................... 28

Ejercicio 11. Fibonacci en un vector ........................................................................................ 31

Ejercicio 12. Distancia al primero ............................................................................................. 33

Ejercicio 13. Números primos .................................................................................................... 41

Ejercicio 14. Vector con los n primeros números primos ............................................... 44

Ejercicio 15. Vector con los n primeros números primos ordenados de mayor a menor 46

Ejercicio 16. Calcular el enésimo número primo ................................................................ 48

Ejercicio 17. Contar números distintos en un vector ....................................................... 49

Ejercicio 18. Descomposición en factores primos (I) ....................................................... 50

Ejercicio 19. Descomposición en factores primos (II) ...................................................... 52

Ejercicio 20. Máximo común divisor ........................................................................................ 54

Ejercicio 21. Tablero de ajedrez ................................................................................................. 56

Ejercicio 22. Alfil ............................................................................................................................... 57

Ejercicio 23. El caballo de ajedrez ............................................................................................. 61

Ejercicio 24. Matriz identidad ..................................................................................................... 68

Ejercicio 25. Diagonal principal ................................................................................................. 70

Ejercicio 26. Traza de una matriz .............................................................................................. 73

Ejercicio 27. Unos y ceros alternados ...................................................................................... 75

Macario Polo Usaola

2

Ejercicio 28. Matriz de Vandermonde ..................................................................................... 81

Ejercicio 29. Matriz de Fibonacci ............................................................................................... 83

Ejercicio 30. Producto de matrices. .......................................................................................... 85

Ejercicio 31. Triángulo de Tartaglia ......................................................................................... 87

Ejercicio 32. Triángulo equilátero ............................................................................................. 90

Ejercicio 33. Matriz triangular superior ................................................................................. 95

Ejercicio 34. Diagonales que se incrementan (I) ................................................................ 99

Ejercicio 35. Diagonales que se incrementan (II) ............................................................. 102

Ejercicio 36. Números ordenados ........................................................................................... 103

Ejercicio 37. Números ordenados descendentemente .................................................. 105

Ejercicio 38. Zigzag ........................................................................................................................ 106

Ejercicio 39. Distancias ................................................................................................................ 107

Ejercicio 40. Distancia en letras ............................................................................................... 111

Ejercicio 41. Buscador de cadenas .......................................................................................... 113

Ejercicio 42. Detección de palíndromos ............................................................................... 115

Ejercicio 43. El monte ................................................................................................................... 124

Ejercicio 44. Cálculo de pi (π) ................................................................................................... 129

Ejercicio 45. La salida del laberinto ....................................................................................... 133

Ejercicio 46. Búsqueda binaria ................................................................................................. 137

46 ejercicios resueltos de MATLAB

1

Ejercicio 1. Factorial iterativo

Realizar una función que, recibiendo como argumento de entrada un número entero n, devuelva el factorial de dicho número.

Si no se recibiese ningún argumento de entrada se deberá devolver un -‐1 y mostrar un mensaje de aviso por pantalla. Si n fuera menor que cero se deberá devolver también un -‐1 y mostrar un mensaje de aviso por pantalla. Si n no fuera entero se deberá redondear hacia +∞ .

El factorial de un número natural n es el producto de todos los números naturales desde 1 hasta ese número n. El factorial de 5, por ejemplo, es 1·2·3·4·5=120. Además, el factorial de 0 es 1. La función factorial se representa con una admiración: n!=n·(n-‐1)·…3·2·1.

• Solución 1.

En una primera solución supondremos que el número que se pasa como argumento a la función es natural y positivo. Para computar el resultado necesitamos únicamente un bucle for que vaya desde 1 hasta n de 1 en 1 (Función 1): a la función la hemos llamado factorial1 y toma un argumento1 n.

function result = factorial1( n ) result=1; for i=1:1:n result=result*i; end end Función 1. Un factorial sencillo, sin comprobación de parámetros y con un for que incrementa

El bucle for i=1:1:n inicializa la variable contador i a 1 y la va incrementando de 1 en 1 hasta n (el valor del argumento pasado). En el cuerpo del bucle se utiliza una variable acumuladora result (puede llamarse de cualquier manera, pero utilizaremos habitualmente result para hacer referencia al resultado que debe devolver la función) en la que iremos guardando el resultado de calcular el valor anterior de result multiplicado por el valor de i. Con objeto de que result vaya almacenando correctamente los valores, es necesario inicializarla a 1 antes de empezar el bucle.

La Tabla 1 muestra una traza de ejecución de la función cuando pasamos 5 como valor del parámetro n: al entrar a la función, ni result ni i tienen valor, y lo único que está definido es el parámetro n. En la asignación result=1 que hay antes del bucle, result toma el valor 1 pero i sigue sin estar definida. Al entrar al bucle por primera vez, result sigue valiendo 1 e i toma ya valor 1.

1 argumento y parámetro significan lo mismo. Utilizaremos ambas palabras indistintamente.

Macario Polo Usaola

2

En la segunda vuelta al bucle, i se ha incrementado en 1, con lo que vale 2, y a result le asignamos el valor que tenía (1) multiplicado por el valor de i: la aparición de la palabra result en el lado derecho de la instrucción result=result*i hace referencia al valor actual de result; la aparición de result en el lado izquierdo hace referencia al valor que le vamos a asignar.

Se continúa de esta manera, haciendo ese cómputo, hasta que i alcance el valor 5, que es el valor de n que pasamos como parámetro y que es la condición de parada en el bucle for: for i=1:1:n

Comentarios n result i Al entrar a la función 5 Al ejecutar result=1 5 1 La primera vez que entramos al bucle 5 result=result*i

result=1*1=1 1

Segunda vuelta al bucle 5 result=result*i result=1*2=2

2

5 result=2*3=6 3 5 result=6*4=24 4 5 result=24*5=120 5

Tabla 1

Si ejecutamos la función desde la línea de comando, obtenemos esto:

>> factorial1(5) ans = 120 Figura 1

La palabra ans que escribe MATLAB es la answer (la respuesta) al cálculo que le hemos solicitado. Muestra un 120 porque, en la cabecera de la función asignábamos a result el resultado de la función, y precisamente es result la variable en la que vamos, iteración a iteración, almacenando el resultado que deseamos.

function result = factorial1( n )

• Solución 2.

Otra forma de implementar exactamente lo mismo es utilizar también un bucle for, pero que vaya desde n hasta 1, de -‐1 en -‐1. Observa (Función 2) que el bucle for ha cambiado:

function result = factorial2( n ) result=1; for i=n:-1:1 result=result*i; end end Función 2. Un factorial sencillo, sin comprobación de parámetros y con un for que decrementa


3

• Solución 3.

En el enunciado del problema nos piden que, si no pasamos ningún argumento, se muestre un mensaje de aviso por pantalla. Ahora mismo se muestra el mensaje de error por defecto de MATLAB, que es bastante feo:

>> factorial2() ??? Input argument "n" is undefined. Error in ==> factorial2 at 3 for i=n:-‐1:1 Figura 2

Modificaremos ligeramente la función para que se compruebe que se pasan argumentos y que, en caso de que no sea así, se muestre un mensaje de error personalizado, la función devuelva 1 y el programa termine: en la Función 3 hemos añadido unas líneas de código en las que usamos la palabra reservada nargin (que indica el número de valores pasados a la función como parámetros) para comprobar que, si es 0, el resultado de la función sea -‐1 (nos lo pide el enunciado), se muestre un mensaje de error (uso de la función disp de MATLAB) y el programa termine (uso de return).

function result = factorial2( n ) if (nargin==0) result=-1; disp('Debes dar un argumento a la función'); return; end result=1; for i=n:-1:1 result=result*i; end end Función 3. El factorial con comprobación del número de parámetros

Ahora, el resultado de llamar a la función sin argumentos es:

>> factorial2() Debes dar un argumento a la función ans = -‐1 Figura 3

• Solución 4.

El enunciado también nos dice que, si n es menor que cero, se dé un mensaje de aviso y se devuelva también -‐1. Una forma de hacerlo es añadir otro if después del if que ya añadimos a la Función 3, de manera que el código quede como en la Función 4:

Macario Polo Usaola

4

function result = factorial2( n ) if (nargin==0) result=-1; disp('Debes dar un argumento a la función'); return; end if (n<0) result=-1; disp('El parámetro debe ser positivo'); return; end result=1; for i=n:-1:1 result=result*i; end end Función 4

Si intentamos calcular, por ejemplo, el factorial de -‐5, se muestra la siguiente respuesta:

>> factorial2(-‐5) El parámetro debe ser positivo ans = -‐1 Figura 4

• Solución 5.

Otra forma de conseguir lo mismo que en la solución anterior es colocar las dos comprobaciones (existencia de un argumento y que éste sea positivo) en un solo if: en la Función 5 unimos ambas condiciones con un or (símbolo |, la barra vertical), de manera que si el número de argumentos es 0 o n es menor que cero, la función devuelva -‐1, se muestre un mensaje de error y se termine el cálculo.


5

function result = factorial2( n ) if (nargin==0 | n<0) result=-1; disp('Debes dar un argumento positivo a la función'); return; end result=1; for i=n:-1:1 result=result*i; end end Función 5

• Solución 6.

Nos piden en el enunciado, por último, que si n no fuera entero se redondee hacia +∞: es decir, si queremos calcular el factorial de 7.85, devolveremos el factorial de 8.

Una vez comprobado que hay un argumento positivo, utilizaremos la función ceil(x) de MATLAB: si x tiene decimales, ceil(x) redondea el valor de x hacia el entero superior más próximo; si no los tiene, deja el valor de x como está.

function result = factorial2( n ) if (nargin==0 | n<0) result=-1; disp('Debes dar un argumento positivo a la funciÛn'); return; end n=ceil(n); result=1; for i=n:-1:1 result=result*i; end end Función 6

Ahora, la función se comporta correctamente:

Macario Polo Usaola

6

>> factorial2(4.5) ans = 120 >> factorial(5) ans = 120 Figura 5


7

Ejercicio 2. Número combinatorio

Escribir una función que calcule el número combinatorio !! , sabiendo que

n>=m, !! = !! = ! y que !! = !!

!!· !!! !. Los valores de n y m serán

argumentos de entrada y el resultado del cálculo se devolverá como argumento de salida.

• Solución 1.

Escribiremos primero una solución algo larga, pero en la que se realiza todo el cálculo: en los primeros tres if (marcados en amarillo) hacemos una comprobación de los argumentos. En el siguiente comprobamos si m es 0 o si n==m, con lo que debemos devolver 1 como resultado.

En los siguientes tres bloques calculamos los factoriales de n, m y de n-‐m usando tres bucles for como los que ya utilizamos en la primera solución a la función factorial (página 1). Estos factoriales los guardamos en tres variables llamadas factorialN, factorialM y factorialNmenosM. Finalmente, asignamos a la variable de resultado (result) el cálculo solicitado.

function result = numeroCombinatorio1( n, m ) if (nargin~=2) disp('Se necesitan dos argumentos'); return; end if (n<0 | m<0) disp('Los argumentos deben ser positivos'); return; end if (n<m) disp('n debe ser mayor o igual que m'); return; end if (n==m | m==0) result=1; return; end factorialN=1; for i=1:1:n factorialN=factorialN*i; end factorialM=1; for i=1:1:m factorialM=factorialM*i; end factorialNmenosM=1; for i=1:1:(n-m) factorialNmenosM=factorialNmenosM*i;

Macario Polo Usaola

8

end result=factorialN/(factorialM*factorialNmenosM); end Función 7

• Solución 2.

En una solución menos complicada podemos utilizar cualquiera de las funciones factorial que escribimos como soluciones del ejercicio 1. Basta con escribir una nueva función en la que las llamamos:

function result = numeroCombinatorio2( n, m ) result=factorial1(n)/(factorial1(m)*factorial1(n-m)) end Función 8

• Solución 3.

En las dos soluciones anteriores repetimos cálculos. Supongamos que nos piden calcular !"! : calculamos primero factorialN=10·9·8·7·6·5·4·3·2·1 y luego computamos factorialM=5·4·3·2·1, con lo que estamos repitiendo parte del cálculo del factorialN.

Si debiéramos hacer este cálculo a mano, probablemente calcularíamos primero el factorial de m y luego, al calcular el de n, nos detendríamos al llegar al valor de m. Es decir, que factorialN=10·9·8·7·6·factorialM. Esto es lo que hacemos en esta solución (Función 9), que requiere menos tiempo de cómputo: en la primera línea se calcula el factorial de m; luego, en el bucle for resaltado en amarillo, vamos guardando en factorialN el valor de multiplicar i desde n hasta el valor de m+1. En la instrucción siguiente, multiplicamos el valor de factorialN por el valor de factorialM que hemos calculado antes, de manera que nos ahorramos unas cuantas vueltas de bucle. Finalmente calculamos (n-‐m)! por el método tradicional y calculamos el resultado final del número combinatorio. Se han omitido las comprobaciones de argumentos para facilitar la lectura del código.

function result = numeroCombinatorio3( n, m ) factorialM=factorial1(m); factorialN=1; for i=n:-1:m+1 factorialN=factorialN*i; end factorialN=factorialN*factorialM; factorialNmenosM=factorial1(n-m); result=factorialN/(factorialM*factorialNmenosM); end Función 9


9

Ejercicio 3. ex por Taylor

Realizar una función que recibiendo como argumento de entrada un número real x devuelva el valor de la exponencial de dicho número, que deberá calcularse mediante su serie de Taylor truncada en n de tal forma que el error absoluto entre la serie en el término n-‐1 y n sea menor de 10-‐7. La serie de Taylor de la exponencial viene dada por la expresión:

!! =!!

!! ,∀!!

!!!

• Solución 1.

Antes de implementar la función es conveniente plantear un ejemplo para ver cómo podemos abordar la solución. Al programar funciones de cálculo, en muchos casos, debemos intentar imitar nuestro propio razonamiento.

Supongamos que deseamos calcular e5 (cuyo valor es 148,4131591025764) mediante la aproximación de Taylor:

!! =!!

!! =!!

!! +!

!!!

!!

!! +!!

!! +!!

!! +⋯

Pararemos cuando la diferencia entre el término n-‐1 y el n sea menor que 0.0000001.

Para una primera solución no tendremos en cuenta esta consideración del error absoluto, y lo que haremos será iterar, por ejemplo, 100 veces. Es decir:

!! =!!

!! =!!

!! +!""

!!!

!!

!! +!!

!! +!!

!! +⋯+!!!

!!! +!!""

!""!

Una forma de implementar esta solución es la siguiente:

function result = exponencialPorTaylor1( x ) result=0; for n=0:1:100 result=result+(x^n)/factorial(n); end end Función 10

El resultado de calcular exponencialPorTaylor1(5) es:

>> exponencialPorTaylor1(5) ans = 148.4132 Figura 6

Macario Polo Usaola

10

• Solución 2.

Podemos escribir una solución parecida a la anterior, pero utilizando un while en lugar de un for. Diremos entonces que mientras n (que es la variable contador del bucle) sea menor o igual a 100, realice el cálculo:

function result = exponencialPorTaylor2( x ) result=0; n=0; while (n<=100) result=result+(x^n)/factorial(n); n=n+1; end end Función 11

• Solución 3.

Con objeto de ir acercándonos a lo que nos pide el enunciado, vamos a modificar ligeramente el código anterior para que la función nos muestre la diferencia entre el valor calculado para n y para n-‐1. Más adelante, en otra solución, utilizaremos este valor (el error absoluto) como condición de parada para devolver el resultado solicitado.

En la Función 12 hemos añadido unas líneas al código anterior: ya que necesitamos comparar, en cada iteración del bucle, el resultado que se acabe de calcular con el anterior, creamos antes del while una variable ultimoResultado a la que asignamos el valor infinito (función Inf() de MATLAB). Luego, en cada vuelta del bucle, asignamos a una variable error la diferencia entre el último resultado calculado (almacenado en la variable ultimoResultado que hemos creado ex profeso para esto) y el resultado que se acaba de calcular. Mostramos el error por la consola (disp(error)) y, por último, actualizamos el valor de ultimoResultado al valor que se acaba de calcular.

function result = exponencialPorTaylor3( x ) result=0; n=0; ultimoResultado=Inf(); while (n<=24) result=result+(x^n)/factorial(n); error=ultimoResultado-result; ultimoResultado=result; disp(error); n=n+1; end end Función 12

Si ejecutamos exponencialPorTaylo3(5), MATLAB muestra lo siguiente:

>>exponencialPorTaylor3(5)


11

Inf -‐5 -‐12.5 -‐20.8333333333333 -‐26.0416666666667 -‐26.0416666666667 -‐21.7013888888889 -‐15.5009920634921 -‐9.68812003968253 -‐5.38228891093473 -‐2.69114445546737 -‐1.2232474797579 -‐0.509686449899135 -‐0.196033249961204 -‐0.070011874986136 -‐0.0233372916620453 -‐0.00729290364438384 -‐0.00214497166010119 -‐0.000595825461147115 -‐0.000156796173996554 -‐3.91990434991385e-‐05 -‐9.33310559503298e-‐06 -‐2.12116034958854e-‐06 -‐4.61121828720934e-‐07 -‐9.60670547556219e-‐08 0 0 ... 0 ans= 148.413159078837 Figura 7

La larga lista de números que muestra (hemos omitido bastantes ceros al final) se corresponde con los valores de error calculados en cada iteración del bucle while.

• Solución 4.

Para cumplir con el enunciado, el cómputo debe detenerse en el momento en que el valor absoluto del error sea menor que 10-‐7. Como lo vamos calculando en cada vuelta del bucle, basta con que modifiquemos la condición de parada del while para que, en lugar de dar 100 vueltas fijas, esté dando vueltas mientras el valor absoluto de error sea mayor o igual a 10-‐7. Es decir, que modificamos el código para que quede como sigue:

Macario Polo Usaola

12

function result = exponencialPorTaylor4( x ) result=0; error=Inf(); ultimoResultado=Inf(); n=0; while (abs(error)>=10e-7) result=result+(x^n)/factorial(n); error=ultimoResultado-result; ultimoResultado=result; n=n+1; end end Función 13


13

Ejercicio 4. seno(x) por Taylor

Escribir una función que recibiendo como argumento de entrada un número real x devuelva el seno de dicho número, que deberá calcularse mediante su serie de Taylor truncada en n de tal forma que el error absoluto entre la serie en el término n-‐1 y n sea menor de 10e-‐7. La serie de Taylor del seno viene dada por la expresión:

!"#$ ! =(−!)!

!"+ ! !!!"!!,∀!

!

!!!

• Solución 1.

La solución a este ejercicio es muy parecida a la del anterior: ya que no sabemos exactamente cuántas iteraciones debemos hacer, sino sólo la condición de parada, lo haremos, como antes, con un bucle while. La condición de parada será la misma, y la forma de cálculo también muy similar. Cambiará únicamente la fórmula de asignación del resultado.

function result = senoTaylor(x) result=0; error=Inf(); resultAnterior=Inf(); n=0; while (abs(error)>=10e-7) result=result+((-1)^n/factorial(2*n+1))*(x^(2*n+1)); error=abs(result-resultAnterior); n=n+1; resultAnterior=result; end end Función 14

Macario Polo Usaola

14

Ejercicio 5. Factorial recursivo

Escribir una función que calcule el factorial de manera recursiva.

• Solución 1.

Una función recursiva es una función que, en su implementación, contiene una llamada a sí misma. La función factorial se describe recursivamente de forma muy natural, ya que:

n!=n·(n-‐1)!

Es decir, el factorial de n es n multiplicado por el factorial de n-‐1. En efecto, 5!=5·4·3·2·1 o, lo que es lo mismo, 5!=5·4!, ya que 4!=4·3·2·1.

En las funciones debe haber siempre, al menos, un caso base, que haga que las sucesivas llamadas a la función se detengan. En el caso del factorial, el caso base se alcanza cuando n=0, ya que 0!=1.

En la Función 15 preguntamos que si el argumento que se está pasando es 0: en caso afirmativo, asignamos a result el valor 1 y la llamada a la función termina; en caso negativo, asignamos a result el resultado de multiplicar n por el factorial de n-‐1, tal y como hacíamos arriba al escribir n!=n·(n-‐1)!

function result = factorialRecursivo( n ) if (n==0) result=1; return else result=n*factorialRecursivo(n-1); return end end Función 15

Supongamos que deseamos calcular recursivamente el factorial de 5. La siguiente tabla muestra una traza de lo que va sucediendo al escribir en la línea de comando de MATLAB factorialRecursivo(5):

Comentarios n result 1ª llamada a la función. Se ejecuta factorialRecursivo(5)

5

Como n no es 0, se entra al else 5 result=5*factorialRecursivo(4) 2ª llamada. Se ejecuta factorialRecursivo(4). n toma ahora el valor 4

4

Como n no es 0, se entra al else 4 result=4* factorialRecursivo(3) 3ª llamada. Se ejecuta factorialRecursivo(3). n entra valiendo 3

3


15

Comentarios n result Como n no es 0, se entra al else 3 result=3* factorialRecursivo(2) 4ª llamada. Se ejecuta factorialRecursivo(2). El valor de n es 2

2

Como n no es 0, se entra al else 2 result=2*factorialRecursivo(1) 5ª llamada. Se ejecuta factorialRecursivo(1). n llega valiendo 1

1

Como n no es 0, se entra al else 1 result=1*factorialRecursivo(0) 6ª llamada. Se ejecuta factorialRecursivo(0). n vale 0

0

n es ahora 0, por lo que es cierta la condición del if (n==0)

0 result=1

En este punto se ha alcanzado el caso base, por lo que no hay más llamadas recursivas. Ahora, el valor calculado en la 6ª llamada se utiliza para calcular el valor

de la 5ª llamada, que a su vez se utiliza para calcular el de la 4ª, etcétera. Regreso a la 5ª llamada. 1 result=1*factorialRecursivo(0)=1*1=1 Regreso a la 4ª llamada. 2 result=2*factorialRecursivo(1)=1*2=1 Regreso a la 3ª llamada. 3 result=3*factorialRecursivo(2)=3*2=6 Regreso a la 2ª llamada. 4 result=4*factorialRecursivo(3)=4*6=24 Regreso a la 1ª llamada. 5 result=5*factorialRecursivo(5)=5*24=120 Tabla 2

Macario Polo Usaola

16

Ejercicio 6. Fibonacci

Escribir una función que calcule el término n de la función de Fibonacci, que viene dada por: x1=1; x2 = 1; xi=xi-‐1+xi-‐2

• Solución 1.

Puesto que ya sabemos un poco de recursividad, es fácil observar que la función de Fibonacci se describe muy bien de forma recursiva:

fibonacci(1)=1

fibonacci(2)=1

fibonacci(n)=fibonacci(n-‐1) + fibonacci(n-‐2), si n>2

Observamos que hay dos casos base: uno con n=0 y otro con n=1. En estos dos casos, el valor de la función es 1. El código puede ser el siguiente:

function result=fib(n) if (n==1) result=1; elseif (n==2) result=1; else result=fib(n-1)+fib(n-2); end end Función 16. Fibonacci recursivo con dos casos base

• Solución 2.

Obsérvense en el código anterior los dos casos base, marcados en amarillo. Realmente, podemos agruparlos en uno solo:

function result=fib2(n) if (n<=2) result=1; else result=fib(n-1)+fib(n-2); end end Función 17. Fibonacci recursivo con un caso base

• Solución 3.

Cualquiera de las dos soluciones que hemos dado arriba es muy costosa en términos del número de sumas que es necesario realizar. Para calcular a mano, por ejemplo, fib(8), hacemos lo siguiente:

fib(8)=fib(7)+fib(6)=


17

= [fib(6)+fib(5)] + [fib(5)+fib(4)] =

= { [fib(5)+fib(4)] + [fib(4)+fib(3)] } + { [fib(4)+fib(3)] + [fib(2)+fib(1)] } = …

El mismo cómputo, que resulta complicado escribirlo en forma de ecuación, se puede representar de forma arborescente: nótese que hay cálculos que se repiten varias veces, y obsérvese que el caso base se alcanza en total 21 veces, correspondientes a los 21 unos que hay en el árbol, y que fibonacci(8)=21.

Figura 8. Árbol correspondiente al cálculo tradicional de Fibonacci(8)

Por ello, es conveniente utilizar, si es posible, algoritmos más rápidos. Una versión menos compleja computacionalmente hablando, y que además no utiliza recursividad, es la siguiente:

function result=fib3(n) i=1; j=0; for k=1:1:n t=i+j; i=j; j=t; end result=j; end Función 18. Versión iterativa de la función de Fibonacci

• Solución 4.

Podemos comparar el tiempo dedicado por el ordenador a realizar un determinado cómputo mediante las funciones de MATLAB tic (que pone el cronómetro a cero) y toc (que lo detiene). En la siguiente figura reproducimos el código de la Función 17 y de la Función 18, pero con las instrucciones tic y toc.

Macario Polo Usaola

18

function result=fib2(n) tic; if (n<=2) result=1; else result=fib2(n-1)+fib2(n-2); end toc; end

function result=fib3(n) tic; i=1; j=0; for k=1:1:n t=i+j; i=j; j=t; end result=j; toc; end

Función 19. La versión recursiva (izquierda) y la iterativa (derecha) para calcular Fibonacci, anotadas con instrucciones para calcular el tiempo

El resultado de ambas funciones para calcular fibonacci(20) es:

>> fib2(20) Elapsed time is 0.000119 seconds. ans = 6765

>> fib3(20) Elapsed time is 0.000005 seconds. ans = 6765

• Solución 5.

Si investigamos un poquito, averiguaremos que el término n de la función Fibonacci se corresponde también con el siguiente valor:

!"# ! =!! − (1− !)!

5

…en donde:

! =1+ 52

Así, otra implementación de la función, mucho más rápida que cualquiera de las anteriores, ya que no requiere ni recursividad ni bucles, es la dada en la Función 20: primero se calcula el valor de Φ, y luego calculamos y devolvemos el resultado.

function result=fib4(n) fi=(1+sqrt(5))/2; result=(fi^n-(1-fi)^n)/sqrt(5); end Función 20


19

Ejercicio 7. La divina proporción

Se pide realizar una función que recibiendo como argumento de entrada un número entero positivo n devuelva el valor de la aproximación de la divina proporción para el término n de la serie de Fibonacci. La divina proporción es la división del término i de la serie de Fibonacci entre el anterior.

• Solución 1.

Habiendo ya implementado la función de Fibonacci, la resolución de este ejercicio es muy sencilla. La fórmula de cálculo es:

divinaProporción(n)=fibonacci(n)/fibonacci(n-‐1)

Podemos hacer uso de cualquiera las implementaciones que hemos dado a la función de Fibonacci en el ejercicio anterior, no siendo necesario reescribirla:

function result = divinaProporcion( n ) result=fib4(n)/fib4(n-1); end Función 21

Macario Polo Usaola

20

Ejercicio 8. Conversión de entero a binario

Escribir una función de MATLAB que, recibiendo como argumento de entrada un número entero, n, represente por pantalla su equivalente en el sistema binario. Si el número es negativo, se deberá escribir el correspondiente signo menos antes del número. Si el número no es entero, se mostrará un mensaje de error.

• Solución 1.

Antes de programar, veamos cómo hacemos a mano una conversión de entero a binario. Supongamos que queremos pasar a binario el número 15: lo que hacemos es ir dividiendo sucesivamente entre 2 hasta que el cociente obtenido sea 1. Luego, para construir la representación en base 2, recorremos desde el último cociente obtenido (1), y subiendo por todos los restos:

De este modo, obtenemos que 152=1111.

De igual manera podemos calcular el 29 en base 2:

Así, 292=11101.

Por tanto, utilizaremos un bucle para ir dividiendo el número que obtengamos entre 2, mientras que el cociente sea mayor o igual a 2. Además, deberemos ir memorizando los restos que vayamos obteniendo.

Una primera aproximación a la solución es la siguiente (Función 22):


21

function result = pasarABinario( n ) cociente=n; resto=mod(cociente, 2); result=[resto]; while (cociente>=2) cociente=floor(cociente/2); resto=mod(cociente, 2); result=[resto result]; end end Función 22. Primera aproximación para la conversión a binario

El código de la Función 22 tiene una novedad respecto de las funciones que hemos escrito hasta ahora: a la variable result le asignamos, en las líneas resaltadas, valores entre corchetes. Con los corchetes indicamos que la variable es un vector. En la primera sentencia (result=[resto]), guardamos en result un vector con un solo elemento, el resto que se ha calculado. En la segunda (result=[resto result]) añadimos al comienzo del vector result el valor que hemos calculado del resto en esta iteración.

Usamos, además, la función mod en la primera asignación al resto: resto=mod(cociente, 2). mod(x,y) devuelve el resto de la división entera de x entre y. Igualmente, usamos la función floor, que redondea un número decimal al entero inmediatamente inferior.

Hagamos una traza de la función con n=12:

Comentarios n cociente resto result Llamada a la función 12 Ejecución de cociente=n 12 12 Ejecución de resto=mod(cociente, 2) 12 12 0 Ejecución de result=[resto] 12 12 0 [ 0 ] Entramos al bucle, ya que cociente>=2

12 12 0 [ 0 ]

cociente=floor(cociente/2) 12 6 0 [ 0 ] resto=mod(cociente, 2) 12 6 0 [ 0 ] result=[resto result] 12 6 0 [ 0 0 ] Segunda vuelta al bucle 12 6 0 [ 0 0] cociente=floor(cociente/2) 12 3 0 [ 0 ] resto=mod(cociente, 2) 12 3 1 [ 0 ] result=[resto result] 12 3 1 [ 1 0 0 ] Tercera vuelta al bucle 12 3 1 [ 1 0 0 ] cociente=floor(cociente/2) 12 1 1 [ 0 ] resto=mod(cociente, 2) 12 1 1 [ 0 ] result=[resto result] 12 1 1 [ 1 1 0 0 ]

Y en este momento se sale del bucle, ya que cociente=1, que es menor que 2 Tabla 3. Traza de pasarABinario(12)

Macario Polo Usaola

22

Si en la consola de MATLAB ejecutamos pasarABinario(12), se nos muestra lo siguiente:

>> pasarABinario(12) ans = 1 1 0 0 Figura 9

El resultado que nos está devolviendo MATLAB no es un número entero ni natural, sino un vector con cuatro valores.

• Solución 2.

En el enunciado del problema se nos dice que “Si el número es negativo, se deberá escribir el correspondiente signo menos antes del número”.

Como sabemos, el primer dígito del número binario es el primer resto que calculamos. Lo que haremos será preguntar, después del bucle, si el número que nos pasaron como parámetro es negativo: en caso afirmativo, modificaremos el primer elemento del vector multiplicándolo por -‐1; en caso negativo, lo dejamos como está. Inicialmente, podríamos dejar esto de la siguiente manera:

function result = pasarABinario2( n ) cociente=n; resto=mod(cociente, 2); result=[resto]; while (cociente>=2) cociente=floor(cociente/2); resto=mod(cociente, 2); result=[resto result]; end if (n<0) result(1)=-1*result(1); end end Función 23. La función de paso a binario con soporte para negativos, pero con un pequeño error

En las líneas en amarillo preguntamos que, si n<0, entonces el primer elemento del vector sea sustituido por su valor multiplicado por -‐1. Al ejecutar, como ejemplo, pasarABinario(-‐12), esperaríamos la respuesta -‐1100; sin embargo, MATLAB nos responde, sorprendentemente, de la siguiente forma:


23

>> pasarABinario2(-‐12) ans = 0 Figura 10

El error lo encontramos en la primera sentencia de la función, que necesita ser modificada: si n=-‐12, entonces por la asignación que hay a continuación se hace cociente=-‐12 y no se entra en el while, ya que no se verifica la condición. Debemos asignar, en la primera instrucción, el valor abs(n) a cociente. Es decir:

function result = pasarABinario2( n ) cociente=abs(n); resto=mod(cociente, 2); result=[resto]; while (cociente>=2) cociente=floor(cociente/2); resto=mod(cociente, 2); result=[resto result]; end if (n<0) result(1)=-1*result(1); end end Figura 11. La función de paso a binario con soporte para negativos, ahora corregida

• Solución 3.

En el enunciado también se nos dice que, si el número que se pasa como parámetro no es entero, se debe dar un mensaje de error. Una forma de comprobar esto es preguntar si el parámetro n es igual a la parte entera del propio n, es decir:

Macario Polo Usaola

24

function result = pasarABinario3( n ) if (n~=floor(n)) error('Se esperaba un entero'); return; end cociente=abs(n); resto=mod(cociente, 2); result=[resto]; while (cociente>=2) cociente=floor(cociente/2); resto=mod(cociente, 2); result=[resto result]; end if (n<0) result(1)=-1*result(1); end end Función 24


25

Ejercicio 9. Contador de apariciones

Escribir una función de MATLAB que tome como entradas un vector de números enteros v y un número entero n, y que devuelva el número de veces que n está contenido en el vector v.

• Solución 1.

Igual que en otras ocasiones, veamos cómo haríamos esto a mano. Supongamos que tenemos el vector v= {1 2 1 3 4 1 2 5 6 4 1}, y que deseamos contar las apariciones de n=1.

Posición 1 2 3 4 5 6 7 8 9 10 11 Valor 1 2 1 3 4 1 2 5 6 4 1

A mano, leeríamos el valor de la posición 1; como es 1, almacenamos 1 en un contador; pasamos a la posición 2 y, como no es 1, dejamos el contador como está; pasamos a la posición 3 y, como contiene un 1, incrementamos en uno el contador, que ya vale 2; llegamos sin cambiar hasta la posición 6, en la que hacemos que contador sea 3, y seguimos hasta el final del vector, la posición 11, en la que incrementamos el contador hasta 4.

Una implementación de esta solución es la siguiente (Función 25): utilizamos como contador la variable result; luego recorremos todas las posiciones del vector con un bucle for que va desde 1 hasta su longitud (length(vector)). En el cuerpo del bucle tomamos en la variable vi el valor i-‐ésimo del vector, lo comparamos con n y, si es igual, incrementamos el resultado.

function result = problema8ContadorB( vector, n ) result=0; for i=1:1:length(vector) vi=vector(i); if (vector(i)==n); result=result+1; end end end Función 25. Una primera versión de la función para contar el número de apariciones

Para ejecutar la función con el vector dado como ejemplo y para que busque el valor 1, escribimos en el área de comandos de MATLAB dos instrucciones: primero, una para asignar a una variable x el vector; luego, la llamada a la función que hemos escrito.

Macario Polo Usaola

26

>> x=[ 1 2 1 3 4 1 2 5 6 4 1] x = 1 2 1 3 4 1 2 5 6 4 1 >> problema8ContadorB(x, 1) ans = 4 Figura 12

• Solución 2.

MATLAB dispone de muchas funciones muy cómodas para trabajar con vectores y matrices. Dado el vector anterior, podemos escribir en la línea de comandos lo siguiente:

>> x==2 ans = 0 1 0 0 0 0 1 0 0 0 0 Figura 13

Lo que le estamos diciendo a MATLAB con x==2 es que me muestre qué valores del vector x son iguales a 2 y cuáles no. Como respuesta, MATLAB devuelve otro vector con unos y ceros: en aquellas posiciones en las que el vector tiene valor 2, MATLAB pone un 1, y un 0 en las que no. De este modo, aparece el valor 1 en las posiciones 2 y 7, ya que x contiene un 2 en esas dos posiciones.

Posición 1 2 3 4 5 6 7 8 9 10 11 x= 1 2 1 3 4 1 2 5 6 4 1

¿x==2? 0 1 0 0 0 0 1 0 0 0 0

Otra función interesante de MATLAB es la función sum: aplicada a un vector, devuelve la suma de sus elementos. Por ejemplo, la suma de los valores de x es 30:

>> sum(x) ans = 30 Figura 14

Bien, pues podemos combinar ambas funciones para calcular muy rápida y sencillamente el número de apariciones de un elemento en un vector: si calculamos la suma del vector de unos y ceros, ya sabremos cuántas veces aparece el número solicitado:


27

function result = problema8ContadorA( vector, n ) result=sum(vector==n); end Función 26. Otra versión, mucho más eficaz

En efecto, lo que decimos en la sentencia de asignación de la Función 26 es que asigne a result el resultado de sumar los elementos del vector de unos y ceros construido a partir de la comparación del vector pasado como parámetro con el valor de n.

Posición 1 2 3 4 5 6 7 8 9 10 11 x= 1 2 1 3 4 1 2 5 6 4 1

¿x==2? 0 1 0 0 0 0 1 0 0 0 0 La suma de los elementos en amarillo es 2.

Y sí, funciona:

>> problema8ContadorA(x, 2) ans = 2 Figura 15

Macario Polo Usaola

28

Ejercicio 10. Producto escalar

Escribir una función que calcule el producto escalar de dos vectores v y w que se pasan como parámetros. Si no se recibiesen dos argumentos de entrada se deberá mostrar un mensaje de error por pantalla y devolver un -‐1. Si las dimensiones de los vectores fueran incoherentes para realizar el producto escalar se deberá devolver un -‐1 y mostrar también un mensaje de error.

• Solución 1.

El producto escalar de dos vectores se calcula de la siguiente forma:

! · ! = !1, !2,… !" ·!1!2…!"

= !1 · !1+ !2 ∗ !2+⋯+ !" · !"

Si lo calculamos a mano, consiste en ir acumulando la suma de multiplicar el primero por el primero, más el segundo por el segundo, más el tercero por el tercero, etcétera.

Para escribir la función MATLAB correspondiente, basta con un bucle for que recorra desde 1 hasta n (donde n es la longitud de los vectores) y que acumule en una variable la suma de los productos. Es decir:

function result = productoEscalar(v, w) result=0; for i=1:1:length(v) result=result+v(i)*w(i); end end Función 27. Función para el cálculo del producto escalar

• Solución 2.

En el enunciado nos piden que hagamos varias comprobaciones de argumentos: que haya 2 y que las dimensiones de ambos vectores sean coherentes. En el primer if del siguiente código comprobamos que se pasan exactamente dos argumentos; en el segundo, que las longitudes de ambos vectores sean iguales.


29

function result = productoEscalar2(v, w) if (nargin~=2) disp('Debe pasar dos argumentos'); return; end if (length(v)~=length(w)) disp('Los vectores deben tener el mismo número de elementos'); return; end result=0; for i=1:1:length(v) result=result+v(i)*w(i); end end Función 28. Producto escalar con comprobación de argumentos

• Solución 3.

Desde luego, podemos utilizar también los propios operadores de MATLAB para multiplicar matrices y vectores y hacer la cosa mucho más sencilla.

En la siguiente figura mostramos el uso del operador * para multiplicar dos vectores:

§ En (1), mostramos el valor del vector x. § En (2), asignamos a y el mismo vector x, de manera que ya tenemos dos

vectores. § En (3), utilizamos el operador ‘ para pedirle a MATLAB que nos muestre el

vector y traspuesto. § En (4), intentamos multiplicar x por y. MATLAB da un error porque los

vectores deben tener dimensiones compatibles: 1xn y nx1. § En (5) arreglamos el problema, multiplicando x por el traspuesto de y.

>> x x = 1 2 1 3 4 1 2 5 6 4 1

>> y=x y = 1 2 1 3 4 1 2 5 6 4 1

>> y' ans = 1 2 1 3 4 1 2 5 6 4 1

>> x*y ??? Error using ==> mtimes Inner matrix dimensions must agree.

>> x*y' ans = 114

Figura 16. Cálculo del producto escalar, directamente en la línea de comandos de MATLAB

1 2

3 4

5

Macario Polo Usaola

30

En realidad, no nos hace falta entonces crear ninguna función en MATLAB para calcular el producto escalar de dos vectores. No obstante, si deseamos hacerlo:

function result = productoEscalar3(v, w) if (nargin~=2) disp('Debe pasar dos argumentos'); return; end if (length(v)~=length(w)) disp('Los vectores deben tener el mismo número de elementos'); return; end result=v*w'; end Función 29


31

Ejercicio 11. Fibonacci en un vector

Escribir una función de MATLAB que construya un vector que contenga los n primeros términos de la serie de Fibonacci, donde n es un parámetro que se pasará como argumento de entrada.

• Solución 1.

En la Función 30 damos una primera solución: primero asignamos a fib (la variable que, en este caso y por variar, utilizamos para devolver el resultado) un vector de tantos ceros como valor tenga el parámetro n. Para ello usamos la función zeros(x) de MATLAB, que construye un vector con x ceros.

Luego, colocamos sendos unos en la primera y segunda posiciones. A continuación, recorremos el vector desde la posición 3 hasta el final, colocando en cada una la suma de las dos posiciones anteriores.

function fib=vectorFibonacci(n) fib=zeros(1, n) fib(1) = 1; fib(2) = 1; for i = 3 : n fib(i) = fib(i-1) + fib(i-2); end end Función 30

El resultado es el siguiente:

>> vectorFibonacci(8) ans = 1 1 2 3 5 8 13 21 Figura 17

• Solución 2.

También podemos utilizar cualquiera de las funciones para el cálculo de la función de Fibonacci que vimos en ejercicios anteriores. Por ejemplo:

function fib=vectorFibonacci2(n) fib=[]; for i = 1 : n fib=[fib fib2(i)]; end end Función 31

En el código anterior hay dos novedades: la primera en la sentencia fib=[], que construye un vector vacío; la segunda en el bucle for, que tiene solamente los

Macario Polo Usaola

32

valores inicial y final de i, y no el incremento que debe darse a esta variable en cada vuelta del bucle. Cuando el incremento no se pone, MATLAB asume que es 1.


33

Ejercicio 12. Distancia al primero

Escriba una función de MATLAB que reciba un vector de números reales, v, como argumento de entrada y determine cuál de todos ellos es el más cercano al primero de los elementos del vector y devuelva su posición, p, dentro del vector.

Ejemplo: para v = (2, 6, 4, 1, 10) , p = 4, ya que el número más cercano al primero (2) es el cuarto (1).

Si no se proporciona un vector de entrada se generará un vector de tamaño 10 de números aleatorios reales entre 0 y 10. En caso de que el vector no tenga al menos dos componentes, el método devolverá un -‐1.

• Solución 1.

Primero de todo, ¿cómo lo haríamos a mano? Supongamos que tenemos el vector que nos proponen en el enunciado:

Posición 1 2 3 4 5 v= 2 6 4 1 10

En un procedimiento manual, probablemente leeríamos y memorizaríamos el primer número; luego, leeríamos el segundo, calcularíamos la diferencia (en valor absoluto, por si hubiera negativos) y, puesto que de momento es el más cercano (la diferencia es 4), guardaríamos su posición (2) como resultado. A continuación leeríamos el tercero (un 4), calcularíamos la diferencia respecto del primero (4-‐2=2) y, como es menor que el resultado que llevamos hasta el momento (4), almacenamos la posición (3) y actualizamos el resultado. Seguiríamos así hasta la última posición del vector.

Bien, pues esto es exactamente lo que hacemos en la Función 32: en p devolveremos el resultado, que inicializamos a -‐1. En mejorDistancia guardamos la distancia o diferencia más corta hasta el momento, que inicializamos a infinito. Luego, en el bucle, recorremos el vector desde la segunda posición hasta el final. En cada iteración calculamos la distancia desde el elemento en el que estamos (v(i)) hasta el primero (v(1)). Si es menor que la mejorDistancia hasta el momento, actualizamos p (con la posición de este elemento) y el valor de mejorDistancia.

function p = distanciaAlPrimero(v) p=-1; mejorDistancia=Inf(); for i=2:length(v) distancia=abs(v(i)-v(1)); if (distancia<mejorDistancia) p=i; mejorDistancia=distancia; end end end Función 32

Macario Polo Usaola

34

Con el vector de ejemplo, el resultado es:

>> x=[2 6 4 1 10] x = 2 6 4 1 10 >> distanciaAlPrimero(x) ans = 4 Figura 18

• Solución 2.

El enunciado nos pide que, si no se proporciona un vector de entrada, se genere uno con 10 números aleatorios reales entre 0 y 10. Si se pasa un vector como entrada pero no tiene al menos dos elementos, debe devolverse un -‐1.

La segunda comprobación es sencilla, pues basta utilizar la función length(v). Para la segunda contaremos el número de argumentos con nargin: si es 0, generaremos un vector de 10 números aleatorios entre 0 y 10.

MATLAB dispone de la función rand, que genera un número al azar entre 0 y 1:

>> rand ans = 0.435119497879152

>> rand ans = 0.017483539523425

>> rand ans = 0.446709873639582

>> rand ans = 0.918297137138448

Figura 19

Si deseamos generar un número al azar entre 0 y 10, basta con escribir rand*10.

Por otro lado, si queremos generar una matriz de nxm números aleatorios, escribiríamos rand(n, m). Por ejemplo, a continuación generamos una matriz de 4x3:


35

>> rand(4,3) ans = 0.887620611199764 0.561801676019808 0.674758140355275 0.17367398659238 0.107561794984856 0.373326492462255 0.379791754484912 0.446083836222534 0.30283659962261 0.405999530454979 0.99179953529122 0.673265764196007 Figura 20

Si lo que queremos es generar un vector de 10 números, el comando es rand(1, 10), que es el que usaremos en la nueva versión de nuestra función: en amarillo indicamos que, si el número de argumentos es 0, entonces v (el vector sobre el que vamos a trabajar) debe inicializarse como nos piden en el enunciado. En el segundo if preguntamos por la longitud del vector, que también se nos pedía.

function p = distanciaAlPrimero(v) if (nargin==0) v=rand(1,10)*10; end if (length(v)<=2) p=-1; return; end p=-1; mejorDistancia=Inf(); for i=2:length(v) distancia=abs(v(i)-v(1)); if (distancia<mejorDistancia) p=i; mejorDistancia=distancia; end end end Función 33

• Solución 3.

Una solución más elegante pasa por utilizar las funciones de MATLAB para manipulación de vectores y matrices. Supongamos que disponemos del siguiente vector, en el que hay algunos elementos repetidos:

posición 1 2 3 4 5 6 7 8 9 10 x= 1 2 3 1 4 8 -‐1 6 7 1

Si escribimos x en la consola de MATLAB, sabemos que nos muestra los elementos del vector. Si escribimos (por ejemplo) x-‐5, MATLAB nos muestra como resultado un vector en el que ha restado 5 a todos los elementos del vector original, x. Es decir:

Macario Polo Usaola

36

>> x-‐5 ans = -‐4 -‐3 -‐2 -‐4 -‐1 3 -‐6 1 2 -‐4 Figura 21

Para irnos aproximando a la solución del ejercicio, podemos pedirle a MATLAB que nos muestre el resultado de restar a todos los elementos de x el primer elemento del vector:

>> x-‐x(1) ans = 0 1 2 0 3 7 -‐2 5 6 0 Figura 22

O, mejor aún, su valor absoluto:

>> abs(x-‐x(1)) ans = 0 1 2 0 3 7 2 5 6 0 Figura 23

A partir del resultado mostrado en la figura anterior, sabemos que el valor de la posición que debe devolvernos la función que buscamos es un 4, que es la ubicación del segundo cero: el que está en la primera posición no nos interesa, porque es el elemento con el que hacemos todas las comparaciones.

Nos interesa, entonces, trabajar con el vector x, pero quitándole el primer elemento. Afortunadamente, MATLAB permite extraer cómodamente un trozo de un vector: en la Figura 24, le decimos a MATLAB que vaya al vector x, que se fije en su fila 1 (la única que tiene, pues se trata de un vector y no de una matriz) y que, de ella extraiga los elementos que hay desde la posición 2 hasta la última (length(x)):

>> x(1, 2:length(x)) ans = 2 3 1 4 8 -‐1 6 7 1 Figura 24

Ahora podemos medirle a MATLAB que, al vector obtenido en la Figura 24, le reste el valor que tenemos en la posición 1 del vector x:


37

>> x(1, 2:length(x))-‐x(1) ans = 1 2 0 3 7 -‐2 5 6 0 Figura 25

El elemento que buscamos es el que está en la tercera posición de este vector resultante, que es realmente el cuarto del vector original. Tendremos esto en cuenta para más adelante.

Otra función interesante de MATLAB es min(v), que devuelve el valor mínimo del vector que se pasa como parámetro:

>> x x = 1 2 3 1 4 8 -‐1 6 7 1 >> min(x) ans = -‐1 Figura 26

Realmente, nos interesa conocer el valor mínimo del vector que construimos en la Figura 25, en el que no estábamos considerando el primer elemento:

>> x(1, 2:length(x))-‐x(1) ans = 1 2 0 3 7 -‐2 5 6 0 >> min(x(1, 2:length(x))-‐x(1)) ans = -‐2 Figura 27

Si seleccionamos el menor valor, escogeríamos el -‐2, que está en la sexta posición del vector (séptima en el vector original). Esta elección sería errónea, pues el valor más próximo al primero es el 0. Modifiquemos la expresión de la Figura 27 para que considere el valor absoluto:

Macario Polo Usaola

38

>> min(abs(x(1, 2:length(x))-‐x(1))) ans = 0 Figura 28

Ahora sí, en la figura anterior tenemos localizado el menor valor del vector que procede de calcular el valor absoluto de restar a los elementos 2º a último de x el valor x(1).

El vector original, x, era este:

posición 1 2 3 4 5 6 7 8 9 10 x= 1 2 3 1 4 8 -‐1 6 7 1

Las transformaciones que hemos ido haciendo para adaptarlo a nuestras necesidades han sido:

posición — 1 2 3 4 5 6 7 8 9 x(1, 2:length(x)= — 2 3 1 4 8 -‐1 6 7 1

x(1, 2:length(x))-‐x(1)= — 1 2 0 3 7 -‐2 5 6 0 abs(x(1, 2:length(x))-‐x(1)) — 1 2 0 3 7 2 5 6 0

Ahora necesitamos encontrar en qué posición se encuentra el menor valor del vector abs(x(1, 2:length(x))-‐x(1)). Para encontrar valores en un vector, MATLAB dispone de la función find, que devuelve un vector con las posiciones de los elementos que cumplen cierta condición. En la figura siguiente buscamos todas las apariciones del valor 1 en el vector x: nos dice que el valor 1 aparece en las posiciones 1, 4 y 10. Este resultado (1, 4, 10) es devuelto en forma de vector.

>> x x = 1 2 3 1 4 8 -‐1 6 7 1 >> find(x==1) ans = 1 4 10 Figura 29

Hasta ahora, sabemos extraer un subvector haciendo alguna transformación al vector original (como en el caso de abs(x(1, 2:length(x))-‐x(1))) y calcular el mínimo de un vector. Bien, pues busquemos en el vector abs(x(1, 2:length(x))-‐x(1)) las posiciones en las que aparece el valor mínimo: en la Figura 30, le estamos diciendo a MATLAB que busque, en el vector abs(x(1, 2:length(x))-‐x(1)), su valor mínimo. MATLAB responde diciendo que el valor mínimo está en las posiciones 3 y 9.


39

>> find(abs(x(1, 2:length(x))-‐x(1))==min(abs(x(1, 2:length(x))-‐x(1)))) ans = 3 9 Figura 30

Nos interesa realmente quedarnos sólo con el primer elemento. Como el resultado devuelto por find es un vector, extraemos el primer elemento: primero, asignamos a una variable auxiliar, a la que llamamos z, el vector que contiene las posiciones del valor mínimo; luego, leemos el primer elemento de ese vector z.

>> z=find(abs(x(1, 2:length(x))-‐x(1))==min(abs(x(1, 2:length(x))-‐x(1)))) z = 3 9 >> z(1) ans = 3 Figura 31

Para ir terminando, recordemos que el valor que nos interesa devolver tiene que hacer referencia a la posición en el vector original, x. Por ello, devolveremos realmente z(1)+1:

>> z(1)+1 ans = 4 Figura 32

Llevemos todo esto a una función de MATLAB (Función 34):

1) Primero comprobamos la corrección de los argumentos. 2) Luego mostramos el valor del vector original, v (nótese que tenemos una

instrucción compuesta simplemente de la palabra v sin punto y coma al final: la supresión del punto y coma hace que, al ejecutar esta instrucción, se muestre el valor de v; también lo hemos quitado en las siguientes líneas, para ver en la consola de MATLAB cómo va evolucionando el resultado).

3) A continuación, en una variable a la que llamamos vectorDesdeLaPosicion2 colocamos los elementos del vector original desde la posición 2 hasta el final.

4) En valoresAbsolutos guardamos un nuevo vector con el valor absoluto de las diferencias respecto del primer elemento de v.

Macario Polo Usaola

40

5) En minimo guardamos el valor mínimo de los valores absolutos de las diferencias.

6) En posicionesDeLosMinimos guardamos un vector con las posiciones en las que se encuentra el valor mínimo.

7) Finalmente, devolvemos en p la posición del primer elemento de posicionesDeLosMinimos, que es el elemento más cercano a v(1).

function p = distanciaAlPrimero2(v) if (nargin==0) v=rand(1,10)*10; end if (length(v)<=2) p=-1; return; end v vectorDesdeLaPosicion2=v(1, 2:length(v)) valoresAbsolutos=abs(vectorDesdeLaPosicion2-v(1)) minimo=min(valoresAbsolutos) posicionesDeLosMinimos=find(valoresAbsolutos==minimo) p=posicionesDeLosMinimos(1)+1 end Función 34

Si ejecutamos la función, el resultado es el siguiente:

>> distanciaAlPrimero2(x) v = 1 2 3 1 4 8 -‐1 6 7 1 vectorDesdeLaPosicion2 = 2 3 1 4 8 -‐1 6 7 1 valoresAbsolutos = 1 2 0 3 7 2 5 6 0 minimo = 0 posicionesDeLosMinimos = 3 9 p = 4 ans = 4 Figura 33


41

Ejercicio 13. Números primos

Escriba una función que determine si el número que se le pasa como parámetro es o no primo.

• Solución 1.

Un número es primo cuando sólo puede dividirse por sí mismo y por 1. Un número es divisible por otro cuando el resto de la división entera es 0. Ya vimos que MATLAB dispone de la función mod(x, y), que devuelve el resto de la división entera de x entre y.

Una primera forma de resolver el problema es ir dividiendo el número n por 1, por 3, etcétera, hasta llegar a n. Si el número de divisores encontrados es 2, entonces el número es primo:

function result = esPrimo1(n) numeroDeDivisores=0; for i=1:n if mod(n, i)==0 numeroDeDivisores=numeroDeDivisores+1; end end if numeroDeDivisores==2 result=1; else result=0; end end Figura 34

Un pequeño cambio que podemos hacerle a la función está en el último if: en lugar de preguntar cuántos divisores hay y asignar a result, podemos asignar directamente el resultado de computar numeroDeDivisores==2, que devuelve 1 o 0 en función de que el resultado sea cierto o falso:

function result = esPrimo1(n) numeroDeDivisores=0; for i=1:n if mod(n, i)==0 numeroDeDivisores=numeroDeDivisores+1; end end result= numeroDeDivisores==2; end Función 35

Macario Polo Usaola

42

• Solución 2.

La solución anterior, no obstante, es muy ineficiente, porque hacemos siempre n divisiones. Podríamos empezar a dividir por 2 y parar a la mitad de n: si no encontramos divisores, entonces el número es primo.

function result = esPrimo3(n) numeroDeDivisores=0; for i=2:n/2 if mod(n, i)==0 numeroDeDivisores=numeroDeDivisores+1; end end result= numeroDeDivisores==0; end Función 36

• Solución 3.

Aunque la solución anterior es más eficiente, probablemente podamos averiguar si n es primo antes de llegar a la mitad de n. En lugar de recorrer con un for, podemos utilizar un while que se detenga o bien cuando se llegue a la mitad de n, o bien cuando se encuentre un divisor entre 2 y n/2:

function result = esPrimo4(n) numeroDeDivisores=0; i=2; while (i<=n/2 && numeroDeDivisores==0) if mod(n, i)==0 numeroDeDivisores=numeroDeDivisores+1; end i=i+1; end result= numeroDeDivisores==0; end Función 37

• Solución 4.

Una variante, aún más rápida, consiste en buscar hasta la raíz cuadrada de n, en lugar de hasta la mitad. La función de MATLAB para la raíz cuadrada es sqrt(x):

function result = esPrimo5(n) tic; numeroDeDivisores=0; i=2; while (i<=sqrt(n) && numeroDeDivisores==0) if mod(n, i)==0 numeroDeDivisores=numeroDeDivisores+1;


43

end i=i+1; end result= numeroDeDivisores==0; toc; end Función 38

• Solución 5.

Una última posición pasa por el uso de la función isprime(x) de MATLAB, que devuelve 1 si x es primo y 0 en caso contrario.

Macario Polo Usaola

44

Ejercicio 14. Vector con los n primeros números primos

Escriba una función que devuelva un vector con los n primeros números primos.

• Solución 1 (errónea).

Una solución incorrecta, pero en la que es fácil caer, consiste en disponer de un bucle for desde 1 hasta n, e ir preguntando si i es primo. En caso afirmativo, lo añadimos al resultado. Es decir:

function result = vectorNPrimerosPrimosMalo(n) result=[]; for i=1:n if (isprime(i)) result=[result i]; end end end Función 39. Una versión incorrecta del algoritmo solicitado

El código anterior no funciona bien, porque devuelve un vector de primos, pero no con los n primeros, sino con los que están entre 1 y n:

>> vectorNPrimerosPrimosMalo(10) ans = 2 3 5 7 Figura 35

Obsérvese que usamos (en la Función 39) la función de MATLAB isPrime, en lugar de cualquiera de las que hemos escrito antes.

• Solución 2.

La solución entonces es sencilla: en lugar de ir de manera fija desde 1 a n con un for, iremos añadiendo elementos mientras que no hayamos encontrado n números: es decir, mientras (while) el número de elementos en el vector resultado sea menor que n.


45

function result = vectorNPrimerosPrimos1(n) result=[]; i=1; while (length(result)<n) if (isprime(i)) result=[result i]; end i=i+1; end end Función 40

Ahora, el resultado que nos da MATLAB es:

>> vectorNPrimerosPrimos1(10) ans = 2 3 5 7 11 13 17 19 23 29 Figura 36

Nótese, en la figura anterior, que el vector result no contiene el valor 1. De hecho, MATLAB no considera que el 1 sea primo:

>> isprime(1) ans = 0 Figura 37

Macario Polo Usaola

46

Ejercicio 15. Vector con los n primeros números primos ordenados de mayor a menor

Escriba una función que devuelva un vector con los n primeros números primos ordenados de mayor a menor.

• Solución 1.

Para resolver este ejercicio podemos añadir una sencilla línea al código de la Función 40 (página 45), en la que llamamos a la función sort de MATLAB. sort ordena un vector o una matriz de menor a mayor pero, si utilizamos el parámetro descend, lo ordena descendentemente:

function result = vectorNPrimerosPrimosOrdenado1(n) result=[]; i=1; while (length(result)<n) if (isprime(i)) result=[result i]; end i=i+1; end result=sort(result, 'descend'); end Función 41

• Solución 2.

En el código anterior, en la línea que hay dentro del if, añadimos cada valor de i que vamos encontrando al final del vector (result=[result i]). En lugar de hacer eso, podemos añadirlo al principio, escribiendo result=[i result]:

function result = vectorNPrimerosPrimosOrdenado2(n) result=[]; i=1; while (length(result)<n) if (isprime(i)) result=[i result]; end i=i+1; end end Función 42

El resultado de la funciones vectorNPrimerosPrimosOrdenado1 (Función 41) y vectorNPrimerosPrimosOrdenado2 (Función 42) es exactamente el mismo:


47

>> vectorNPrimerosPrimosOrdenado1(10) ans = 29 23 19 17 13 11 7 5 3 2

>> vectorNPrimerosPrimosOrdenado2(10) ans = 29 23 19 17 13 11 7 5 3 2

Figura 38

Macario Polo Usaola

48

Ejercicio 16. Calcular el enésimo número primo

Escriba una función que devuelva el n-‐ésimo número primo, siendo n el valor pasado como parámetro.

• Solución 1.

Utilizaremos la función isprime(x) para ir generando números primos hasta que un contador llegue a n:

function result = enesimoPrimo( n ) contador=0; i=2; while contador<n if isprime(i)==1 contador=contador+1; end if contador==n result=i; end i=i+1; end end Función 43. Cálculo del enésimo primo


49

Ejercicio 17. Contar números distintos en un vector

Escriba una función que devuelva cuántos números distintos aparecen en el vector que se pasa como parámetro.

• Solución 1.

Una forma de hacerlo a mano, que trataremos de imitar, es la siguiente: recorreremos el vector v que nos pasan como parámetro desde el principio hasta el final con un for; en cada iteración, miramos si el valor i-‐ésimo ya se encuentra en un vector auxiliar que habremos construido previamente inicializándolo a vacío: si el valor está, no lo añadimos; si no está, lo añadimos. Como resultado, devolveremos el tamaño del vector auxiliar:

posición 1 2 3 4 5 6 7 8 9 10 v= 1 2 3 1 4 8 -‐1 6 7 1

auxiliar= 1 2 3 4 8 -‐1 6 7

La solución podemos implementarla como en la Función 44: creamos el vector auxiliar vacío; luego, en el bucle, almacenamos en un vector aparicionesDeVi las veces que aparece el número v(i) en el vector auxiliar. Si no aparece ninguna vez (es decir, si la longitud del vector aparicionesDeVi es cero), entonces lo añadimos. Al final, devolvemos la longitud del vector auxiliar como resultado.

function result = numerosDistintos1( v ) auxiliar=[]; for i=1:length(v) aparicionesDeVi=find(auxiliar==v(i)); if length(aparicionesDeVi)==0 auxiliar=[auxiliar v(i)]; end end result=length(auxiliar); end Función 44

Un par de ejemplos de la ejecución son:

>> x x = 1 2 3 1 4 8 -‐1 6 7 1 >> numerosDistintos1(x) ans = 8

>> z=[1 1 1 1 2 3 1] z = 1 1 1 1 2 3 1 >> numerosDistintos1(z) ans = 3

Figura 39

Macario Polo Usaola

50

Ejercicio 18. Descomposición en factores primos (I)

Escriba una función que devuelva un vector con los factores primos del número que se pasa como parámetro.

• Solución 1.

Lo que hacemos habitualmente a mano es, como se muestra a continuación, encontrar el menor número primo por el que n es divisible: cuando lo encontramos, lo guardamos, calculamos el cociente y seguimos hasta que el cociente sea 1.

Vamos a proceder exactamente de la misma forma, aprovechando la función enesimoPrimo que escribimos en la Función 43 (página 48): mientras el cociente (que inicialmente es n, pero que se va actualizando según vayamos encontrando factores primos) sea distinto de 1, buscamos (en el while anidado) el primer número primo que divide al cociente: cuando lo encontramos, lo añadimos al vector result y actualizamos el cociente al valor que tenía dividido por el número primo que acabamos de encontrar.

function result = factoresPrimos1( n ) result=[]; cociente=n; while (cociente~=1) i=1; while (mod(cociente, enesimoPrimo(i))~=0) i=i+1; end result=[result enesimoPrimo(i)]; cociente=floor(cociente/enesimoPrimo(i)); end end Función 45. Cálculo de los factores primos de n

Los dos ejemplos manuscritos que veíamos arriba son:


51

>> factoresPrimos1(120) ans = 2 2 2 3 5

>> factoresPrimos1(27) ans = 3 3 3

Figura 40

Macario Polo Usaola

52

Ejercicio 19. Descomposición en factores primos (II)

Escriba una función que devuelva una matriz con dos filas: en la primera aparecerán los factores primos del número que se pasa como parámetro; en la segunda, los exponentes de dichos factores primos.

Por ejemplo, para el número 120, que es 23·3·5, se devolverá la siguiente matriz:

2 3 5 3 1 1

• Solución 1.

Del ejercicio anterior tenemos la función que devuelve un vector con los factores primos del n que pasamos como parámetro. Del 120, por ejemplo, obtenemos el siguiente vector:

posición 1 2 3 4 5 result= 2 2 2 3 5

Lo que haremos será escribir una nueva función que haga lo siguiente:

1) Guardaremos los factores primos de n en un vector factores, que construiremos llamando a la Función 45 (pagina 50).

2) Crearemos dos vectores: uno para guardar los factores que encontremos (el 2, el 3 y el 5 en el ejemplo del número 120) y otro para guardar los exponentes (3, 1 y 1 en el mismo ejemplo). Llamaremos a estos vectores, respectivamente, filaFactores y filaExponentes. Cuando los hayamos completado, los utilizaremos para devolver la matriz resultante.

3) Recorreremos todos los valores que tengamos en el vector factores. Si el valor i-‐ésimo no está en filaFactores, lo añadimos al final y añadimos también un 1 al final de filaExponentes. Si el valor ya estuviera, entonces basta con incrementar en uno el valor correspondiente en filaExponentes.

4) Finalmente, devolveremos una matriz formada por filaFactores y FilaExponentes.

Esto es lo que se hace en la función siguiente:


53

function result = factoresPrimos2( n ) factores=factoresPrimos1(n); filaFactores=[]; filaExponentes=[]; for i=1:length(factores) factorI=factores(i); posicionDelFactor=find(filaFactores==factorI); if length(posicionDelFactor)==0 filaFactores=[filaFactores factorI]; filaExponentes=[filaExponentes 1]; else filaExponentes(posicionDelFactor(1))= filaExponentes(posicionDelFactor(1))+1; end end result=[filaFactores; filaExponentes]; end Función 46. Devolución de los factores primos en dos vectores

Nótese que la matriz resultado la construimos utilizando corchetes y el operador punto y coma para separar las filas que compondrán la matriz:

result=[filaFactores; filaExponentes];

Hagamos una traza de ejemplo con el número 120. Como detalle, nótese que en la variable posicionDelFactor guardamos el resultado de ejecutar la función find de MATLAB, que devuelve un vector con las posiciones de los elementos que cumplen cierta condición. Si ninguno de los elementos la cumple, posicionDelFactor estará vacío.

Comentarios factores i factorI posicionDelFactor filaFactores filaExponentes [2 2 2 3 5] [ ] [ ] 1 2 [ ] El if es cierto 1 2 [ ] [ 2 ] [ 1 ] 2 2 [ 1 ] [ 2 ] [ 1 ] El if es falso 2 2 [ 1 ] [ 2 ] [ 2 ] 3 2 [ 1 ] [ 2 ] [ 2] El if es falso 3 2 [ 1 ] [ 2 ] [ 3 ] 4 3 [ ] [ 2 ] [ 3 ] El if es cierto 4 3 [ ] [ 2 3 ] [ 3 1 ] 5 5 [ ] [ 2 3 ] [ 3 1 ] El if es cierto 5 5 [ ] [ 2 3 5] [ 3 1 1 ]

Y aquí se termina el bucle porque se ha llegado a i=5, que es la longitud del vector de entrada. Figura 41. Traza de la Función 46 para n=120

Si ejecutamos la función en MATLAB, el resultado es:

>> factoresPrimos2(120) ans = 2 3 5 3 1 1 Figura 42

Macario Polo Usaola

54

Ejercicio 20. Máximo común divisor

Escriba una función que devuelva el máximo común divisor de n y m.

• Solución 1.

Lo habitual es hacer la descomposición en factores primos de n y m y, luego, tomar los factores comunes con su menor exponente. Por ejemplo, para calcular el máximo común divisor de 48 y 60, hacemos:

48=24·3

60=22·3·5

Con lo que el mcd es 22·3=12.

Si aplicamos la Función 46 a los números 48 y 60, obtenemos las dos siguientes matrices a las que, por entendernos, llamaremos m48 y m60:

m48 2 3 m60 2 3 5 4 1 2 1 1

Lo que vamos a hacer es recorrer los factores (la fila 1) de m48 y ver si están en los factores de m60. En caso afirmativo, añadiremos a una variable result de acumulación el factor común multiplicado por el menor exponente de los dos.

function result = mcd1(n, m) fpN=factoresPrimos2(n); fpM=factoresPrimos2(m); factoresN=fpN(1, :); exponentesN=fpN(2, :); factoresM=fpM(1, :); exponentesM=fpM(2, :); result=1; for i=1:length(factoresN) posicionEnM=find(factoresM==factoresN(i)); if (length(posicionEnM)>0) exponente=min(exponentesN(i), exponentesM(posicionEnM(1))); result=result*factoresN(i)^exponente; end end end Función 47

• Solución 2.

Otra solución elegante viene dada por la aplicación del algoritmo de Euclides: para calcular el mcd de n y m se hace lo siguiente:


55

1) Si m==0, entonces mcd(n, m)=n y paramos. 2) Si no, mcd(n, m)=mcd(m, r), donde r es el resto de n entre m.

Se trata, como se ve, de una función recursiva pero que es muy fácil de implementar:

function result = mcd2Euclides(n, m) if m==0 result=n; else r=mod(n, m); result=mcd2Euclides(m, r); end end Función 48

Macario Polo Usaola

56

Ejercicio 21. Tablero de ajedrez

Escribir una función que dibuje un tablero de ajedrez. Las casillas negras se indicarán con N y las blancas con B.

• Solución 1.

El tablero de ajedrez es un cuadrado de 8x8 casillas. Sabiendo que la casilla superior izquierda es blanca, a partir de ella podemos colorear todas las demás. Dicha casilla está en la posición (1, 1): si nos damos cuenta, son blancas las casillas cuya suma de fila y columna es par, y negras las demás.

Una función que dibuja el tablero es la siguiente:

function tablero = tablero() tablero=char(8,8); for i=1:1:8 for j=1:1:8 if (mod(i+j, 2)==0) tablero(i,j)='B'; else tablero(i,j)='N'; end end end end Función 49

Obsérvese que la variable tablero, que almacena el resultado, se inicializa a una matriz de 8x8 caracteres, ya que en sus posiciones colocaremos letras.

Si la ejecutamos, el resultado es:

>> tablero ans = BNBNBNBN NBNBNBNB BNBNBNBN NBNBNBNB BNBNBNBN NBNBNBNB BNBNBNBN NBNBNBNB Figura 43


57

Ejercicio 22. Alfil

Escriba una función en MATLAB que tome como parámetros la posición (fila y columna) de un alfil en el tablero de ajedrez y muestre todos sus posibles movimientos con un asterisco.

• Solución 1.

El alfil se mueve en diagonal: un alfil como el de la figura, situado en la fila 4, columna 4, puede moverse a todas las casillas señaladas con el asterisco. Si nos fijamos, la suma de la fila y columna de las casillas de la diagonal ascendente es siempre 8 (igual que la posición en la que está situado el alfil); respecto de las que están en la descendente, sucede que la resta de sus columna y fila es cero, igual que la resta de la posición original del alfil.

1 2 3 4 5 6 7 8 1 * * 2 * * 3 * * 4 A 5 * * 6 * * 7 * * 8 *

Hecha esta observación, la solución es muy sencilla:

function t = alfil( col, fila ) t=tablero(); for i=1:1:8 for j=1:1:8 if (i+j==col+fila || i-j==col-fila) t(i,j)='*'; end end end end Función 50. Una solución fácil de implementar, pero no muy eficiente, para los movimientos del alfil

Y, si llamamos a la función, obtenemos:

>> alfil(4, 4) ans = *NBNBN*N N*NBN*NB BN*N*NBN NBN*NBNB BN*N*NBN N*NBN*NB *NBNBN*N NBNBNBN*

>> alfil(4, 1) ans = BNB*BNBN NB*BNBNB B*BNBNBN *BNBNBNB B*BNBNBN NB*BNBNB BNB*BNBN NBNB*BNB

Figura 44

Macario Polo Usaola

58

Nótese que, si pasamos los valores de los parámetros intercambiados (en lugar de 4,1 pasamos 1,4), el resultado de la derecha de la figura anterior cambia:

>> alfil(4, 4) ans = *NBNBN*N N*NBN*NB BN*N*NBN NBN*NBNB BN*N*NBN N*NBN*NB *NBNBN*N NBNBNBN*

>> alfil(1,4) ans = BNB*BNBN NB*B*BNB B*BNB*BN *BNBNB*B BNBNBNB* NBNBNBNB BNBNBNBN NBNBNBNB

Figura 45. El resultado derecho de la Figura 44 cambia si alteramos el orden del valor de los parámetros

• Solución 2.

Aunque funciones, la solución anterior no es, de todos modos, demasiado eficiente, ya que pasa por las 64 casillas del tablero. Si lo hacemos a mano, no nos hace falta ir recorriendo todas las casillas para saber si una casilla dada es alcanzable o no por el alfil.

Para marcar, sobre un tablero de verdad y manualmente, las casillas alcanzables por un alfil, basta con que vayamos moviéndonos en cuatro direcciones y visitando muchas menos casillas: arriba, derecha; abajo, derecha; arriba, izquierda; abajo, izquierda. Esto lo podemos conseguir con cuatro bucles while (Función 51), uno para los movimientos en cada dirección. Teniendo en cuenta que, en MATLAB, la primera fila (la fila 1) es la de arriba, la primera columna (columna 1) es la de la izquierda y que para colocar un elemento en una matriz se pasa primero la fila y luego la columna, tenemos que:

1) Movernos hacia arriba y a la derecha significa incrementar la columna y decrementar la fila. Usamos dos variables i y j para ir marcando la casilla en la que queremos colocar el asterisco: partiendo de la posición inicial (que viene dada por los parámetros col, fila), decrementamos la fila (i) e incrementamos la columna (j) mientras estemos dentro de los límites del tablero.

2) Movernos hacia abajo y a la derecha equivale a incrementar la columna e incrementar la fila. Ahora, incrementamos i y j en cada vuelta del bucle mientras estemos dentro delos límites del tablero.

3) Movernos hacia arriba y a la izquierda equivale a decrementar tanto la columna como la fila. Ahora, restamos 1 a i y 1 a j en cada vuelta del bucle mientras estemos dentro delos límites del tablero.

4) Movernos hacia abajo y a la izquierda implica el decremento de la columna y el incremento de la fila: mientras estemos dentro delos límites del tablero, sumamos 1 a i y restamos 1 a j.


59

function t = alfil2( col, fila ) t=tablero(); % Derecha, arriba i=fila; j=col; while (i>=1 && j<=8) t(i, j)='*'; i=i-1; j=j+1; end % Derecha, abajo i=fila; j=col; while (i<=8 && j<=8) t(i, j)='*'; i=i+1; j=j+1; end % Izquierda, arriba i=fila; j=col; while (i>=1 && j>=1) t(i, j)='*'; i=i-1; j=j-1; end % Izquierda, abajo i=fila; j=col; while (i<=8 && j>=1) t(i, j)='*'; i=i+1; j=j-1; end end Función 51. Movimientos del alfil, conseguidos con menor coste

• Solución 3.

Es importante que el código que escribamos sea legible, fácil de usar por terceras personas y, en la medida de lo posible, fácil de entender. Respecto del código de las dos soluciones que hemos dado para el movimiento del alfil, un pequeño detalle mejorable es que la función reciba los parámetros en el mismo orden en que se utilizan en las matrices de MATLAB: es decir, si MATLAB usa la notación fila, columna para colocar un valor en la matriz, queda mejor que la función alfil tome también los parámetros en ese orden. Esto hará más difícil que el usuario de nuestra función se equivoque.

Macario Polo Usaola

60

Ya que los valores de los parámetros col y fila se usan sólo para realizar asignaciones, podemos modificar la cabecera de la función para que los parámetros se pasen en el orden habitual. Es decir, dejar la cabecera como en la Función 52:

function t = alfil3( fila, col) % Todo el código de la función exactamente igual … end Función 52. La misma Función 51, pero con los parámetros intercambiados


61

Ejercicio 23. El caballo de ajedrez

Escribir una función en MATLAB que tome como parámetros la posición (fila y columna) de un caballo en el tablero de ajedrez y muestre todos sus posibles movimientos con un asterisco.

• Solución 1.

De manera general, en este tipo de problemas (como en el anterior, del alfil) se trata de encontrar algún patrón que relacione la posición de origen con las posibles posiciones de destino.

En el caso del caballo del ajedrez, el movimiento es en L, a derecha e izquierda y hacia arriba y abajo, como se muestra en el tablero siguiente, de manera que el número de casillas de la L que puede moverse es tres: dos a la derecha/izquierda y una arriba/abajo, o una a la derecha/izquierda y dos arriba/abajo.

1 2 3 4 5 6 7 8 1 2 * * 3 * * 4 C 5 * * 6 * * 7 8

Por cambiar un poco el punto de vista de la solución respecto del ejercicio anterior del alfil, haremos ahora lo siguiente:

1) A partir de la posición inicial (que vendrá en el orden fila, col), moveremos una columna a la derecha (en el ejemplo de arriba, iremos a la casilla 4,5). Una vez aquí, colocamos un asterisco dos filas arriba y dos filas abajo. Así, habremos colocado los asteriscos en (2,5) y (6,5).

2) Volvemos a la posición inicial y movemos dos casillas a la derecha. Luego, colocamos el asterisco una fila arriba y una fila abajo.

3) Otra vez desde la posición inicial, nos movemos una a la izquierda y colocamos un asterisco dos filas arriba y dos filas abajo.

4) Por último, nos movemos dos columnas a la izquierda y colocamos el asterisco dos filas arriba y dos filas abajo.

Obviamente, tenemos que controlar que no nos salgamos de los límites del tablero, que vienen dados por los valores 1 a 8 para la fila y la columna.

La solución que damos en la Función 53 simula estos cuatro bloques de movimientos. Utilizamos dos variables auxiliares i y j para denotar respectivamente la fila y columna en que debemos colocar los asteriscos. En el primero, por ejemplo, asignamos a j el valor del parámetro col incrementado en 1; si estamos dentro del tablero (es decir, si j<=8), entonces restamos 2 a la fila (variable i), volvemos a comprobar que estamos dentro del tablero (i>=1) y, en caso afirmativo, colocamos el asterisco. Hacemos a continuación lo mismo para la casilla situada dos filas por debajo de la original (i=fila+2).

Macario Polo Usaola

62

function t = caballo1(fila, col) t=tablero(); % 1 a la derecha, 2 arriba y abajo j=col+1; if j<=8 i=fila-2; if i>=1 t(i, j)='*'; end i=fila+2; if (i<=8) t(i, j)='*'; end end % 2 a la derecha, 1 arriba y abajo j=col+2; if j<=8 i=fila-1; if i>=1 t(i, j)='*'; end i=fila+1; if (i<=8) t(i, j)='*'; end end % 1 a la izquierda, 2 arriba y abajo j=col-1; if j>=1 i=fila-2; if i>=1 t(i, j)='*'; end i=fila+2; if (i<=8) t(i, j)='*'; end end % 2 a la izquierda, 1 arriba y abajo j=col-2; if j>=1 i=fila-1; if i>=1 t(i, j)='*'; end i=fila+1; if (i<=8) t(i, j)='*'; end end end Función 53. Movimientos del caballo


63

• Solución 2.

Si nos fijamos en los bloques de código de la Función 53, vemos que los dos movimientos a la derecha son casi exactamente iguales entre sí, como también los dos movimientos a la izquierda. En la Figura 46 resaltamos en amarillo las diferencias entre los movimientos hacia la derecha: cuando se suma 1 a la columna, se resta y suma 2 a la fila; cuando se suma 2 a la columna, se resta y suma 1 a la fila.

% 1 a la derecha, 2 arriba y abajo j=col+1; if j<=8 i=fila-2; if i>=1 t(i, j)='*'; end i=fila+2; if (i<=8) t(i, j)='*'; end end

% 2 a la derecha, 1 arriba y abajo j=col+2; if j<=8 i=fila-1; if i>=1 t(i, j)='*'; end i=fila+1; if (i<=8) t(i, j)='*'; end end

Figura 46. Los movimientos a la derecha son muy parecidos en la Función 53

Podemos agrupar los dos trozos de código en uno solo, con un bucle for cuya variable de control, a la que podemos llamar suma, vaya desde 1 hasta 2 y que utilizaremos para sumarla a la variable j. Es decir, sustituir ambos fragmentos de código por uno solo, como en la Figura 47:

% Movimientos a la derecha for suma=1:2 j=col+suma; if j<=8 i=fila-2; % Si suma=1, restar 2; si suma=2, restar 1 if i>=1 t(i, j)='*'; end i=fila+2; % Si suma=1, sumar 2; si suma=2, sumar 1 if (i<=8) t(i, j)='*'; end end end Figura 47. Paso 1 del agrupamiento en uno de los dos bloques de la Figura 46

En la figura anterior, sumamos la variable suma a j: la primera vez se le suma 1, y la segunda 2. Sin embargo, nos falta actualizar adecuadamente los valores que deben restarse y sumarse y que hemos resaltado en morado. En este caso, cuando suma=1 hay que restar/sumar 2 o 1 según suma sea, respectivamente, 1 o 2.

Este valor que deseamos sustituya al -‐2 y al +2 que aparecen en morado lo conseguimos con la expresión 3-‐suma. El código para el movimiento a la derecha, entonces, queda de la siguiente manera:

Macario Polo Usaola

64

function t = caballo2(fila, col) t=tablero(); % Movimientos a la derecha for suma=1:2 j=col+suma; if j<=8 i=fila-(3-suma); if i>=1 t(i, j)='*'; end i=fila+(3-suma); if (i<=8) t(i, j)='*'; end end end % 1 a la izquierda, 2 arriba y abajo j=col-1; if j>=1 i=fila-2; if i>=1 t(i, j)='*'; end i=fila+2; if (i<=8) t(i, j)='*'; end end % 2 a la izquierda, 1 arriba y abajo j=col-2; if j>=1 i=fila-1; if i>=1 t(i, j)='*'; end i=fila+1; if (i<=8) t(i, j)='*'; end end end Función 54. Movimientos del caballo, agrupando los movimientos a la derecha en un solo bloque

Del mismo modo, agrupamos los movimientos a la izquierda, de modo que la función queda así:


65

function t = caballo2(fila, col) t=char(8,8); for i=1:1:8 for j=1:1:8 t(i,j)='-'; end end t(fila, col)='C'; % Movimientos a la derecha for suma=1:2 j=col+suma; if j<=8 i=fila-(3-suma); if i>=1 t(i, j)='*'; end i=fila+(3-suma); if (i<=8) t(i, j)='*'; end end end % Movimientos a la izquierda for resta=1:2 j=col-resta; if j>=1 i=fila-(3-resta); if i>=1 t(i, j)='*'; end i=fila+(3-resta); if (i<=8) t(i, j)='*'; end end end end Función 55. Movimientos del caballo, con los movimientos a la derecha y a la izquierda en dos for

Observa que, con objeto de facilitar la lectura del resultado, en el código anterior hemos sustituido la llamada a la función tablero() por una inicialización del tablero mediante guiones, y que hemos añadido una instrucción (resaltada en morado) para colocar una C en el lugar en que se encuentra el caballo. Dos ejemplos de ejecución son los siguientes:

Macario Polo Usaola

66

>> caballo2(4, 4) ans = -‐-‐-‐-‐-‐-‐-‐-‐ -‐-‐*-‐*-‐-‐-‐ -‐*-‐-‐-‐*-‐-‐ -‐-‐-‐C-‐-‐-‐-‐ -‐*-‐-‐-‐*-‐-‐ -‐-‐*-‐*-‐-‐-‐ -‐-‐-‐-‐-‐-‐-‐-‐ -‐-‐-‐-‐-‐-‐-‐-‐

>> caballo2(4, 8) ans = -‐-‐-‐-‐-‐-‐-‐-‐ -‐-‐-‐-‐-‐-‐*-‐ -‐-‐-‐-‐-‐*-‐-‐ -‐-‐-‐-‐-‐-‐-‐C -‐-‐-‐-‐-‐*-‐-‐ -‐-‐-‐-‐-‐-‐*-‐ -‐-‐-‐-‐-‐-‐-‐-‐ -‐-‐-‐-‐-‐-‐-‐-‐

Figura 48

• Solución 3.

En una vuelta de tuerca más, vemos también semejanzas entre los dos bucles for de la Función 55. Como vemos en la Figura 49, en uno llamamos a la variable suma y en otro resta (en amarillo); otra diferencia (en morado), es que en uno sumamos y en otro restamos; la última diferencia (en verde) es que en uno comparamos j<=8 y en otro j>=1.

% Movimientos a la derecha for suma=1:2 j=col+suma; if j<=8 i=fila-(3-suma); if i>=1 t(i, j)='*'; end i=fila+(3-suma); if (i<=8) t(i, j)='*'; end end end

% Movimientos a la izquierda for resta=1:2 j=col-resta; if j>=1 i=fila-(3-resta); if i>=1 t(i, j)='*'; end i=fila+(3-resta); if (i<=8) t(i, j)='*'; end end end

Figura 49. Los bucles de los movimientos a la derecha y a la izquierda son muy parecidos

Bueno, pues es sencillo agrupar ambos bucles, como se hace en la Función 56: las dos condiciones (en verde) las agrupamos en una sola (j>=1 && j<=8); como una vez nos interesa sumar y otra restar, nos inventamos una variable nueva signo que tome valor -‐1 y +1 y que usamos como variable de control de un nuevo bucle for (en amarillo); esta variable signo la utilizamos (en morado) para multiplicar por factor, que sustituye a las antiguas variables suma y resta.


67

function t = caballo3(fila, col) t=char(8,8); for i=1:1:8 for j=1:1:8 t(i,j)='-'; end end t(fila, col)='C'; for signo=-1:+2:1 for factor=1:2 j=col+signo*factor; if j>=1 && j<=8 i=fila-(3-factor); if i>=1 t(i, j)='*'; end i=fila+(3-factor); if (i<=8) t(i, j)='*'; end end end end end Función 56. Todos los movimientos del caballo en dos for anidados

Macario Polo Usaola

68

Ejercicio 24. Matriz identidad

Escribir una función en MATLAB que, sin usar la función eye, devuelva una matriz identidad de nxn.

• Solución 1.

La función eye(n) devuelve directamente la matriz identidad:

>> eye(5) ans = 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 Figura 50

Para cumplir el enunciado, construiremos una matriz de nxn ceros y, luego, recorreremos la diagonal principal (en sus posiciones coinciden la fila y la columna) y colocamos un 1.

En una primera solución, recorremos todas las posiciones de la matriz con dos bucles anidados controlados por i y j: si i==j, entonces la casilla es de la diagonal principal y colocamos un 1:

function result = matrizIdentidad1(n) result=zeros(n); for i=1:n for j=1:n if i==j result(i, j)=1; end end end end Función 57. Matriz identidad recorriendo toda la matriz

• Solución 2.

Claramente, no es necesario recorrer todas las casillas de la matriz. Podemos recorrer, sencillamente, la diagonal principal con un solo bucle for. Basta con recorrer desde 1 hasta n con una variable i y colocal el 1 en (i, i):


69

function result = matrizIdentidad2(n) result=zeros(n); for i=1:n result(i, i)=1; end end Función 58. Matriz identidad, recorriendo solamente la diagonal principal

Macario Polo Usaola

70

Ejercicio 25. Diagonal principal

Escribir una función en MATLAB que, sin usar la función diag, devuelva los valores situados en la diagonal principal de una matriz que se pasa como parámetro.

• Solución 1.

La función diag(M) devuelve directamente, en forma de vector, los valores ubicados en la diagonal principal de la matriz M:

>> M=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16] M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

>> diag(M) ans = 1 6 11 16

Figura 51. Construcción de una matriz (izquierda) y extracción de su diagonal principal con diag

Como el enunciado nos prohíbe usar la función diag, recorreremos con un solo buce for controlado por una variable i las posiciones (i, i):

function diagonal = diagonalPrincipal(M) diagonal=[]; for i=1:length(M) diagonal=[diagonal M(i, i)]; end end Función 59. Extracción de la diagonal principal

Al ejecutar, obtenemos esto:

>> M M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

>> diagonalPrincipal(M) ans = 1 6 11 16

Figura 52

Si queremos obtener el vector traspuesto, para devolver el resultado igual que lo devuelve la función diag (Figura 51), basta con añadir la línea resaltada:


71

function diagonal = diagonalPrincipal(M) diagonal=[]; for i=1:length(M) diagonal=[diagonal M(i, i)]; end diagonal=diagonal'; end Función 60. Extracción de la diagonal principal como un vector vertical

• Solución 2.

Supongamos que debemos comprobar que la matriz que se pasa como parámetro sea cuadrada.

Si tenemos la siguiente matriz no cuadrada N:

1 2 3 1 1 2 3 2 4 5 6 3 7 8 9 4 10 11 12

La función length(N) nos devuelve el número de filas de la matriz:

>> N=[1 2 3; 4 5 6; 7 8 9; 10 11 12] N = 1 2 3 4 5 6 7 8 9 10 11 12

>> length(N) ans = 4

Figura 53. Construcción de una matriz no cuadrada y cálculo de su longitud

Si queremos conocer su número de columnas, debemos extraer una fila y calcular su longitud. Para extraer una fila de la matriz usamos MATRIZ(númeroDeFila, :):

>> N(1, :) ans = 1 2 3

>> length(N(1, :)) ans = 3

Figura 54. Extracción de la fila 1 de la matriz N (izquierda) y cálculo de la longitud de esa fila

Así, añadimos a la función anterior el if que resaltamos:

Macario Polo Usaola

72

function diagonal = diagonalPrincipal(M) if length(M)~=length(M(1, :)) disp('La matriz debe ser cuadrada'); return; end diagonal=[]; for i=1:length(M) diagonal=[diagonal M(i, i)]; end diagonal=diagonal'; end Función 61

El resultado con las matrices M (cuadrada) y N (no cuadrada) es:

>> M M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 >> diagonalPrincipal(M) ans = 1 6 11 16

>> N N = 1 2 3 4 5 6 7 8 9 10 11 12 >> diagonalPrincipal(N) La matriz debe ser cuadrada

Figura 55. Resultado de diagonalPrincipal sobre una matriz cuadrada (izquierda) y una no cuadrada


73

Ejercicio 26. Traza de una matriz

Escribir una función en MATLAB que calcule la traza de una matriz.

• Solución 1.

La traza de una matriz es la suma de los elementos situados en su diagonal principal, por lo que esta función es casi trivial. Basta con recuperar la diagonal principal y sumar sus elementos.

Un solución un poco larga es la siguiente:

function result = traza1(M) if length(M)~=length(M(1, :)) disp('La matriz debe ser cuadrada'); return; end diagonal=[]; for i=1:length(M) diagonal=[diagonal M(i, i)]; end result=0; for i=1:length(diagonal) result=result+diagonal(i); end end Función 62. Cálculo de la traza de una matriz (I)

• Solución 2.

En una segunda aproximación, podemos recuperar la diagonal principal llamando a la función diagonalPrincipal que construimos en la Función 61 (o a la función diag de MATLAB) y sumar sus valores:

function result = traza2(M) diagonal=diagonalPrincipal(M); result=0; for i=1:length(diagonal) result=result+diagonal(i); end end Función 63. Cálculo de la traza de una matriz (II)

• Solución 3.

Por último, en lugar de sumar los elementos con un bucle, como hacemos en la Función 62 y en la Función 63, podemos sumar mediante la función sum de MATLAB:

Macario Polo Usaola

74

function result = traza3(M) diagonal=diagonalPrincipal(M); result=sum(diagonal); end Función 64. Cálculo de la traza de una matriz (III)

El código de la función anterior lo podemos agrupar en una sola línea:

function result = traza4(M) result=sum(diagonalPrincipal(M)); end Función 65. Cálculo de la traza de una matriz (IV)

O, como decíamos, usar diag en lugar de nuestra función diagonalPrincipal:

function result = traza5(M) result=sum(diag(M)); end Función 66. Cálculo de la traza de una matriz (V)

En general, las operaciones tan sencillas las podemos escribir directamente en la línea de comandos de MATLAB:

>> M M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 >> sum(diag(M)) ans = 34 Figura 56. Cálculo de la traza de M desde la línea de comandos


75

Ejercicio 27. Unos y ceros alternados

Escribir una función que construya una matriz cuadrada de anchura par, formada por 1 y 0 alternativos. Por ejemplo, si n=6:

1 2 3 4 5 6 1 1 0 1 0 1 0 2 0 1 0 1 0 1 3 1 0 1 0 1 0 4 0 1 0 1 0 1 5 1 0 1 0 1 0 6 0 1 0 1 0 1

• Solución 1.

Tenemos muchas formas de resolver este ejercicio. En una primera, podemos comenzar creando una matriz de ceros (función zeros) y colocar un 1 en la posición (1, 1). Luego, vamos avanzando de 2 en 2 columnas hasta llegar al límite derecho (n-‐1). Esto lo haríamos para todas las filas impares. Para las pares, colocamos un 1 en la segunda columna y vamos avanzando de 2 en 2 hasta llegar a la columna n.

function result = alternar1(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); % Filas impares for fila=1:2:n-1 for columna=1:2:n-1 result(fila, columna)=1; end end % Filas pares for fila=2:2:n for columna=2:2:n result(fila, columna)=1; end end end Función 67. Unos y ceros alternados (I)

• Solución 2.

Igual que nos pasaba en el ejercicio sobre los movimientos del caballo (página 61), los dos bucles son muy parecidos. Si los comparamos (Figura 57), observamos que si, en los dos bucles de la izquierda, escribimos n en lugar de n-‐1, el resultado sigue siendo válido.

Macario Polo Usaola

76

% Filas impares for fila=1:2:n-1 for columna=1:2:n-1 result(fila, columna)=1; end end

% Filas pares for fila=2:2:n for columna=2:2:n result(fila, columna)=1; end end

Figura 57. Los bucles de las filas nones y las pares son muy parecidos

Es decir, que podemos modificar el bucle de la izquierda para que quede como se muestra:

% Filas impares for fila=1:2:n for columna=1:2:n result(fila, columna)=1; end end

% Filas pares for fila=2:2:n for columna=2:2:n result(fila, columna)=1; end end

Figura 58. Los bucles de las filas nones y las pares son muy parecidos

Ambos bucles pueden agruparse en uno solo, que recorra todas las filas (desde 1 hasta n) y que actúe de diferente manera según la fila sea impar o par (es decir, según mod(fila, 2) sea 1 o 0):

function result = alternar2(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); for fila=1:n if mod(fila, 2)==1 % Si la fila es impar for columna=1:2:n result(fila, columna)=1; end else % Si es par for columna=2:2:n result(fila, columna)=1; end end end end Función 68. Unos y ceros alternados (II)

• Solución 3.´

Podemos simplificar un poco el código de la función anterior si tenemos en cuenta que, cuando la fila es impar, la columna en la que se coloca el primer 1 es la 1 y que, cuando la fila es par, el primer 1 se pone en la columna 2. Luego, sea par o impar la columna, se va incrementando la columna de 2 en 2 hasta llegar a n. O sea:


77

function result = alternar3(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); for fila=1:n if mod(fila, 2)==1 columna=1; else columna=2; end for j=columna:2:n result(fila, j)=1; end end end Función 69. Unos y ceros alternados (III)

• Solución 4.

Simplemente por variar un poco, podemos reescribir la solución anterior y utilizar un while en vez de un for: simplemente debemos inicializar la variable fila antes del bucle, escribir adecuadamente su condición de salida (fila<=n) e incrementar al final del while para que no se forme un bucle infinito:

function result = alternar4(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); fila=1; while fila<=n if mod(fila, 2)==1 columna=1; else columna=2; end for j=columna:2:n result(fila, j)=1; end fila=fila+1; end end Función 70. Unos y ceros alternados (IV)

Macario Polo Usaola

78

• Solución 5.

Otra forma más de solucionar el ejercicio consiste en generar dos vectores distintos: uno para las filas impares y otro para las pares. Luego, recorremos las filas de la matriz (previamente inicializada a, por ejemplo, ceros) y vamos sustituyendo cada fila por filaImpar o filaPar:

function result = alternar5(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); filaImpar=[]; for columna=1:2:n filaImpar(columna)=1; end filaImpar=[filaImpar 0]; filaPar=[]; for columna=2:2:n filaPar(columna)=1; end for fila=1:n if mod(fila, 2)==1 result(fila, :)=filaImpar; else result(fila, :)=filaPar; end end end Función 71. Unos y ceros alternados (V): sustituimos filas

Como pequeño detalle, nótese la necesidad de añadir un cero manualmente a las filas impares (línea resaltada en morado) para que se quede de la misma longitud que las pares.

Por otro lado, véase la forma en que se modifica una fila concreta en MATLAB: la línea resaltada en verde modifica de la variable result la fila número fila; al colocar dos puntos (:) después de la coma, indicamos a MATLAB que sustituya toda la fila.

• Solución 6.

Igual que hemos rellenado por filas en la solución anterior (Función 71), también podemos rellenar por columnas. En este caso inicializamos dos variables columnaImpar y columnaPar y, luego, recorremos todas las columnas, sustituyendo por la que corresponda.


79

function result = alternar6(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); columnaImpar=[]; for fila=1:2:n columnaImpar(fila)=1; end columnaImpar=[columnaImpar 0]'; columnaPar=[]; for fila=2:2:n columnaPar(fila)=1; end columnaPar=columnaPar'; for columna=1:n if mod(columna, 2)==1 result(:, columna)=columnaImpar; else result(:, columna)=columnaPar; end end end Función 72. Unos y ceros alternados (VI): sustituimos columnas

Obsérvese en la figura siguiente la diferencia, en los últimos bucles for de la Función 71 (en que sustituíamos filas) y de la Función 72 (sustituimos columnas), sobre cómo sustituir una fila o una columna: para modificar una fila completa, primero va el número de fila y luego dos puntos; para modificar una columna completa, primero los dos puntos y después el número de columna:

result(fila, :)= filaImpar;

result(:, columna)= columnaImpar;

Figura 59. Sustitución de una fila (número, dos puntos) y de una columna (dos puntos, columna)

• Solución 7.

Una última solución consiste en inicializar la matriz a ceros (o a unos) y recorrer después las nxn casillas de la matriz, colocando un 1 (o un 0 según corresponda): el 1 se pone en las casillas cuya suma de fila y columna sea par.

Macario Polo Usaola

80

function result = alternar7(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=zeros(n); for fila=1:n for columna=1:n if mod(fila+columna, 2)==0 result(fila, columna)=1 end end end end Función 73. Unos y ceros alternados (VII): colocamos un 1 en las casillas cuyas fila y columna suman par

La versión en la que colocamos 0 en vez de 1 necesita dos cambios: primero, inicializar la matriz a 1 (marcado en amarillo) y luego colocar el 0 en las casillas cuya suma de fila y columna sea non (morado):

function result = alternar8(n) if mod(n, 2)~=0 disp('n debe ser par'); end result=ones(n); for fila=1:n for columna=1:n if mod(fila+columna, 2)==1 result(fila, columna)=0; end end end end Función 74. Unos y ceros alternados (VIII): colocamos un 0 en las casillas cuyas fila y columna suman impar


81

Ejercicio 28. Matriz de Vandermonde

Vandermonde. Escribir una función que reciba como parámetro un vector v y un entero n y devuelva la matriz de Vandermonde de n columnas. El vector v representa los valores de la segunda columna.

Por ejemplo, si v=[1 2 3 4] y n=5, la matriz de Vandermonde tiene los valores de v en la segunda columna, y n columnas en total:

1! !! 1! 1! 1!2! !! 2! 2! 2!3! !! 3! 3! 3!4! !! 4! 4! 4!

• Solución 1.

Antes de abordar la solución, observamos que la primera columna es la segunda con todos sus elementos elevados a 0; la segunda es el vector pasado con todos sus elementos elevados a 1; la tercera columna es la segunda con todos los elementos elevados a dos; etcétera. Es decir, en cada columna colocamos la segunda columna con sus elementos elevados al número columna menos 1.

En MATLAB podemos operar con todos los elementos de un vector o de una matriz de manera muy cómoda. Supongamos que v=[1 2 3 4]. Si queremos obtener el vector [15 25 35 45], hacemos lo siguiente:

>> v v = 1 2 3 4

>> v.^5 ans = 1 32 243 1024

Figura 60. En el lado derecho obtenemos el vector v de la izquierda, con todos sus valores elevados a 5

Nótese, en la figura anterior, el punto antes del símbolo de potencia: el símbolo punto indica que la operación afecta a todos los elementos del vector.

Con un sencillo bucle for podemos iterar con un variable col desde 1 hasta n, añadiendo en cada iteración el vector v elevado a col-‐1:

function result = vandermonde1(v, n) result=[]; for col=1:n result(:, col)=v.^(col-1); end end Función 75. Matriz de Vandermonde rellenando columna a columna

El resultado para el ejemplo anterior es:

Macario Polo Usaola

82

>> v v = 1 2 3 4 >> vandermonde1(v, 5) ans = 1 1 1 1 1 1 2 4 8 16 1 3 9 27 81 1 4 16 64 256 Figura 61

• Solución 2.

Otra manera de conseguir el mismo resultado es rellenar la matriz por filas: estando en la fila i, el valor que corresponde a una cierta columna es el valor i-‐ésimo del vector v, elevado a la columna de que se trate menos 1. Es decir:

function result = vandermonde2(v, n) result=[]; for fila=1:length(v) for col=1:n result(fila, col)=v(fila)^(col-1); end end end Función 76. Matriz de Vandermonde rellenando por filas


83

Ejercicio 29. Matriz de Fibonacci

Escribir una función que, tomando como parámetro un número entero n, devuelva una matriz de dimensión n×n que contenga de forma ordenada los n*n primeros términos de la serie de Fibonacci.

Para n=3, por ejemplo:

! ! !! ! !!" !" !"

• Solución 1.

En una primera solución, recorremos todas las posiciones de la matriz con dos bucles for anidados. Por cada iteración vamos incrementando un contador, que utilizamos para calcular el valor que corresponda. Podemos utilizar cualquiera de las funciones de Fibonacci que implementamos en ejercicios anteriores:

function result = matrizFibonacci1(n) result=[]; contador=1; for fila=1:n for col=1:n result(fila, col)=fib(contador); contador=contador+1; end end end Función 77. Matriz de Fibonacci, utilizando una función auxiliar

Dos ejemplos del resultado son:

>> matrizFibonacci1(3) ans = 1 1 2 3 5 8 13 21 34

>> matrizFibonacci1(5) ans = 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025

Figura 62

• Solución 2.

Otra forma de resolver el ejercicio es ir colocando, en cada posición de la matriz, la suma de los dos valores anteriores. Hacer esto con un vector es sencillo (ya lo resolvimos en el Ejercicio 11, página 31). Hacerlo con una matriz tiene una pequeña dificultad adicional, ya que hay que tener en cuenta los finales de fila.

Macario Polo Usaola

84

En el siguiente código, inicializamos primero las dos primeras columnas de la primera fila; luego, completamos la primera fila en el primer bucle for. A continuación, recorremos desde la fila 2 hasta la n: en las columnas 1 y 2 de estas filas tenemos la precaución de leer valores de la fila anterior; en las restantes, leemos los dos valores inmediatamente anteriores de la misma columna.

function result = matrizFibonacci2(n) result=[]; result(1, 1)=1; result(1, 2)=1; for col=3:n result(1, col)=result(1, col-2)+result(1, col-1); end for fila=2:n for col=1:n if col==1 result(fila, 1)=result(fila-1, n-1)+result(fila-1, n); elseif col==2 result(fila, 2)=result(fila-1, n)+result(fila, col-1) else result(fila, col)=result(fila, col-2)+result(fila, col-1); end end end end Función 78. Matriz de Fibonacci, computada mediante la suma de las dos posiciones anteriores (I)

• Solución 3.

En una solución parecida a la anterior, pero algo más sencilla, eliminamos los dos if y, en lugar de comenzar el bucle anidado en col=1, lo empezamos en col=3:

function result = matrizFibonacci3(n) result=[]; result(1, 1)=1; result(1, 2)=1; for col=3:n result(1, col)=result(1, col-2)+result(1, col-1); end for fila=2:n result(fila, 1)=result(fila-1, n-1)+result(fila-1, n); result(fila, 2)=result(fila-1, n)+result(fila, 1); for col=3:n result(fila, col)=result(fila, col-2)+ result(fila, col-1); end end end Función 79. Matriz de Fibonacci, computada mediante la suma de las dos posiciones anteriores (II)


85

Ejercicio 30. Producto de matrices.

Escribir una función en MATLAB que calcule el producto de dos matrices.

• Solución 1.

MATLAB ya dispone del operador * para multiplicar matrices directamente. Obviamente, lo que nos piden es la escritura de una función que multiplique dos matrices sin utilizar ese operador.

Veamos cómo lo hacemos a mano, asumiendo una matriz A de nxm y otra B de mxn:

!!! !!" … !!!!!" !!! … !!!… … … …!!! !!! … !!"

·

!!! !!" … !!!!!" !!! … !!!… … … …!!! !!! … !!"

Siendo R la matriz resultado, sus dos primeras posiciones son:

R11=a11·b11+a12*b21+…+a1n*bn1

R12=a11·b12+a12*b22+…+a1n*bn2

En general, en la posición Rij va la suma de los productos de Mij por Nji. Necesitaremos tres bucles: uno que recorra las filas de M, otro que recorra las columnas de N y otro más que se encargue de multiplicar los elementos de la fila y columna considera y de acumular el resultado para colocarlo en la posición i, j:

function R = productoDeMatrices(M, N) columnasM=length(M(1, :)); filasM=length(M(:, 1)); columnasN=length(N(1, :)); R=zeros(filasM, columnasN); for i=1:filasM for j=1:columnasN for k=1:columnasM R(i, j)=R(i, j)+M(i, k)*N(k, j); end end end end Función 80. Multiplicación de dos matrices

Podemos comprobar que la función está bien hecha pidiéndole a MATLAB que nos diga si todos los elementos de la matriz R coinciden con todos los elementos que MATLAB calcula para M*N: en la figura siguiente mostramos dos matrices M y N; más abajo, los resultados de ejecutar nuestra función (izquierda) y de ejecutar la función de multiplicación de matrices de MATLAB (M*N); en la fila inferior, le pedimos a MATLAB que compare los dos resultados utilizando el operador de

Macario Polo Usaola

86

comparación (==): el resultado (una matriz de unos) indica que ambas matrices son iguales y que, por tanto, hemos implementado bien el código de la función.

>> M M = 1 4 7 10 2 5 8 11 3 6 9 12

>> N N = 1 2 3 4 5 6 7 8 9 10 11 12

>> productoDeMatrices(M, N) ans = 166 188 210 188 214 240 210 240 270

>> M*N ans = 166 188 210 188 214 240 210 240 270

>> productoDeMatrices(M, N)==M*N ans = 1 1 1 1 1 1 1 1 1 Figura 63

• Solución 2.

Podemos modificar un poco el código anterior: una vez que tenemos la fila de M (y que guardamos, por ejemplo, en un vector llamado filaDeM) y la columna de N (que guardamos en columnaDeN), podemos hacer directamente el producto de ambos vectores:

function R = productoDeMatrices2(M, N) filasM=length(M(:, 1)); columnasN=length(N(1, :)); R=zeros(filasM, columnasN); for i=1:filasM filaDeM=M(i, :); for j=1:columnasN columnaDeN=N(:, j); R(i, j)=filaDeM*columnaDeN; end end end Función 81. Multiplicación de matrices aprovechando el producto vectorial


87

Ejercicio 31. Triángulo de Tartaglia

Escribir una función que tome un parámetro n y construya una matriz con el triángulo de Tartaglia de dimensión n.

Por ejemplo, para n=4, la matriz que se espera es:

1 2 3 4 1 1 0 0 0 2 1 1 0 0 3 1 2 1 0 4 1 3 2 1

• Solución 1.

En primer lugar, construimos una matriz de nxn llena de ceros. Luego, colocamos 1 en la primera columna. Después, para cada columna desde 2 hasta n, colocamos en cada casilla el valor que haya en la fila superior. Por ejemplo, ubicados en la segunda columna y segunda fila (marcada a continuación en amarillo), colocamos en esa posición el valor que tiene encima más 1.

1 2 3 4 1 1 0 0 0 2 1 0 0 0 3 1 0 0 0 4 1 0 0 0

De este modo, la matriz quedará de la siguiente manera:

1 2 3 4 1 1 0 0 0 2 1 1 0 0 3 1 0 0 0 4 1 0 0 0

A continuación, bajamos a la celda resaltada a continuación en amarillo y, en ella, colocamos el 1 que tiene encima más 1:

1 2 3 4 1 1 0 0 0 2 1 1 0 0 3 1 2 0 0 4 1 0 0 0

Continuamos de esa manera hasta llegar a la última fila. Luego, pasamos a la columna 3 y a la fila 3. Proseguimos de la misma manera hasta recorrer todas las columnas:

Macario Polo Usaola

88

function result = tartaglia1( n) result=zeros(n); result(:, 1)=ones(n, 1); for col=2:n for fila=col:n result(fila, col)=result(fila-1, col)+1; end end end Función 82. Una solución para el triángulo de Tartaglia, rellenando por columnas

• Solución 2.

Podemos partir también de una matriz identidad con la primera columna a 1. Por ejemplo:

1 2 3 4 5 1 1 0 0 0 0 2 1 1 0 0 0 3 1 0 1 0 0 4 1 0 0 1 0 5 1 0 0 0 1

Para completar esta matriz basta con comenzar por la fila 3. Además, para completar cada fila empezaremos en la columna 2 y llegaremos hasta la columna que coincida con la fila-‐1: en la fila 4, por ejemplo, ponemos valores desde la columna 2 hasta la columna 3; en la fila 5, desde la 2 hasta la 4.

Con esta idea, podemos rellenar exactamente de la misma manera que antes:

function result = tartaglia2( n) result=eye(n); result(:, 1)=ones(n, 1); for fila=3:n for col=2:fila-1 result(fila, col)=result(fila-1, col)+1; end end end Función 83. El triángulo de Tartaglia, rellenando ahora por filas

• Solución 3.

Podemos rellenar la matriz de otra manera. Si nos fijamos, por ejemplo, en la fila 5, el primer valor que debemos colocar en la columna 2 es el número de fila-‐1; el siguiente, en la columna 3, es el número de fila-‐2; luego, en la columna 4, el número de fila-‐3: en general, colocamos el número de fila menos el número de columna decrementado en 1.


89

1 2 3 4 5 1 1 0 0 0 0 2 1 1 0 0 0 3 1 3-‐(2-‐1) 1 0 0 4 1 4-‐(2-‐1) 4-‐(3-‐1) 1 0 5 1 5-‐(2-‐1) 5-‐(3-‐1) 5-‐(4-‐1) 1

En otras palabras:

function result = tartaglia3( n) result=eye(n); result(:, 1)=ones(n, 1); for fila=3:n for col=2:fila-1 result(fila, col)=fila-(col-1); end end end Función 84. El triángulo de Tartaglia, rellenando de otra manera

Macario Polo Usaola

90

Ejercicio 32. Triángulo equilátero

Escribir una función que, dado un parámetro n, devuelva una matriz formada por asteriscos que formen un triángulo equilátero.

Por ejemplo, para n=4 y n=5, las figuras son:

1 2 3 4 5 6 7 1 * 2 * * * 3 * * * * * 4 * * * * * * *

1 2 3 4 5 6 7 8 9 1 * 2 * * * 3 * * * * * 4 * * * * * * * 5 * * * * * * * * *

• Solución 1.

Fijándonos en las figuras anteriores, observamos que n representa, por un lado, el número de filas de la matriz; por otro, el número de la columna central; además, la matriz tiene 2·n-‐1 columnas.

Cada fila está formada por un número decreciente de espacios en blanco, un número creciente de asteriscos y, otra vez, un número decreciente de espacios en blanco. Si observamos la siguiente figura, vemos que, en cada fila, hay dos bloques de n-‐fila blancos y, entre ambos bloques, asteriscos hasta completar la anchura (si la anchura es 2n-‐1 y hay dos bloques de n-‐fila blancos, hay 2·(n-‐fila) blancos), con lo que el número de asteriscos es (2n-‐1)-‐2·(n-‐fila).

1 2 3 4 5 6 7 8 9 1 * n-‐1 blancos, 1 asterisco, n-‐1 blancos 2 * * * n-‐2 blancos, 3 asteriscos, n-‐2 blancos 3 * * * * * n-‐3 blancos, 5 asteriscos, n-‐3 blancos 4 * * * * * * * n-‐4 blancos, 7 asteriscos, n-‐4 blancos 5 * * * * * * * * * n-‐5 blancos, 9 asteriscos, n-‐5 blancos Anchura=2·n-‐1

Es decir, que cada fila la construimos escribiendo n-‐fila blancos desde la columna 1. Luego, escribimos asteriscos desde la columna siguiente (n-‐fila+1) hasta la columna n-‐fila+1+(2n-‐1)-‐2·(n-‐fila)-‐1. Finalmente, escribimos blancos.

Tenemos muchas formas de solucionar el ejercicio. Lo que haremos en primer lugar será construir una matriz de nx(2n-‐1) asteriscos y, luego, poner los blancos que correspondan en cada fila:


91

function result = trianguloEquilatero1(n) result=char(n, 2*n-1); for fila=1:n for col=1:2*n-1 result(fila, col)='*'; end end for fila=1:n for col=1:n-fila result(fila, col)=' '; end for col=n-fila+1+(2*n-1)-2*(n-fila):2*n-1 result(fila, col)=' '; end end end Función 85. El triángulo equilátero, sustituyendo asteriscos por espacios en blanco.

Hagamos una traza parcial para n=4:

Comentarios fila col n-‐fila n-‐fila+1+(2*n-‐1)-‐2*(n-‐fila)

result

Dimensionamos el resultado como una matriz de nx(2n-‐1) caracteres y la rellenamos de asteriscos en el primer for

1 2 3 4 5 6 7 1 * * * * * * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

Entramos en el bucle resaltado en amarillo en la Función 85

1 1 3 1 2 3 4 5 6 7 1 * * * * * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

1 2 3 1 2 3 4 5 6 7 1 * * * * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

1 3 3 1 2 3 4 5 6 7 1 * * * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

Macario Polo Usaola

92

Comentarios fila col n-‐fila n-‐fila+1+(2*n-‐1)-‐2*(n-‐fila)

result

Llegamos al bucle verde

1 5 4-‐1+1+(2*4-‐1)-‐2*(4-‐1)=5

1 2 3 4 5 6 7 1 * * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

1 6 5 1 2 3 4 5 6 7 1 * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

1 7 5 1 2 3 4 5 6 7 1 * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * *

Hemos recorrido los bucles amarillo y verde para fila=1. Se incrementa fila para procesar la fila 2. Entramos de nuevo en el bucle amarillo

2 1 2 1 2 3 4 5 6 7 1 * 2 * * * * * * 3 * * * * * * * 4 * * * * * * *

2 2 2 1 2 3 4 5 6 7 1 * 2 * * * * * 3 * * * * * * * 4 * * * * * * *

Y se continúa de esta manera con todas las filas Figura 64. Traza parcial de la Función 85

• Solución 2.

En otra posible solución, partimos de una matriz de blancos y colocamos asteriscos en las posiciones que correspondan:


93

function result = trianguloEquilatero2(n) result=char(n, 2*n-1); for fila=1:n for col=n-fila+1:n-fila+1+(2*n-1)-2*(n-fila)-1 result(fila, col)='*'; end end end Función 86. El triángulo equilátero, colocando asteriscos por filas

• Solución 3.

Podemos analizar el problema por columnas en lugar de por filas. Para n=5, observamos que en la columna 1 hay 1 asterisco abajo del todo; en la 2, 2 asteriscos abajo del todo; llegamos así hasta la columna 5, en la que hay 5 asteriscos. En la 6 hay 4; en la 7, 3; en la 8, 2; y en la 9, 1.

1 2 3 4 5 6 7 8 9 1 * 2 * * * 3 * * * * * 4 * * * * * * * 5 * * * * * * * * *

En la siguiente función, construimos la matriz de caracteres y, con objeto de apreciar mejor el resultado, la rellenamos con guiones en lugar de con blancos. A continuación, en el bucle amarillo, construimos una variable hilera que usaremos para almacenar el contenido de cada columna. A continuación, recorremos la matriz desde las columnas 1 a n y colocamos en hilera los asteriscos que hagan falta para la columna que corresponda (bucle verde). Por último, colocamos la hilera recién formada en la columna izquierda (col) y en su simétrica derecha (2*n-‐col):

Macario Polo Usaola

94

function result = trianguloEquilatero3(n) result=char(n, 2*n-1); for fila=1:n for col=1:2*n-1 result(fila, col)='-'; end end hilera=char(n); for fila=1:n hilera(fila)='-'; end for col=1:n for fila=n:-1:n-col+1 hilera(fila)='*'; end result(:, col)=hilera; result(:, 2*n-col)=hilera; end end Función 87. El triángulo equilátero, colocando asteriscos por columnas

Dos resultados de ejemplo son los siguientes:

>> trianguloEquilatero3(5) ans = ----*---- ---***--- --*****-- -*******- *********

>> trianguloEquilatero3(10) ans = ---------*--------- --------***-------- -------*****------- ------*******------ -----*********----- ----***********---- ---*************--- --***************-- -*****************- *******************

Figura 65


95

Ejercicio 33. Matriz triangular superior

Escribir una función tome como parámetro un número n y devuelva una matriz de nxn, triangular superior, con la siguiente forma:

! ! ! … !! ! ! … !− !! ! ! … !− !! ! ! … …! ! ! ! !! ! ! ! !

• Solución 1.

Podemos partir de una matriz identidad. Luego, en cada fila, recorremos desde la columna fila+1 hasta la columna n, colocando en cada casilla el número que tenga a la izquierda incrementado en 1:

function result = triangularSuperior1(n) result=eye(n); for fila=1:n for col=fila+1:n result(fila, col)=result(fila, col-1)+1; end end end Función 88. Matriz triangular superior, rellenando por filas y empezando con una matriz identidad

Y el resultado es:

>> triangularSuperior1(5) ans = 1 2 3 4 5 0 1 2 3 4 0 0 1 2 3 0 0 0 1 2 0 0 0 0 1 Figura 66

• Solución 2.

También podemos partir de una matriz de ceros y rellenar cada fila de forma parecida: en cada fila, empezaremos en la columna fila desde 1 hasta n. El código, en principio, podría ser el siguiente:

Macario Polo Usaola

96

function result = triangularSuperior2(n) result=zeros(n); for fila=1:n for col=fila:n result(fila, col)=result(fila, col-1)+1; end end end Función 89. Solución incorrecta para la matriz triangular superior

Al ejecutar la Función 89, sin embargo, encontramos un error:

>> triangularSuperior2(5) ??? Attempted to access result(1,0); index must be a positive integer or logical. Error in ==> triangularSuperior2 at 7 result(fila, col)=result(fila, col-‐1)+1; Figura 67. Mensaje de error obtenido al ejecutar la Función 89

El error se produce la primera vez que se intenta acceder al elemento result(fila, col-‐1): en este momento, col=1 y, claramente, col-‐1=0, con lo que el elemento que tratamos de recuperar es result(1, 0), que está fuera de los límites de la matriz.

Una forma de arreglar el problema es rellenar de manera separada la primera fila y, luego, continuar desde la fila 2 hasta la n:

function result = triangularSuperior2(n) result=zeros(n); for col=1:n result(1, col)=col; end for fila=2:n for col=fila:n result(fila, col)=result(fila, col-1)+1; end end end Función 90. La función anterior, ahora sin el error

• Solución 3.

También podemos rellenar por columnas: partiendo de una matriz de ceros, el primer valor de cada columna es el propio número de columna. Para completar la columna, vamos decrementando el valor hasta llegar a 0. Es decir:


97

function result = triangularSuperior3(n) result=zeros(n); for col=1:n valor=col; for fila=1:col result(fila, col)=valor; valor=valor-1; end end end Función 91. Matriz triangular superior, rellenando por columnas

• Solución 4.

En una forma más de solucionarlo, completamos primero la primera fila y luego recorremos todas las columnas desde la fila 2. En cada posición, colocamos el valor que haya encima menos 1:

function result = triangularSuperior4(n) result=zeros(n); for col=1:n result(1, col)=col; end for col=1:n for fila=2:col result(fila, col)=result(fila-1, col)-1; end end end Función 92. Matriz triangular superior, rellenando por columnas tras rellenar antes la primera fila

• Solución 5.

Quizá la solución más sencilla sea la siguiente: si nos fijamos, el valor que aparece en cada casilla del triángulo superior es la diferencia entre el número de columna y el número de fila más 1:

1 2 3 4 5 1 2-‐1+1 2 4-‐2+1 3 3-‐3+1 4 5

Por tanto:

Macario Polo Usaola

98

function r=triangularSuperior5(n) r=[]; for fila=1:n for col=fila:n r(fila, col)=col-fila+1; end end end Función 93. Una solución sencilla para la Matriz triangular superior


99

Ejercicio 34. Diagonales que se incrementan (I)

Escribir una función que construya una matriz de nxn cuya diagonal principal esté formada por unos, y el resto de diagonales están formadas por su distancia a la diagonal principal.

Por ejemplo, para n=5:

! ! ! ! !! ! ! ! !! ! ! ! !! ! ! ! !! ! ! ! !

• Solución 1.

Este ejercicio es una generalización del anterior: ahora se trata de rellenar no sólo el triángulo superior, sino también el inferior. Partiendo de la última solución dada al ejercicio de la matriz triangular superior, el valor que debemos colocar en cada casilla es abs(col-‐fila)+1:

function r=diagonalesQueSeIncrementan1(n) r=[]; for fila=1:n for col=1:n r(fila, col)=abs(col-fila)+1; end end end Función 94

• Solución 2.

Podemos hacerlo también más complicado: en la primera columna, colocamos los números desde 1 empezando en la fila 1 y terminando en la fila n; en la segunda, colocamos los números desde 1 empezando en la fila 2 (el mismo número que la columna) y llegando hasta la fila n. De esta manera completamos el triángulo inferior:

function r=triangularInferior1(n) r=[]; for col=1:n valor=1; for fila=col:n r(fila, col)=valor; valor=valor+1; end end end Función 95. Fragmento de código para rellenar por columnas el triángulo inferior

Efectivamente, si ejecutamos obtenemos el siguiente resultado:

Macario Polo Usaola

100

>> diagonalesQueSeIncrementan2(8) ans = 1 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 3 2 1 0 0 0 0 0 4 3 2 1 0 0 0 0 5 4 3 2 1 0 0 0 6 5 4 3 2 1 0 0 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 Figura 68. Al ejecutar el código de la Función 95, obtenemos el triángulo inferior

Para completar el resto, nos podemos fijar en algunas de las soluciones dadas al Ejercicio 33 y completar el código:

function r=diagonalesQueSeIncrementan2(n) r=[]; for col=1:n valor=1; for fila=col:n r(fila, col)=valor; valor=valor+1; end end for fila=1:n for col=fila+1:n r(fila, col)=r(fila, col-1)+1; end end end Función 96. La Función 95, completada para que se rellene el triángulo superior

• Solución 3.

Del ejercicio anterior tenemos varias funciones para construir la matriz triangular superior, y con la Función 95 construimos la triangular inferior. Podemos combinar los resultados de ambas funciones en una sola matriz: lo que haremos será tomar, de cada matriz, el máximo valor de la misma posición:

Triangular superior Triangular inferior 1 2 3 4 5 1 0 0 0 0 0 1 2 3 4 2 1 0 0 0 0 0 1 2 3 3 2 1 0 0 0 0 0 1 2 4 3 2 1 0 0 0 0 0 1 5 4 3 2 1

Esto es lo que hacemos en la función siguiente mediante la función max de MATLAB:


101

function r=diagonalesQueSeIncrementan3(n) r=max(triangularInferior1(n), triangularSuperior1(n)); end Función 97. Construcción de la matriz pedida a partir de las dos triangulares

Macario Polo Usaola

102

Ejercicio 35. Diagonales que se incrementan (II)

Escribir una función que construya una matriz de nxn cuya diagonal principal esté formada por los valores pasados en un parámetro m, y el resto de diagonales están formadas por su distancia a la diagonal principal más m.

Por ejemplo, para n=5 y m=6:

! ! ! ! !"! ! ! ! !! ! ! ! !! ! ! ! !!" ! ! ! !

• Solución 1.

Partiendo de cualquiera de las soluciones dadas al ejercicio anterior, lo único que tenemos que hacer es recorrer la matriz obtenida y sumar, a cada casilla, el valor de m-‐1. Por ejemplo, para n=5 y m=6:

1 2 3 4 5 1+6-‐1 2+6-‐1 3+6-‐1 4+6-‐1 5+6-‐1 2 1 2 3 4 2+6-‐1 1+6-‐1 2+6-‐1 3+6-‐1 4+6-‐1 3 2 1 2 3 3+6-‐1 2+6-‐1 1+6-‐1 2+6-‐1 3+6-‐1 4 3 2 1 2 4+6-‐1 3+6-‐1 2+6-‐1 1+6-‐1 2+6-‐1 5 4 3 2 1 5+6-‐1 4+6-‐1 3+6-‐1 2+6-‐1 1+6-‐1

Una posible solución, en la que llamamos a la Función 94 (página 99), es:

function r=diagonalesQueSeIncrementanB1(n, m) r=diagonalesQueSeIncrementan1(n); for fila=1:n for col=1:n r(fila, col)=r(fila, col)+m-1; end end end Función 98


103

Ejercicio 36. Números ordenados

Escribir una función que tome un argumento n y devuelva una matriz de nxn con todos los números desde 1 hasta n2.


1 2 3 4 1 1 2 3 4 2 5 6 7 8 3 9 10 11 12 4 13 14 15 16

• Solución 1.

Con lo que ya sabemos, este ejercicio es prácticamente trivial. Por ejemplo, podemos recorrer todas las casillas con dos bucles anidados (uno para las filas y otro para las columnas), colocando en cada una un valor que vamos incrementando en cada iteración:

function r = numerosOrdenados1(n) r=zeros(n); valor=1; for fila=1:n for col=1:n r(fila, col)=valor; valor=valor+1; end end end Función 99

• Solución 2.

Otra solución algo más enrevesada es la siguiente: si nos fijamos, el primer número de cada columna es su número de columna. Luego, hacia abajo, van incrementando de n en n:

1 2 3 4 1 1 2 3 4 2 1+4 2+4 3+4 4+4 3 4

Esto es lo que hacemos en la solución siguiente: primero, llenamos en un bucle aparte la primera fila; luego, continuamos recorriendo cada columna a partir de la segunda fila, poniendo en cada posición el valor que tenga encima incrementado en n:

Macario Polo Usaola

104

function r = numerosOrdenados2(n) r=zeros(n); for col=1:n r(1, col)=col; end for col=1:n for fila=2:n r(fila, col)=r(fila-1, col)+n; end end end Función 100


105

Ejercicio 37. Números ordenados descendentemente

Escribir una función que tome un argumento n y devuelva una matriz de nxn con todos los números desde 1 hasta n2, ordenados de mayor a menor.


1 2 3 4 1 16 15 14 13 2 12 11 10 9 3 8 7 6 5 4 4 3 2 1

• Solución 1.

Reescribiremos la primera solución dada al ejercicio anterior. Ahora, el valor por el que arrancamos será n2 y lo iremos decrementando en cada iteración:

function r = numerosOrdenadosDescendentemente1(n) r=zeros(n); valor=n^2; for fila=1:n for col=1:n r(fila, col)=valor; valor=valor-1; end end end Función 101

• Solución 2.

Otra forma de hacerlo, parecida a la solución 2 del ejercicio anterior, es rellenar por columnas: primero completamos la última fila en un bucle aparte; luego, en cada columna, vamos desde la penúltima fila hasta la primera, colocando en cada posición el valor que tiene debajo más n:

function r = numerosOrdenadosDescendentemente2(n) r=zeros(n); for col=1:n r(n, col)=n-col+1; end for col=1:n for fila=n-1:-1:1 r(fila, col)=r(fila+1, col)+n; end end end Función 102

Macario Polo Usaola

106

Ejercicio 38. Zigzag

Escribir una función en MATLAB que devuelva una matriz de nxn con los número desde el 1 hasta n2 colocados en las filas en zigzag.


1 2 3 4 1 1 2 3 4 2 8 7 6 5 3 9 10 11 12 4 16 15 14 13

• Solución 1.

Si nos fijamos en la matriz de ejemplo, los valores en las filas impares son crecientes, y decrecientes en las pares. Podemos ir recorriendo la matriz por filas: si la fila es impar, recorremos sus casillas desde la columna 1 hasta la n; si es par, recorremos desde la n hasta la 1. En cada casilla, colocamos un valor que inicializamos a 1 y que vamos incrementando en cada iteración.

function r = zigzag(n) r=zeros(n); valor=1; for fila=1:n if mod(fila, 2)==1 for col=1:n r(fila, col)=valor; valor=valor+1; end else for col=n:-1:1 r(fila, col)=valor; valor=valor+1; end end end end Función 103


107

Ejercicio 39. Distancias

Escribir una función que construya una matriz de nxn, con n impar, en la que cada elemento es un número que representa la distancia al elemento central de la matriz. La distancia es la suma de las distancias en filas y columnas.


1 2 3 4 5 1 4 3 2 3 4 2 3 2 1 2 3 3 2 1 0 1 2 4 3 2 1 2 3 5 4 3 2 3 4

• Solución 1.

El ejercicio es muy sencillito: conociendo la fila y columna mitad (que es (n+1)/2), recorreremos todas las casillas colocando, como valor, la suma de su columna menos la mitad más la fila menos la mitad, ambas en valor absoluto:

function r = distancias1(n) r=zeros(n); mitad=(n+1)/2; for fila=1:n for col=1:n r(fila, col)=abs(fila-mitad)+abs(col-mitad); end end end Función 104

Y al ejecutar la función, obtenemos:

>> distancias1(5) ans = 4 3 2 3 4 3 2 1 2 3 2 1 0 1 2 3 2 1 2 3 4 3 2 3 4 Figura 69

• Solución 2.

Podemos resolverlo de otra manera: partiendo de la columna central ya rellena, podemos movernos por las de la izquierda (desde la mitad-‐1 hasta 1) y las de la derecha (desde mitad+1 hasta n): en las de la izquierda, colocamos el valor que

Macario Polo Usaola

108

tengan a la derecha más 1. Luego, en las de la derecha, colocamos el valor que tengan a la izquierda más 1:

1 2 3 4 5 1 2+1 2 2+1 2 1+1 1 1+1 3 0+1 0 0+1 4 1+1 1 1+1 5 2+1 2 2+1

La primera columna la podemos completar en dos partes: para la parte superior iremos desde 1 hasta mitad-‐1, colocando valores desde mitad-‐1 hasta 1 (bajando de 1 en 1); para la parte inferior, recorremos desde mitad+1 hasta n, colocando valores desde 1 hasta llegar a la fila n.

Con el siguiente fragmento de código rellenamos la columna central:

function r = distancias2(n) r=zeros(n); mitad=(n+1)/2; for fila=1:mitad-1 r(fila, mitad)=mitad-fila; end for fila=mitad+1:n r(fila, mitad)=fila-mitad; end end Función 105. Rellenamos la columna central mediante dos bucles

En efecto, el resultado para n=5 es:


Para completar la mitad izquierda añadimos un poco de código:


109

function r = distancias2(n) r=zeros(n); mitad=(n+1)/2; for fila=1:mitad-1 r(fila, mitad)=mitad-fila; end for fila=mitad+1:n r(fila, mitad)=fila-mitad; end for col=mitad-1:-1:1 for fila=1:n r(fila, col)=r(fila, col+1)+1; end end end Función 106. Completamos el código de la ¡Error! No se encuentra el origen de la referencia. para completar la mitad izquierda

El resultado, de momento, es el siguiente:


Y, ya por último, completamos con otro bucle para rellenar la mitad derecha:

Macario Polo Usaola

110

function r = distancias2(n) r=zeros(n); mitad=(n+1)/2; for fila=1:mitad-1 r(fila, mitad)=mitad-fila; end for fila=mitad+1:n r(fila, mitad)=fila-mitad; end for col=mitad-1:-1:1 for fila=1:n r(fila, col)=r(fila, col+1)+1; end end for col=mitad+1:n for fila=1:n r(fila, col)=r(fila, col-1)+1; end end end Función 107


111

Ejercicio 40. Distancia en letras

Escribir una función que construya una matriz de nxn, con n impar, en la que cada elemento es una letra que representa la distancia al elemento central de la matriz. La distancia es la suma de las distancias en filas y columnas. El cero se corresponde con la letra a, el 1 con la b, etcétera.


1 2 3 4 5 1 e d c d e 2 d c b c d 3 c b a b c 4 d c b c d 5 e d c d e

• Solución 1.

Para plantear la solución, debemos saber primero que cada carácter de los que manipula MATLAB tiene un número entero asociado (lo que se llama el código ASCII). Así, por ejemplo, las letras mayúsculas empiezan en el 65 (la A) y terminan en el 90 (la Z). Las minúsculas empiezan en la 97. El siguiente programa muestra los caracteres que corresponden a cada valor numérico:

function caracteres() for i=1:255 linea=[int2str(i), '-> ', char(i)]; disp(linea); end end Función 108. Programa para sacar la lista de códigos ASCII

En el código de arriba hemos resaltado la función char(i), que devuelve el carácter correspondiente al valor que se pasa como parámetro: así, por ejemplo, char(65) es ‘A’, y char(97)=’a’.

Para escribir el código que solucione este ejercicio procederemos de forma muy parecida al ejercicio anterior: ahora, sin embargo, en lugar de colocar números queremos colocar letras. El código de la función es muy parecido al de la Función 104 (página 107): la distancia de cada casilla al centro la guardamos en la variable distancia; luego, el valor que colocamos es el código ASCII correspondiente a esa distancia pero, como debemos empezar por la letra ‘a’ para representar el cero, le sumamos 97 (ya que char(97+0)=char(97)=’a’).

Macario Polo Usaola

112

function r = distanciaEnLetras1(n) r=char(n); mitad=(n+1)/2; for fila=1:n for col=1:n distancia=abs(fila-mitad)+abs(col-mitad); r(fila, col)=char(97+distancia); end end end Función 109


113

Ejercicio 41. Buscador de cadenas

Escribir una función en MATLAB que busque, en la cadena que se pasa como primer parámetro, la cadena que se pasa como segundo. La operación debe devolver un -‐1 si no la encuentra, o la posición en la que aparece.

Por ejemplo: encontrar(‘Problemas de MATLAB’, ‘MATLAB’) debe devolver 14.

• Solución 1.

MATLAB trata las cadenas de caracteres como vectores. Para el ejemplo anterior, se trata de buscar un subvector dentro de un vector.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P r o b l e m a s d e M A T L A B

Si el patrón que buscamos (‘MATLAB’, en el ejemplo) tiene 6 caracteres, el problema se reduce a extraer subvectores de 6 caracteres de la cadena grande empezando en la posición 1. Si lo encontramos en esa posición, devolvemos un 1; si no, avanzamos hasta la 2. Continuamos así hasta que lo encontremos o hasta que lleguemos a una posición desde la que no podamos leer 6 caracteres (es decir, la 15).

El ejercicio podemos resolverlo de la siguiente forma: en posicionFinal guardamos la posición del último carácter a partir del cual no podemos seguir buscando (14, en el ejemplo); luego, entramos a un while en el que permaneceremos hasta encontrar el patrón o hasta que, sin encontrarlo, lleguemos a la posicionFinal.

Dentro del bucle, vamos extrayendo subcadenas, desde la posición i, de la misma longitud que el patrón, y las comparamos con el patron. La comparación la hacemos con la función strcmp de MATLAB, que devuelve 1 si las dos cadenas que se pasan como parámetros son iguales y 0 en caso contrario.

function r = encontrar1(texto, patron) r=-1; i=1; posicionFinal=length(texto)-length(patron)+1; while (r==-1 && i<=posicionFinal) subcadena=texto(1, i:i+length(patron)-1); if strcmp(subcadena, patron)==1 r=i; end i=i+1; end end Función 110. Búsqueda de un patrón en una cadena

Una posible traza con el ejemplo anterior es:

Macario Polo Usaola

114

Comentario r i posFinal patron subcadena Antes del while -‐1 1 14 MATLAB Entramos al while -‐1 1 14 MATLAB Proble -‐1 2 14 MATLAB roblem -‐1 3 14 MATLAB oblema -‐1 4 14 MATLAB blemas Con – denotamos el espacio en blanco -‐1 5 14 MATLAB lemas-‐

-‐1 6 14 MATLAB emas-‐d -‐1 7 14 MATLAB mas-‐de -‐1 8 14 MATLAB as-‐de-‐ -‐1 9 14 MATLAB s-‐de-‐M -‐1 10 14 MATLAB -‐de-‐MA -‐1 11 14 MATLAB de-‐MAT -‐1 12 14 MATLAB e-‐MATL -‐1 13 14 MATLAB -‐MATLA strcmp devuelve 1, pues patron es igual a subcadena

14 14 14 MATLAB MATLAB

Figura 72. Traza de la Función 110


115

Ejercicio 42. Detección de palíndromos

Escribir una función que, tomando una cadena de caracteres como parámetro, devuelva un 1 si la cadena es un palíndromo, y 0 en caso contrario, sin considerar los espacios en blanco.

• Solución 1.

Consideremos el palíndromo de siete caracteres anilina:

1 2 3 4 5 6 7 a n i l i n a

La palabra es palíndromo porque el carácter 1 es igual al 7, el 2 igual al 6 y el 3 igual al 5. El carácter 4 no hace falta compararlo porque el número de caracteres de la palabra es impar y la ele queda en medio.

Para un palíndromo con un número par de letras, como erre, no hay carácter en el centro. El carácter 1 es igual al 4 y el 2 es igual al 3.

1 2 3 4 e r r e

Lo primero que haremos será quitar todos los espacios en blanco a la ristra de caracteres que le llegue a la función. Recorreremos la ristra original de principio a fin: si el carácter i-‐ésimo no es un espacio, lo añadimos a la ristra modificada; si sí lo es, pasamos al siguiente carácter sin añadirlo:

original 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P r o b l e m a s d e M A T L A B

sin espacios

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 P r o b l e m a s d e M A T L A B

El siguiente trozo de código realiza la función descrita: crea la variable auxiliar como un vector de caracteres; luego, recorre el texto original y, si el carácter no es una espacio, lo añade a auxiliar.

function r = palindromo1(texto) auxiliar=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) auxiliar(pos)=texto(i); pos=pos+1; end end auxiliar end Función 111. Primero eliminamos los espacios en blanco

Macario Polo Usaola

116

La línea resaltada en amarillo en el código anterior, en la que aparece la palabra “auxiliar” sin punto y coma al final, sirve para que MATLAB muestre por la consola el valor de esa variable:

>> texto texto = Problemas de MATLAB >> palindromo1(texto) auxiliar = ProblemasdeMATLAB Figura 73. Eliminamos los espacios del texto “Problemas de MATLAB”

Una vez preprocesada la cadena, recorreremos la primera mitad de la palabra e iremos comparando sus caracteres con los de la segunda mitad. Para una palabra de longitud par, la primera mitad va desde 1 hasta la longitud entre 2; para una de longitud impar, desde 1 hasta la parte entera de la mitad de la longitud: entonces, antes de comprobar si la cadena de caracteres es o no un palíndromo, calcularemos la posición de la cadena en la que termina la primera mitad, y a la que llamamos dondeParar:

function r = palindromo1(texto) auxiliar=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) auxiliar(pos)=texto(i); pos=pos+1; end end if mod(length(auxiliar), 2)==1 dondeParar=floor(length(auxiliar)/2); else dondeParar=length(auxiliar)/2; end dondeParar end Función 112. Al código de la Función 111 le añadimos unas líneas para conocer dónde parar la comprobación

Si ejecutamos con un par de ejemplos, obtenemos esto:


117

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 P r o b l e m a s d e M A T L A B

8 caracteres 8 caracteres >> texto texto = Problemas de MATLAB >> palindromo1(texto) dondeParar = 8

1 2 3 4 5 6 7 8 A B C D D C B A 4 caracteres 4 caracteres

>> palindromo1('ABCDDCBA') dondeParar = 4 Figura 74. Determinación de dondeParar en función de la longitud par o non de la cadena

Ahora, nos queda solamente completar el código para que se realice la comprobación: la función devolverá 1 o 0 según el texto pasado como parámetro sea o no, respectivamente, palíndromo. El resultado lo almacenamos en la variable r, que vale inicialmente 1 (línea resaltada en amarillo) y que ponemos a 0 en el momento en que detectamos dos caracteres no coincidentes (en el if resaltado en verde):

Macario Polo Usaola

118

function r = palindromo1(texto) auxiliar=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) auxiliar(pos)=texto(i); pos=pos+1; end end if mod(length(auxiliar), 2)==1 dondeParar=floor(length(auxiliar)/2); else dondeParar=length(auxiliar)/2; end r=1; for i=1:dondeParar caracterIzda=auxiliar(i); caracterDcha=auxiliar(length(auxiliar)-i+1); if caracterIzda~=caracterDcha r=0; end end end Función 113. Determinación de si el texto es o no palíndromo con un bucle for

Hagamos una traza de la función para ilustrar su funcionamiento. Supongamos que el texto pasado es Problemas de MATLAB, que ya ha sido preprocesado (con lo que auxiliar vale ProblemasdeMATLAB) y que dondeParar=8.

Comentarios dondeParar r i caracterIzda caracterDcha caracterIzda~=caracterDcha Estamos en la línea r=1

8 1

Entramos al bucle

8 1 1 P B

En el if marcado en verde. r se pone a 0

8 0 1 P B Falso

Reentramos en el bucle y comparamos en el if verde

8 0 2 r A Falso

» 8 0 3 o L Falso » 8 0 4 b T Falso » 8 0 5 l A Falso » 8 0 6 e M Falso » 8 0 7 m e Falso » 8 0 8 a d Falso

En este punto se alcanza la condición de parada del bucle, pues i=8=dondeParar. La función termina con r=0, que es el valor que se devuelve.

Si bien el código que hemos mostrado funciona, lo cierto es que puede modificarse para que sea más eficiente: en efecto, ya desde la primera comparación que


119

aparece en la tercera fila de la tabla se comprueba que el texto pasado no es palíndromo: es decir, desde el momento en que encontramos dos caracteres no coincidentes, ya podemos terminar la ejecución de la función devolviendo un cero.

• Solución 2.

Una forma de mejorar el rendimiento es forzar al código de la Función 113 a que termine en cuanto detecte una diferencia. Una forma de arreglarlo es incluyendo una sentencia return justamente después de la asignación r=0:

function r = palindromo2(texto) auxiliar=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) auxiliar(pos)=texto(i); pos=pos+1; end end if mod(length(auxiliar), 2)==1 dondeParar=floor(length(auxiliar)/2); else dondeParar=length(auxiliar)/2; end r=1; for i=1:dondeParar caracterIzda=auxiliar(i); caracterDcha=auxiliar(length(auxiliar)-i+1); if caracterIzda~=caracterDcha r=0; return; end end end Función 114. Adición de un return para provocar una “salida incondicional” de la función

Como en otros lenguajes, en cuanto MATLAB encuentra una instrucción return en la ejecución de una función, termina su ejecución y retorna el valor que corresponda (el de r, en el ejemplo, que es cero). Eso es lo que se llama una “salida incondicional” que, si lo deseamos, podemos evitarla pues, en cierto modo, viola los principios de la programación estructurada.

• Solución 3.

Para mejorar el rendimiento de la función, que pare en cuanto se sepa que el texto no es un palíndromo y evitar colocar, como hemos hecho en la última solución, una salida incondicional, sustituiremos el último bucle for de la Función 113 por otra estructura de control, de manera que la comparación de los caracteres se ejecute mientras los que se están comparando sean iguales.

Macario Polo Usaola

120

En la siguiente función, cambiamos el while

function r = palindromo2(texto) auxiliar=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) auxiliar(pos)=texto(i); pos=pos+1; end end if mod(length(auxiliar), 2)==1 dondeParar=floor(length(auxiliar)/2); else dondeParar=length(auxiliar)/2; end r=1; i=1; while i<=dondeParar && r==1 caracterIzda=auxiliar(i); caracterDcha=auxiliar(length(auxiliar)-i+1); if caracterIzda~=caracterDcha r=0; end i=i+1; end end Función 115. Sustituimos el último for de la Función 113 (página 118) por un while

• Solución 4.

Una forma más de solucionar el problema consiste en colocar la palabra original (que tenemos guardada, ya sin espacios, en una variable que, por ejemplo, se llame delDerecho), en otro vector, en el que la guardamos “dada la vuelta”, y por lo que lo llamaremos delReves:

1 2 3 4 5 6 7 8 delDerecho a n i l i n a s delReves s a n i l i n a

Luego, como hemos hecho antes, podemos ir comparando posición a posición con un for de principio a fin, con un for con un salto incondicional o con un while. También podemos, sin embargo, utilizar el operador == de MATLAB para comparar los dos vectores, que es lo que hacemos en la siguiente función:


121

function r = palindromo4(texto) delDerecho=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) delDerecho(pos)=texto(i); pos=pos+1; end end delReves=char(); for i=1:length(delDerecho) delReves(i)=delDerecho(length(delDerecho)-i+1); end delDerecho delReves r=delDerecho==delReves; end Función 116. Solución (incompleta) al problema del palíndromo mediante la comparación de dos vectores

En el código anterior, guardamos el texto original sin espacios en la variable delDerecho. Luego, en el bucle for resaltado, colcoamos en delReves el texto al revés. Después de este for aparecen, sin punto y coma al final, los nombres de las variables delDerecho delDerecho y delReves para que, con fines informativos, MATLAB nos muestre su valor. Finalmente, en la sentencia marcada en verde, asignamos a r el vector que resulta de comparar (con el operador ==) los dos vectores delDerecho y delReves.

En la figura siguiente aparecen dos ejemplos de uso de la función anterior: en amarillo la palabra (la de la izquierda es un palíndromo; la de la derecha, no); en verde, los valores de los vectores delDerecho y delReves; finalmente, en morado, el vector de 1 y 0 que resulta de comparar ambos vectores, posición a posición.

>> palindromo4('reconocer') delDerecho = reconocer delReves = reconocer ans = 1 1 1 1 1 1 1 1 1

>> palindromo4('dualidad') delDerecho = dualidad delReves = dadilaud ans = 1 0 0 0 0 0 0 1

Figura 75

Macario Polo Usaola

122

El texto pasado como parámetro será un palíndromo si la suma de los elementos del vector resultante (el que aparece en morado) es igual a la longitud del vector delDerecho (o delReves, daría igual). Por tanto, hacemos un pequeño cambio en las últimas líneas del código de la Función 116 y la dejamos de este modo:

function r = palindromo4(texto) delDerecho=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) delDerecho(pos)=texto(i); pos=pos+1; end end delReves=char(); for i=1:length(delDerecho) delReves(i)=delDerecho(length(delDerecho)-i+1); end r=delDerecho==delReves; if (sum(r)==length(delDerecho)) r=1; else r=0; end end Función 117. Modificación del código de la Función 116 para que se devuelva un 1 o un 0

En el trozo marcado en amarillo preguntamos si la suma de los elementos de r coincide con la longitud del vector con el texto sin espacios: en caso afirmativo, modificamos el valor de r para que valga 1; en caso negativo, lo modificamos también (hasta ahora era un vector de unos y ceros) para que valga cero.

Un cambio adicional, para que el código aparezca más compacto, es el que se muestra a continuación:

function r = palindromo4(texto) delDerecho=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) delDerecho(pos)=texto(i); pos=pos+1; end end delReves=char(); for i=1:length(delDerecho) delReves(i)=delDerecho(length(delDerecho)-i+1);


123

end r= (sum(delDerecho==delReves)==length(delDerecho)); end Función 118. Sustituimos varias líneas del final de la Función 117 por una sola

En la línea amarilla estamos asignando a r el resultado de comparar (==) la suma del vector resultante de, a su vez, comparar los vectores delDerecho y delReves con la longitud del vector delDerecho: básicamente, hacemos lo mismo que en las últimas líneas de la Función 117, pero en menos espacio:

1 2 3 4 5 6 7 8 9

delDerecho r e c o n o c e r delReves r e c o n o c e r

delDerecho==delReves 1 1 1 1 1 1 1 1 1

sum(delDerecho==delReves) 9 length(delDerecho) 9

r 1

• Solución 5. Con recursividad.

También podemos determinar recursivamente si un texto es o no un palíndromo mediante una función recursiva: en efecto, un texto es un palíndromo si su primera letra es igual a la última y lo que hay entre medias es un palíndromo. El caso se base se da cuando, para comparar, nos quede 1 o ningún carácter:

function r = palindromoRecursivo(texto) auxiliar=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) auxiliar(pos)=texto(i); pos=pos+1; end end if length(auxiliar)<=1 r=1; else if auxiliar(1)==auxiliar(length(auxiliar)) auxiliar=auxiliar(1, 2:length(auxiliar)-1); r=palindromoRecursivo(auxiliar); else r=0; end end end Figura 76. Determinación recursiva de los palíndromos

Macario Polo Usaola

124

Ejercicio 43. El monte

Un vector es un monte si su primera mitad es creciente, la segunda decreciente y, además, el vector es un palíndromo. Escribir una función que determine si el vector v que se pasa como parámetro es o no un monte.

• Solución 1.

Los dos vectores siguientes (de longitudes par e impar) son , según la definición anterior, montes:

1 2 3 4 5 6 7 8 a b c d d c b a

1 2 3 4 5 6 7 a b c d c b a

Muy resumidamente, podríamos escribir de la siguiente forma la expresión para determinar si un vector v es un monte:

esPalindromo(v) y estaOrdenado(mitad(v, ‘I’)) y estaOrdenado(alReves(mitad(v, ‘D’)))

En la expresión anterior, esPalindromo(v) devuelve 1 si el vector pasado es palíndromo y 0 en caso contrario (y puede ser cualquiera de las cuatro funciones que hemos implementado para el problema anterior); estaOrdenado(v) devuelve 1 si el vector v está ordenador y 0 en caso contrario; mitad(v, ‘I’) devuelve la mitad izquierda de v; mitad(v, ‘D’) devuelve la mitad derecha de v; alReves(v) devuelve el vector v al revés (el primer elemento en el último lugar, el segundo en el penúltimo… y el último en el primero): lo que estamos diciendo es que v es un monte si es palíndromo, si su mitad izquierda está ordenada y si su mitad derecha, al revés, está también ordenada.

Podemos traducir la expresión anterior directamente a una función MATLAB:

function r = monte(v) r=palindromo4(v) && estaOrdenado(mitad(v, 'I')) && estaOrdenado(alReves(mitad(v, 'D'))); end Función 119. Determinación de si un vector es o no un monte mediante la conjunción de funciones

Ahora falta, evidentemente, implementar las funciones estaOrdenado, mitad y alReves. La función para determinar si es palíndromo es la función palindromo4 (Función 118).

La función estaOrdenado es muy sencilla: recorremos el vector desde la posición 2 hasta el final: si, en algún momento, encontramos que el valor en la posición i+1 es menor que el valor de la posición i, entonces devolvemos un cero mediante una salida incondicional (véase Función 114, número 119); si llegamos al final del vector, entonces es porque el vector sí está ordenado y devolvemos un 1:


125

function r = estaOrdenado(v) r=1; for i=2:length(v) if v(i)<v(i-1) r=0; return; end end end Función 120. Determinamos si el vector está ordenado

La función mitad toma dos parámetros: el vector del que queremos extraer la mitad y un carácter que representa qué mitad queremos extraer: la izquierda (‘I’) o la derecha (‘D’):

function r = mitad(v, lado) if mod(length(v), 2)==0 pararEn=length(v)/2; else pararEn=floor(length(v)/2); end if lado=='D' pararEn=length(v)-pararEn+1; end r=[]; if lado=='I' for i=1:pararEn r=[r v(i)]; end else for i=length(v):-1:pararEn r=[v(i) r]; end end end Función 121. Extracción de la mitad izquierda o derecha de un vector

Finalmente, la función alReves coloca los elementos de un vector, en orden inverso, en otro vector:

function r = alReves(v) r=[]; for i=length(v):-1:1 r(length(v)-i+1)=v(i); end end Función 122. Colocación, al revés, de los elementos de un vector

De este modo, la ejecución de la función da los siguientes resultados para los ejemplos que se muestran:

Macario Polo Usaola

126

>> v=[1 2 3 4 3 2] % No es un palíndromo v = 1 2 3 4 3 2 >> monte(v) ans = 0

>> v=[1 2 1 4 3 2] % No está ordenada la mitad izquierda v = 1 2 1 4 3 2 >> monte(v) ans = 0

>> v=[1 2 3 4 3 5] % No es un palíndromo y no está ordenada la mitad derecha v = 1 2 3 4 3 5 >> monte(v) ans = 0

>> v=[1 2 3 4 3 2 1] % Es un monte v = 1 2 3 4 3 2 1 >> monte(v) ans = 1

Figura 77. Algunos ejemplos de ejecución de la función monte (Función 119, página 124)

• Solución 2.

Si observamos los ejemplos anteriores, nos damos cuenta de que, en realidad, para determinar si un vector es un monte basta con comprobar si es un palíndromo y si está ordenada su mitad izquierda pues, si ésta está ordenada y todo el vector es un palíndromo, forzosamente la mitad derecha estará ordenada de manera decreciente. Es decir, que a la conjunción de funciones que escribíamos en la Función 119 (página 124) le podemos quitar la última llamada:

function r = monte(v) r=palindromo4(v) && estaOrdenado(mitad(v, 'I')); % && estaOrdenado(alReves(mitad(v, 'D'))); end Función 123. No es necesario comprobar el orden en la mitad derecha

• Solución 3.

Supongamos ahora que queremos saber los motivos por los que el vector no es un monte: puede ser que no sea un palíndromo o sus dos mitades no estén ordenadas. En este caso, deberíamos añadir alguna instrucción para que se muestren los correspondientes mensajes.

Las funciones palindromo4 (que es la que utilizamos) y estaOrdenado quedan como sigue:


127

function r = palindromo4(texto) delDerecho=char(); pos=1; for i=1:length(texto) if (~isspace(texto(i))) delDerecho(pos)=texto(i); pos=pos+1; end end delReves=char(); for i=1:length(delDerecho) delReves(i)=delDerecho(length(delDerecho)-i+1); end r= (sum(delDerecho==delReves)==length(delDerecho)); if r==0 disp('No es un monte porque:'); disp('-No es un palíndromo'); end end function r = estaOrdenado(v) r=1; for i=2:length(v) if v(i)<v(i-1) r=0; disp('-No está ordenado'); return; end end end

Función 124. Instrucciones adicionales para mostrar mensajes

Ahora, al ejecutar la función monte (Función 123) con el vector v=[1 2 1 4 3 2], esperamos que nos diga que no es un monte porque no es un palíndromo y además no está ordenado. Sin embargo, al ejecutarla con ese ejemplo, el resultado es:

>> v=[1 2 1 4 3 2] v = 1 2 1 4 3 2 >> monte(v) No es un monte porque: -‐No es un palíndromo ans = 0 Figura 78

Macario Polo Usaola

128

Como vemos, se nos da sólo uno de los dos mensajes que esperábamos. Esto sucede porque, en la Función 123, las llamadas a palindromo4 y a estaOrdenado están separadas con &&: al usar estos dos símbolos para enlazar dos condiciones, MATLAB detiene la ejecución en el momento en que encuentra una falsa. En el ejemplo de v=[1 2 3 1 2 3], puesto que el vector no es un palíndromo, ya no se evalúa la segunda función, que determina el orden.

Para que se evalúen todas las condiciones debemos usar un solo &:

function r = monte(v) r=palindromo4(v) & estaOrdenado(mitad(v, 'I')); end Función 125. Con un solo ampersand, siempre se evalúan ambas funciones

Como se ve, los resultados son diferentes:

palindromo4(v) && estaOrdenado(mitad(v, 'I')); palindromo4(v) & estaOrdenado(mitad(v, 'I')); >> v v = 1 2 1 4 3 2 >> monte(v) No es un monte porque: -‐No es un palíndromo ans = 0

>> v v = 1 2 1 4 3 2 >> monte(v) No es un monte porque: -‐No es un palíndromo -‐No está ordenado ans = 0

Figura 79. Los resultados pueden ser diferentes según usemos & o &&


129

Ejercicio 44. Cálculo de pi (π)

Mediante el algoritmo de Montecarlo es posible calcular el valor aproximado de π. Partimos de una circunferencia de radio 1 inscrita en un cuadrado de lado 2. Para aproximar el valor de π, lanzamos un número grande de dardos aleatoriamente dentro del cuadrado. Al terminar el proceso, la proporción entre el número de dardos dentro del círculo y el número de dardos totales será aproximadamente igual a la ralción entre la superficie del círculo y la superficie del cuadrado. Puesto que conocemos la superficie del cuadrado (lado x lado = 2x2 = 4) y la expresión para calcular la del círculo (π·radio2=π·12), podemos despejar un valor aproximado para π.

totales

círculo

totales

círculo

totales

círculo

cuadrado

círculo

dardosdardosdardosdardos

dardosdardos

SS

·4

4

≈⇒

⇒≈⇒

⇒≈

π

π

Figura 80. Determinación del valor aproximado de π

Se pide la escritura de una función en MATLAB que tome como parámetro el número de dardos que se desea lanzar (n) y devuelva el valor calculado para π.

• Solución 1.

Conocido el valor de n, mediante un bucle for i=1:n simularemos el lanzamiento de los n dardos. Asumiendo que el centro del círculo (y del cuadrado) están en las coordenadas (0, 0), cada dardo caerá en dos coordenadas aleatorias (x, y), siendo cada valor de x y de y un número entre -‐1 y +1. Para determinar si un dardo ha caído dentro del círculo utilizaremos el teorema de pitágoras: si la suma de los cuadrados de x y de y es menor que la hipotenusa (que vale 1), el dardo está dentro, y fuera en otro caso.

La siguiente función es una posible solución: en ella, las coordenadas x e y de cada dardo se generan en las dos líneas marcadas en amarillo con la función rand(), que generan un número aleatorio entre 0 y 1; como se observa, multiplicamos x por signoX e y por signoY, que sirven para determinar si la coordenada respectiva es positiva o negativa (el signo se determina en función de que otro número aleatorio sea o no mayor que 0.5); a continuación comprobamos si la suma de sus cuadrados de x e y es menor o igual a 1 (if marcado en verde), caso en el que incrementamos la variable nd, que representa el número de disparos que han caído dentro del círculo. Al finalizar el bucle, calculamos el valor aproximado de π mediante la expresión de la Figura 80:

Macario Polo Usaola

130

function result=piMontecarlo(n) nd=0; result=0; for i=1:1:n if rand()<=0.5 signoX=-1; else signoX=+1; end if rand()<=0.5 signoY=-1; else signoY=+1; end x=rand()*signoX; y=rand()*signoY; if (x^2+y^2<=1) nd=nd+1; end end result=4*nd/n; end Función 126. Cálculo aproximado de π mediante el método de Montecarlo

Dos ejecuciones distintas de la función para n=100.000 nos dan los siguientes resultados:

>> piMontecarlo(100000) ans = 3.14316

>> piMontecarlo(100000) ans = 3.14436

Figura 81. Dos valores de π bastante aproximados al valor real

• Solución 2.

Puesto que, al determinar si el dardo está dentro o fuera elevamos al cuadrado las dos coordenadas del dardo (líneas en verde de la función anterior), no es preciso generar el signo, pues en la comparación la suma no será nunca un número negativo. Por tanto, el código puede simplificarse sin perder efectividad:


131

function result=piMontecarlo2(n) nd=0; result=0; for i=1:1:n x=rand(); y=rand(); if (x^2+y^2<=1) nd=nd+1; end end result=4*nd/n; end Función 127. La Función 126 puede simplificarse y no generar signos para las coordenadas

• Solución 3.

Además de calcular el valor aproximado de π, podemos hacer que MATLAB nos dibuje el círculo de radio 1 y los puntos que representan los lugares en que han caído los dardos. Para ello, usaremos la función plot(x, y), que dibuja un punto en las coordenadas que se pasan como parámetro, y una serie de instrucciones para que se dibuje el círculo. Modificamos el código de la primera solución que hemos dado a este ejercicio (Función 126, página 130).

function result=piMontecarlo3(n) nd=0; result=0; for i=1:1:n if rand()<=0.5 signoX=-1; else signoX=+1; end if rand()<=0.5 signoY=-1; else signoY=+1; end x=rand()*signoX; y=rand()*signoY; plot(x, y); hold on; if (x^2+y^2<=1) nd=nd+1; end end t=0:pi/30:2*pi; x=cos(t); y=sin(t); plot(x, y, 'red'); result=4*nd/n; end Función 128. Cálculo aproximado de π y su representación gráfica

Macario Polo Usaola

132

En el código anterio se marcan en amarillo las instrucciones plot y hold on. Ésta es necesaria para que todos los puntos se pinten en la misma ventana.

En azul aparecen tres líneas que utilizamos para dibujar un círculo rojo de radio 1: en la primera creamos un vector t con todos los valores desde 0 hasta 2π incrementando de π/30 en π/30. En la segunda creamos dos vectores x e y con, respectivamente, el coseno y el seno de cada valor almacenado en t. Finalmente, en la tercera dibujamos, en rojo (red) los vectores que acabamos de calcular y que tenemos almacenados en x e y.

El resultado por consola es:

>> piMontecarlo3(100000) ans = 3.14636 Figura 82

Y el resultado en la ventana gráfica, en la que se aprecian los cien mil puntos y la circunferencia en rojo es:

Figura 83. Representación de la circunferencia goniométrica y los 100.000 dardos lanzados


133

Ejercicio 45. La salida del laberinto

Disponemos de una matriz de nxm (que representa un laberinto) en la que hay valores cero y uno. Los valores uno representan muros y los valores cero representan zonas por las que puede caminarse. Se pide escribir una función en MATLAB que tome como parámetros una matriz que represente el laberinto, las coordenadas de la entrada y la de la salida, y que permita, mediante movimientos aleatorios de un objeto, llegar desde aquella hasta ésta.

La siguiente matriz (de la que se han omitido los ceros por claridad) representa un laberinto de 10x10, con la entrada en (10, 10) y la salida en (1,1):

1 2 3 4 5 6 7 8 9 10 1 S 1 1 2 1 1 1 1 1 3 1 1 1 4 1 1 1 1 1 5 1 6 1 1 1 1 1 1 7 1 1 8 1 1 1 1 1 9 1 10 1 E

• Solución 1.

El objeto móvil dispondrá en cada momento de unas coordenadas, que coincidirán al principio con las de la entrada y que se irán actualizando mientras no coincidan con las de la salida.

Cada movimiento del móvil lo generaremos con un número aleatorio que representará la dirección en la que el objeto se pueda mover: arriba, abajo, derecha e izquierda. Si, por ejemplo, la dirección es hacia arriba, el objeto no está en la fila 1 y la casilla de arriba está libre, entonces actualizamos la coordenada actual del objeto decrementando en 1 su fila. Procederemos de esta manera para las cuatro direcciones.

En la siguiente función, pasamos como parámetros el laberinto (en forma de una matriz de unos y ceros) y las coordenadas de entrada y salida (como sendos vectores con dos componentes). Al entrar a la función mostramos los valores de los parámetros y ponemos el cronómetro (función tic). En movimientos iremos guardando todos los movimientos realizados por el objeto, cuya coordenada actual la guardamos, en cada momento, en la variable coordenadaActual. Entonces, mientras la coordenada del objeto no coincida con la coordenada de la salida, generamos un número aleatorio entre 0 y 1 (mediante rand()) que almacenamos en la variable direccion. En función de su valor, comprobamos si está dentro de los límites del laberinto, calculamos la nueva coordenada (que guardamos en siguiente) sumando o restando una fila o columna a la coordenadaActual. Tras haber calculado la nueva posición, si ésta no coincide con un muro (es decir, la

Macario Polo Usaola

134

casilla en el laberinto es cero), actualizamos la coordenadaActual, almacenamos la nueva posición en el vector de movimientos y paramos el cronómetro para saber cuánto se ha tardado en encontrar la salida.

function [movimientos] = laberinto1( laberinto, entrada, salida ) entrada salida laberinto tic movimientos=[]; coordenadaActual=entrada; movimientos=[movimientos; coordenadaActual]; while (coordenadaActual(1)~=salida(1) || coordenadaActual(2)~=salida(2)) direccion=rand(); % <=0.25: arriba; <=0.5: derecha; % <=0.75: abajo; <=1: izquierda if direccion<=0.25 & coordenadaActual(1)>1 siguiente(1)=coordenadaActual(1)-1; siguiente(2)=coordenadaActual(2); elseif direccion<=0.5 & coordenadaActual(2)<length(laberinto) siguiente(1)=coordenadaActual(1); siguiente(2)=coordenadaActual(2)+1; elseif direccion<=0.75 & coordenadaActual(1)<length(laberinto(:, 1)) siguiente(1)=coordenadaActual(1)+1; siguiente(2)=coordenadaActual(2); elseif direccion<=1 & coordenadaActual(2)>1 siguiente(1)=coordenadaActual(1); siguiente(2)=coordenadaActual(2)-1; end if laberinto(siguiente(1), siguiente(2))==0 coordenadaActual=siguiente; movimientos=[movimientos; coordenadaActual]; end end toc end Función 129. Búsqueda aleatoria del camino de salida de un laberinto

Si ejecutamos la función con la siguiente línea de comando:

disp(['Solución alcanzada en ' int2str(length(laberinto1(lab, ent, salida))) ' movimientos'])

…el resultado es:


135

>> disp(['Solución alcanzada en ' int2str(length(laberinto1(lab, ent, salida))) ' movimientos']) entrada = 10 10 salida = 1 1 laberinto = 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 Elapsed time is 0.021913 seconds. Solución alcanzada en 1118 movimientos Figura 84

El comando disp que escribimos en la consola de MATLAB compone un vector de tres cadenas de caracteres: la primera es el texto Solución alcanzada en; la segunda, la transformación a texto de la longitud del resultado de ejecutar la función laberinto1 con los valores que pasamos como parámetros; la tercera, la cadena movimientos.

• Solución 2.

Supongamos que se desea que la salida de la función muestre las casillas que ha recorrido el objeto para llegar desde la entrada a la salida. En este caso, una vez calculados los movimientos necesarios, debemos recorrer este vector, tomar cada una de sus coordenadas y colocar, en las posiciones que indique, algún valor (el 2, por ejemplo) sobre el laberinto, de manera que se representen las casillas visitadas.

Esto es lo que hacemos en la Función 130 con el bucle añadido al final: recorremos el vector de movimientos (formado a su vez por vectores de dos coordenadas) y, para cada coordenada contenida en él, vamos a la posición correspondiente en el laberinto y colocamos el valor 2. Finalmente, asignamos el nuevo laberinto a la variable camino, que es la variable que devuelve el resultado de la función.

Macario Polo Usaola

136

function camino = laberinto2( laberinto, entrada, salida ) entrada salida laberinto tic movimientos=[]; coordenadaActual=entrada; movimientos=[movimientos; coordenadaActual]; while (coordenadaActual(1)~=salida(1) || coordenadaActual(2)~=salida(2)) direccion=rand(); % <=0.25: arriba; <=0.5: derecha; % <=0.75: abajo; <=1: izquierda if direccion<=0.25 & coordenadaActual(1)>1 siguiente(1)=coordenadaActual(1)-1; siguiente(2)=coordenadaActual(2); elseif direccion<=0.5 & coordenadaActual(2)<length(laberinto) siguiente(1)=coordenadaActual(1); siguiente(2)=coordenadaActual(2)+1; elseif direccion<=0.75 & coordenadaActual(1)<length(laberinto(:, 1)) siguiente(1)=coordenadaActual(1)+1; siguiente(2)=coordenadaActual(2); elseif direccion<=1 & coordenadaActual(2)>1 siguiente(1)=coordenadaActual(1); siguiente(2)=coordenadaActual(2)-1; end if laberinto(siguiente(1), siguiente(2))==0 coordenadaActual=siguiente; movimientos=[movimientos; coordenadaActual]; end end for i=1:length(movimientos()) casilla=movimientos(i, :); laberinto(casilla(1), casilla(2))=2; end camino=laberinto; toc end Función 130. Modificación de la Función 129 para que se muestren las casillas visitadas

Para una determinada ejecución, el resultado final es el siguiente:

ans = 2 1 2 2 2 2 1 0 0 0 2 1 2 1 1 1 1 0 2 0 2 1 2 1 0 0 1 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 2 2 2 2 2 2 2 2 2 1 2 1 1 1 1 2 1 2 2 2 2 1 2 2 2 2 1 2 1 1 1 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 0 0 1 2 Figura 85. Se han marcado las casillas visitadas por la Función 130


137

Ejercicio 46. Búsqueda binaria

Disponemos de un vector ordenado de enteros de longitud n. Se pide diseñar una función que tome como parámetro el vector v y un valor x y devuelva, mediante una búsqueda binaria, la posición en que se encuentra el valor x dentro de v, o -‐1 en caso de que no esté.

• Solución 1.

Supongamos que tenemos el siguiente vector ordenado:

v= 1 2 3 4 5 6 7 8 9 10 2 2 4 6 7 8 8 9 15 18

Supongamos que deseamos buscar el número 4 dentro de él (o sea, x=4). Mediante una búsqueda binaria, comparamos el elemento buscado con el que se encuentra en la mitad del vector (el 5º, que es un 7): como x<5, buscamos ahora en la mitad inferior (es decir, entre las posiciones 1 a 4) y comparamos con el elemento que está en la mitad (el 2º, que es un 2): como 2<x, buscamos entre el elemento 3º y el 4º. Cotinuamos así hasta que lo encontremos o hasta que lleguemos a la conclusión de que el valor x no se encuentra en el vector.

En la siguiente función devolveremos el resultado en la variable r, que inicalizamos a -‐1, En li y ls guardamos los límites inferior y superior en los que la búsqueda está acotada. Mientras no encontremos el valor (o sea, mientras r=-‐1) y los límites inferior y superior no se crucen (li<=ls), vamos comparando el elemento que encontramos en la mitad: si el valor situado en la mitad es x, actualizamos el valor de r (con lo que saldremos del bucle); si es menor, actualizamos el límite inferior li, pues sabemos que x no estará a la izquierda de él; si es mayor, actualizamos el límite superior ls porque x no estará a la derecha.

function r = busquedaBinaria1(v, x) r=-1; li=1; ls=length(v); while r==-1 && li<=ls mitad=floor((ls+li)/2); if v(mitad)==x r=mitad; elseif v(mitad)<x li=mitad+1; else ls=mitad-1; end end end Función 131. Búsqueda binaria iterativa

Si queremos conocer en cuántas iteraciones se encuentra el valor, añadimos al código anterior las instrucciones resaltadas en amarillo:

Macario Polo Usaola

138

function r = busquedaBinaria1(v, x) r=-1; li=1; ls=length(v); iteraciones=0; while r==-1 && li<=ls mitad=floor((ls+li)/2); if v(mitad)==x r=mitad; elseif v(mitad)<x li=mitad+1; else ls=mitad-1; end iteraciones=iteraciones+1; end disp(['Valor encontrado en ' int2str(iteraciones) ' iteraciones']); end Función 132. Búsqueda binaria iterativa con indicación del número de iteraciones

En la siguiente figura buscamos, en el lado izquierdo, el número 6 entre los números 1 a 100; en el derecho, buscamos el 200 en el mismo rango de valores:

>> z=1:100 % Inicializamos el vector z con los naturales del 1 al 100 z = Columns 1 through 24 1 2 3 4 … Columns 97 through 100 97 98 99 100 >> busquedaBinaria1(z, 6) Valor encontrado en 4 iteraciones ans = 6

>> busquedaBinaria1(z, 200) Valor encontrado en 7 iteraciones ans = -‐1

Figura 86. Dos resultados al ejecutar la Función 132 (se encuentra en la izquierda, y no en la derecha)

• Solución 2.

A continuación damos una versión recursiva de la función de búsqueda binaria pero, a diferencia de la anterior, no devolvemos la posición en la que se encuentra el elemento, sino solamente un 1 si está o un -‐1 en caso contrario:


139

function r = busquedaBinaria2(v, x) r=-1; li=1; ls=length(v); mitad=floor((ls+li)/2); if li>ls r=-1; return elseif v(mitad)==x r=1; return; elseif v(mitad)<x li=mitad+1; else ls=mitad-1; end auxiliar=v(1, li:ls); r=busquedaBinaria2(auxiliar, x); end Función 133. Implementación recursiva de la búsqueda binaria

En el código anterior, calculamos la mitad y comparamos el elemento situado en esa posición con x. Si es menor (if amarillo), actualizamos el límite inferior; si es mayor (else verde), actualizamos el superior. Previamente hemos comprobado los dos casos base de la recursividad: si se ha encontrado el elemento en la mitad, devolvemos un 1; si no se ha encontrado (el límite inferior es mayor que el superior), devolvemos un -‐1. Cuando no estamos en alguno de los dos casos base, guardamos en auxiliar el subvector que hay entre las posiciones li a ls y llamamos recursivamente a la función.

Supongamos que buscamos el número 20 en el siguiente vector:

v= 1 2 3 4 5 6 7 8 9 10 2 2 4 6 7 8 8 9 15 18

Al llamar a la función por primera vez, r=-‐1, li=1, ls=10, mitad=5. Como v(5)=7<20, se actualiza li: li=5+1=6 y auxiliar=[8 8 9 15 18], y se llama a la función con este subvector y el valor x=20.

Entramos al segundo nivel de recursividad. Ahora, v es el vector auxiliar que nos ha llegado a la función desde el primer nivel:

v= 1 2 3 4 5 8 8 9 15 18

Ahora, r=-‐1, li=1, ls=5, mitad=3. Como v(3)=9<20, li=3+1=4 y auxiliar=[15 18], y se llama nuevamente a la función:

v= 1 2 15 18

En este tercer nivel de recursividad, r=-‐1, li=1, ls=2, mitad=1. Como v(1)=15<20, li=1+1=2 y auxiliar=[18], llamándose nuevamente a la función:

Macario Polo Usaola

140

v= 1 18

Ahora, r=-‐1, li=1, ls=1, mitad=1. Como v(1)=18<20, se hace li=2 y recortamos el vector desde la posición 2 hasta la 1, obteniendo un vector vacío, con el cual llamamos nuevamente a la función:

v=

En esta nueva llamada, r=-‐1, li=1, ls=0, mitad=0. Se evalúa el primer caso base de la recursividad (li>ls) y, como la condición es cierta, se va devolviendo el -‐1 hasta llegar a la llamada original desde la línea de comando:

>> v v = 2 2 4 6 7 8 8 9 15 18 >> busquedaBinaria2(v, 20) ans = -‐1 Figura 87. Resultado de ejecutar una búsqueda binaria recursiva en un vector, con resultado infructuoso

introduccion a la programacion con matlab 46 ejercicios resueltos con varias soluciones todas...

Documents