ESTALMAT-Andalucía Oriental 07/08

Actividades

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática: Aplicaciones. _____________________________________________________________________________ En esta segunda sesión vamos a trabajar los siguientes contenidos: - Procedimientos. - Programación Matemática: Aplicaciones.

Actividad 1: Procedimientos.

Actividades:

Proyecto “Visor de Imágenes” Mejora el Visor de Imágenes. Agrega un módulo que vas a llamar “mdlDibujando” al proyecto para escribir los procedimientos AbrirImagen y el procedimiento “DibujaBorde” y sustituye el código que se repite de Visor de Imagen por llamadas a estos procedimientos. Termina de programar las opciones del formulario frmOpciones. Solución: Recuerda que un Objeto es una estructura de programación que encapsula datos y funciones en una sola unidad y a la que solo se puede acceder a través de sus interfaces (propiedades, métodos y eventos). Las Propiedades son atributos que describen al Objeto. Los métodos acciones que el objeto es capaz de realizar. Los eventos son métodos que se ejecutan de un modo especial provocados por el usuario al interactuar con los controles de un formulario.

Recuerda también que un procedimiento es un conjunto discreto de código que puede ser ejecutado desde otros bloques de código. Existen dos tipos de procedimientos: • Que devuelven un valor (denominados funciones). • Que no devuelven un valor(denominados subrutinas o simplemente procedimientos) Funciones Public Function Nombre(ByVal o ByRef variable As …) As … Código… End Function Subrutinas o procedimientos Public Sub Nombre(ByVal o ByRef variable As …) Código… End Sub

Página 1

Paco Villegas & Luis Cabello

ESTALMAT-Andalucía Oriental 07/08

Actividades

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática: Aplicaciones. _____________________________________________________________________________ Carga el proyecto VisorImagen que está en la carpeta sesion20 del escritorio. Pincha en Proyecto>Agregar Módulo… y ponle el nombre dibujando. Escribe el siguiente código: Public Sub AbrirImagen() 'Mostrar el cuadro de diálogo abrir If frmVisor.ofdSeleccionaImagen.ShowDialog = Windows.Forms.DialogResult.OK Then 'Cargar la Imagen en el cuadro de Imagen frmVisor.PicAlojoImagen.Image = _ Image.FromFile(frmVisor.ofdSeleccionaImagen.FileName) 'Mostrar el nombre del archivo en el titulo del formulario frmVisor.sbrBarraEstado.Items(0).Text = _ frmVisor.ofdSeleccionaImagen.FileName End If End Sub Public Sub DibujaBorde(ByRef objcajadibujo As PictureBox) Dim objGraphics As Graphics objGraphics = objcajadibujo.Parent.CreateGraphics objGraphics.Clear(System.Drawing.SystemColors.Control) objGraphics.DrawRectangle(Pens.Blue, _ objcajadibujo.Left - 1, objcajadibujo.Top - 1, _ objcajadibujo.Width + 1, objcajadibujo.Height + 1) objGraphics.Dispose() End Sub Observa que el código de AbrirImagen() coincide casi exactamente con el código asociado a los eventos del botón Imagen del Ítem del Menú Fichero Abrir Imagen y del icono de Barra de la barra de herramientas. Explica cuál es la diferencia. Repitamos y veamos las diferencias del trozo de código que dibuja el borde con el procedimiento DibujaBorde. Ahora sustituimos los trozos de códigos por llamadas a los procedimientos AbrirImagen () y DibujaBorde(picAlojoImagen) ¿Es mejor el procedimiento DibujaBorde que AbrirImagen? ¿Por qué motivo? Trata de mejorar el procedimiento AbrirImagen

Actividad 2: Programación Matemática. Programa: Criba.

Página 2

Paco Villegas & Luis Cabello

ESTALMAT-Andalucía Oriental 07/08

Actividades

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática: Aplicaciones. _____________________________________________________________________________ Diseña una solución que simule la criba de Eratóstenes para buscar los números enteros y positivos primos que hay hasta un número entero positivo dado de antemano. Solución: Vamos a programar un método propuesto por Eratóstenes para obtener la lista de todos los primos menores, hasta cierto valor. Los pasos del método son: • Primero hacemos una lista de todos los números desde 1 hasta n. • Tachamos el 1. • Tomamos el 2 y tachamos todos los múltiplos de 2 en la lista. • Buscamos el primer número sin tachar y tachamos todos sus múltiplos mayores. • Repetimos el paso anterior hasta que se acaben los números. • Los que quedaron sin tachar son los que no tienen divisores (propios) o sea los primos. Monta el formulario como el que tienes en la imagen y programa los botones lista y criba, para ello escribe las líneas de programación oportunas e introduce los comentarios que creas necesarios para que aclaren el funcionamiento del código.

la

Utilizamos el control ListView para mostrar lista de todos los números cuando se pulse el botón

y ponga en azul los múltiplos

cuando se pulse el botón Utilizaremos una matriz en este ejercicio. Una matriz se declara de forma parecida a como se hace con una variable: Dim lista(n) as Integer. lista(n) es una caja con n+1 elementos. Para almacenar un valor lista(2)=3, el tercer elemento de la matriz es un 3. Una Matriz se puede llenar mediante un bucle. La idea es llenar una matriz con n+1 elementos. Colocamos en lista(0) un cero, en todos los demás elementos de la matriz un -1 ¿Con que bucle?. Un -1 en lista(i) indica que i está sin tachar (primo). Un 0 en lista (i) indica que i está tachado (no primo). Hacemos lista(1)=0 y lo ponemos azul. Y viene el bucle anidado milagroso que busca el primer número sin tachar y tachamos todos sus múltiplos mayores. Así sucesivamente. For p = 2 To n If lista(p) = -1 Then MsgBox("Tachamos mútiplos de " & p) Página 3

Paco Villegas & Luis Cabello

ESTALMAT-Andalucía Oriental 07/08

Actividades

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática: Aplicaciones. _____________________________________________________________________________ For j = p * p To n Step p lista(j) = 0 ListView1.Items.Item(j - 1).BackColor = Color.Blue Next j End If Next p

Actividad 3: Programación matemática: Aplicaciones Programa: SuperCriba. Para cada primo p, el múltiplo (propio) más chico que no esta tachado es p2. Así que los primos menores que la raíz cuadrada de n pueden tener múltiplos sin tachar en la tabla, pero los mayores no. ¿Es cierto esto? ¿Porqué?. Basándote en el razonamiento anterior mejora el programa Criba (llámalo SuperCriba) para que sea más rápido. Puedes crear otra versión donde la salida sean los primos menores o iguales que el número de entrada.

Actividad 4: Programación matemática: Aplicaciones. Programa: Descomposición en factores primos. A veces para factorizar un número lo escribimos como producto de dos factores de forma fácil y repetimos el mismo proceso para cada parte hasta que lo descomponemos totalmente. Ejemplo: 140= 10*14 = (2*5)*(7*2). También puede ser 140 = 2*(70)=2*(7*10)=2*(7*(2*5)). Se podría hacer de muchas maneras pero el resultado siempre es el mismo aunque los factores no estén el mismo orden. Diseña un programa que descomponga de esta manera. Solución Observa como podríamos hacer para que el ordenador encontrara algún factor. Dim Raiz, otro, i, factor As Integer Raiz = Int(Math.Sqrt(Numero)) - 1 'Prueba solo hasta la raiz cuadrada por la que ya sabemos 'Pero no con 1 otro = 1 For i = 1 To ParaProbar * Raiz 'Prueba muchas veces a factorizarlo buscando un posible factor aleatorio menor que la raíz del número factor = 2 + Int(Rnd() * Raiz) If Numero Mod factor = 0 Then

Página 4

Paco Villegas & Luis Cabello

ESTALMAT-Andalucía Oriental 07/08

Actividades

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática: Aplicaciones. _____________________________________________________________________________ otro = Numero \ factor Exit For End If Next ParaProbar es una constante para que intente encontrar el factor las veces que se quiera. Si no encuentra un factor podría ser primo. El siguiente código es para comprobar si es primo. If otro = 1 Then 'No ha encontrdo factor, quizas Numero es primo For factor = 2 To Raiz + 1 If Numero Mod factor = 0 Then otro = Numero \ factor Exit For End If Next factor End If Lo puedes ver en la carpeta de la sesion 20. En general ver si un número muy grande es primo o no, es un problema difícil aunque hay algoritmos rápidos, pero basados en matemática más avanzada. Si tratamos de utilizar los métodos que vimos antes para ver si 10000000200000001 es primo, utilizando la criba seguro que nos quedamos sin memoria, y si tratamos de probar dividiendo por los anteriores es demasiado lento. Tremendamente más difícil es factorizar un número si es muy grande, aunque sepamos que nos es primo. En esta dificultad se basa la seguridad de algunos sistemas de encriptación de clave pública por ejemplo el PGP, en este caso se tienen dos claves: • La pública: esta clave se da a conocer y permite que cualquiera sea capaza de cifrar un mensaje, pero no se puede usar para descifrarlo. • La privada: Es secreta y con ella se pueden descifrar los mensajes que se cifraron utilizando la clave pública. Resulta que la clave privada son dos números primos grandes y la pública es el producto de los dos primos grandes que componen la privada. Actividad 5: Programación matemática: Aplicaciones.

Programa: ContarFactorizaciones.

Diseña un solución en visual Basic que averigüe cuántos números enteros positivos menores que un cierto numero p, entero positivodado de antemano, tienen como únicos factores primos al 2, 3 ó 5. (Por ejemplo: 2, 8, 15, 30, 60, ...)

Página 5

Paco Villegas & Luis Cabello

ESTALMAT-Andalucía Oriental 07/08

Actividades

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática: Aplicaciones. _____________________________________________________________________________

Solución. El enunciado pide contar cuántos enteros n cumplen n >= 1, n < p, y n = 2a·3b·5c. Como el 1 no sirve, lo descartamos. Lo que vamos a hacer es un programa que pruebe todos los números enteros desde 2 hasta p, y los cuente cuando el número sólo tiene como factores primos al 2, 3 ó 5.

Vaquedando.

Primero hacemos una copia del valor del número en la variable

Eliminamos todos los doses de la factorización de Vaquedando. Para ello utilizamos Si tiene de factor al 2 Vaquedando lo dividimos por 2. Se repite este proceso hasta que estemos seguros de eliminar a todos los 2. Para ello utilizamos el bucle: Do While (Vaquedando Mod 2 = 0) Vaquedando = Vaquedando / 2 Loop Hacemos lo mismo con 3 y 5 Si al final Vaquedando es 1 hemos encontrado una factorización válida, la contabilizamos y pasamos al siguiente número. Se podría mejorar el programa para que el usuario eligiera los tres primos de la descomposición. El programa lo tienes en la carpeta sesión20.

Página 6

Paco Villegas & Luis Cabello

Programación matemática. Aplicaciones Recursividad Luis Cabello & Paco Villegas 26 de abril de 2008

ESTALMAT - ANDALUCÍA

Índice 1. Introducción: algoritmos 1.1. El coste de los algoritmos: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1. El problema del viajante . . . . . . . . . . . . . . . . . . . . . . . . .

2 2 2

2. Funciones recursivas

5

3. Ejemplos 3.1. Factorial de un número . . . 3.2. Sucesión de Fibonacci . . . 3.3. Torres de Hanoi . . . . . . . 3.3.1. Un poco de historia: 3.3.2. Resolución . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

6 6 7 9 9 10

Introducción: algoritmos

1.

Estalmat-Andalucía 07/08

Introducción: algoritmos

La palabra algoritmo proviene del nombre de un matemático árabe del siglo IX llamado Muhammad ibn M˜usã al-Khwãrizm˜ı (es decir, Muhannmad, hijo de M˜usã, nacido en Khwãrezm), se trata de unos de los “padres” del Álgebra. Entre sus aportaciones destacar que fue uno los culpables de la introducción del sistema árabe de numeración. Pero ¿qué es un algoritmo? Conjunto de reglas que, aplicadas sistemáticamente a unos datos de entrada adecuados, resuelven un cierto problema en un número finito de pasos elementales [1] En el instituto y en el colegio se os han enseñado bastantes algoritmos (algunos que seguro se han olvidado ya), por ejemplo el del cálculo de la parte entera de la raíz cuadrada de un número natural, el algoritmo de Euclides para calcular el máximo común divisor, o por ejemplo, el algoritmo de la multiplicación (no confundirlo con las tablas de multiplicar, no son un algoritmo): Para multiplicar 4 · 3, se suma 4 tres veces (claro antes tengo que saber sumar), es decir: 4 · 3 = 4 + 4 + 4 = 8 + 4 = 12 NOTA: No penséis que multiplicar dos números es tan simple a nivel informático. Cuando se trabaja con números enteros muy grandes, puede ocurrir que los operandos se vuelvan tan grandes que no se puedan operar de forma directa (a partir del tamaño de palabra de la computadora). En este caso se usan algoritmos “especiales” (del tipo divide y vencerás) que permitan hacer los cálculos. Cuestiones antes de seguir: ¿Qué algoritmos conocéis más? Una receta de cocina ¿es un algoritmo? ¿Podemos encontrar un algoritmo para calcular de forma exacta el valor decimal del número π?

1.1.

El coste de los algoritmos: En informática (y matemáticas) uno de los mayores problemas que nos encontramos es el de medir la eficiencia de un algoritmo. Surge entonces la necesidad de estudiar qué recursos (en tiempo de cálculo y cantidad de memoria) se necesitan para conocer de antemano unos indicadores que, de alguna manera, nos permitan saber si el algoritmo encontrado es viable o no. Veamos esto con un ejemplo: 1.1.1.

El problema del viajante

Supongamos que tenemos una empresa de panadería que tiene 20 puntos de venta repartidos por la ciudad. Todas las mañanas, el furgón de reparto tiene que salir desde la panificadora y dejar en cada punto el pan y pasteles necesarios. El chófer de la furgoneta se plantea entonces el siguiente problema: Página 2

Luis Cabello & Paco Villegas

Introducción: algoritmos

Estalmat-Andalucía 07/08

¿Cuál el el camino más corto para pasar por todos los puntos de venta? Como es aficionado a las mates, piensa que esto es fácil: Sólo tengo que saber qué caminos hay disponibles, obtengo su suma de distancias y me quedo con las más corta, así que manos a la obra. Lo primero es saber cuántos caminos diferentes tengo: Veamos, si hay un sólo punto de reparto: el viaje de ida y vuelta, no hay problema Si son dos: casi que da igual, son dos caminos diferentes, pero en realidad es uno solo, le da igual Si son tres: tenemos 6 rutas (notar que el punto de partida no influye), pero se repiten dos a dos (podemos optar por hacer la ruta P123P o P321P, aunque son rutas diferentes a efectos de cómputo suponen el mismo tiempo. Es decir 3!2 = 3 ¿Con cuatro?: número de rutas 4!, pero caminos “diferentes” 4!2 Esto va bien, nuestro chófer concluye, para 20 punto de venta será (abre su wxMaxima y obtiene): 20! 2432902008176640000 = = 1216451004088320000 2 2 Conoce las distancias entre los puntos de venta y el tiempo que tarda en cada uno, así que sólo tiene que hacer esas “pocas de multiplicaciones y sumas” y listo, se queda con la más corta. Como además es aficionado a la informática, sabe que cada una de esas operaciones, en un ordenador actual, puede tardar 100 microsegundos (hay que hacer 20 multiplicaciones y una suma), así que el tiempo que tardará su ordenador será de: 1216451004088320000 · 100 · 10−6 s anos ˜ = 3857340,829808219 anos ˜ 60 · 60 · 24 · 365

¿Cómo? ¡más de 3 millones de años!, esto es fácil cambiará de ordenador y listo, pero claro, la mejora de capacidad de cálculo en un equipo de último modelo es de 1000 veces el que él Página 3

Luis Cabello & Paco Villegas

Introducción: algoritmos

Estalmat-Andalucía 07/08

tiene, así que sólo consigue saber que podrá resolver el problema (qué seguro es computable ya que sólo hay que hacer un número finito de cuentas) en poco más de 3000 años. Para pensar después: Si le aumentan el número de puntos de venta en tres más, ¿cuánto tiempo tardará el nuevo ordenador que se ha comprado? ¿Crees que la solución es cambiar de ordenador para resolver este tipo de problemas? Está claro que la forma de resolver el problema no es la adecuada, hay que buscar un algoritmo que permita resolver el problema en un tiempo real. A partir de problemas como este, surge la necesidad de intentar clasificar los problemas desde una perspectiva del tiempo de cómputo, y surge lo que se llama el análisis de la complejidad de los algoritmos. En informática se usa la notación O (grande) para intentar clasificar el coste teórico en tiempo de un algoritmo, algunas clases de complejidad, ordenadas de menor a mayor coste son: O(1), O(log n), O(n), O(n log n), O(n2 ), O(n3 ), O(2n ), O(n!), O(nn ) En general, los algoritmos de búsqueda son de orden O(n) (si buscamos una persona en un listado no ordenado de n personas, lo más “malo” que nos puede pasar es que esté la última). Los algoritmos estándar de ordenación, en general están en O(n2 ), los “buenos” en O(n log n). Ejemplo: con un algoritmo de tipo cuadrático, el tiempo empleado en ordenar un vector de 100,000 números enteros es unas 6,000 veces más lento que un algoritmo de los “buenos”. Es decir, el “bueno” tarda un minuto, el cuadrático tardaría ¡10 minutos! Para pensar después: busca en Internet algún algoritmo de ordenación de los costes anteriores Los algoritmos cuyo coste sea como máximo del tipo O(nk ) k ∈ Z se denominan polinomiales y son computables en un tiempo “razonable” (son tratables1 ). En la tabla que sigue hemos calculado de forma aproximada (en horas) el tiempo que tardaría cada uno de ellos si suponemos que el coste de una instrucción elemental en tiempo es un nanosegundo (10−9 s) Clase n = 10 n 2, 7 · 10−12 n log n 2, 7 · 10−12 n2 2, 7 · 10−11 n3 2, 7 · 10−10 n 2 2, 84 · 10−10 n! 1, 008 · 10−6 nn 2, 7 · 10−1

n = 100 2, 7 · 10−11 5, 5 · 10−11 2, 7 · 10−9 2, 7 · 10−7 3, 52 · 10+17 2, 59 · 10145 2, 7 · 10187

n = 200 5, 5 · 10−11 1, 28 · 10−10 1, 1 · 10−8 2, 2 · 10−6 4, 46 · 1047 2, 18 · 10362 4, 46 · 10447

n = 500 1, 38 · 10−10 3, 8 · 10−10 6, 94 · 10−8 3, 47 · 10−5 9, 02 · 10137 3, 38 · 101129 8, 48 · 101345

Está claro por qué a los algoritmos de coste mayor a los polinomiales se les llama intratables ¿a qué sí? Moraleja: no basta con encontrar el algoritmo que permita resolver un problema informático, además tiene que ser un buen algoritmo. 1 En

caso de coste mayor, se denominan intratables

Página 4

Luis Cabello & Paco Villegas

Funciones recursivas

2.

Estalmat-Andalucía 07/08

Funciones recursivas

Ya sabemos que ante un problema, no sólo hay que encontrar la forma de resolverlo, además hay que buscar un algoritmo que lo haga antes de que desesperemos (o algo peor). Cuando para resolver un problema, tenemos que repetir una serie de cálculos (muy parecidos) varias veces, los mecanismos que nos permiten los lenguajes de programación son la recursividad y la iteración (ya la habéis visto). La recursividad sólo es posible si un procedimiento o función pueden hacer referencia a sí mismos dentro de su propia definición: Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición, las instancias complejas de un proceso se definen en términos de instancias más simples, estando las finales más simples definidas de forma explícita. [5] Un ejemplo clásico (otro pueden ser los propios número naturales) para explicar en qué consiste una función recursiva, es el de la la función potencia de base entera y exponente natural, por ejemplo: 74 = 71 · 73 ¿qué significa esto? que, el problema de calcular una potencia de exponente 4 lo podemos reducir a calcular una de exponente 3, pero ¿cómo puedo calcular la de exponente 3, ¡pues! 73 = 71 · 72 Qué lío, pero ahora ¿cómo hago lo que me falta?, 72 = 71 · 71 Bien, pero el "ordenata" no es muy listo y ni siquiera sabe cuánto vale eso de 71 , no nos queda mas remedio que avisarle de que 70 = 1 (porque sí) y entonces, él sigue: 71 = 71 · 70 = 7 · 1 = 7 Ya está, deshaciendo el camino tenemos: 72 = 71 · 71 = 49 73 = 71 · 72 = 7 · 49 = 343 74 = 71 · 73 = 7 · 343 = 2401 Si formalizamos esto en lenguaje matemático tendríamos:  1 si n = 0 n 7 = n−1 7·7 si n ≥ 1 ¿Cuál sería la formula “recursiva” de la función potencia para cualquier base?  1 si n = 0 n x = n−1 x·x si n ≥ 1 Página 5

Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

Y usando la nomenclatura matemática para las funciones (con dos letras2 , ¡qué fuerte!):  1 si n = 0 f (x, n) = x · f (x, n − 1) si n ≥ 1 En Visual Basic, podría ser:

Function Potencia(ByVal x As Integer, ByVal n As Integer) As Long If n = 0 Then Return 1 ' Si ya hemos llegado a exponente cero, devuelve 1 Else Return x*Potencia(x,n-1) End If End Function Otro ejemplo que ya hemos visto es el de la criba de Eratóstenes (275-195 a.C.): algoritmo para listar todos todos los números primos comprendidos entre el número 2 y un numero n 1. Escribir todos los números naturales comprendidos entre 2 y n 2. El primer número no tachado de la lista, y no contabilizado todavía es primo. Tachar todos sus múltiplos. Si no queda ningún múltiplo, terminar. 3. Volver al paso 2 Pero, como ya se ha visto, sigamos nosotros con otros ejemplos.

3.

Ejemplos

3.1.

Factorial de un número

Recordemos que la función factorial se escribe en lenguaje matemático como sigue  1 si n = 0 n! = n · (n − 1)! si n ≥ 1 Así, para calcular 4! lo haremos así: 4! = 4 · 3! 3! = 3 · 2! 2! = 2 · 1! 1! = 1 · 0! 2 de

dos variables

Página 6

Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

0! = 1 Y escrita en forma de función sería  f (x) =

1 si n = 0 x · f (x − 1) si n ≥ 1

Por fin, ya sabemos que 4! = 4 · 3 · 2 · 1 · 1 = 12. ¿por qué complicar esto tanto? pues porque así lo hacen los ordenadores. Y para que puedan hacerlo nosotros hemos de “programar” bien el algoritmo. ¿Serías capaz de programarlo? ¡seguro que sí!. Para facilitarte el trabajo te damos algunas pistas.

Function Factorial(ByVal N As Integer) As Long If N = 0 Then ' El factorial de 0 es 1 Return 1 ' No hacer más llamadas ElseIf N > 0 Then Return N * Factorial(N-1) ' Llamadas con N-1 End If End Function Cuando tengas el programa calcula 10! =

20! =

25! =

3.2.

Sucesión de Fibonacci

La sucesión de F IBONACCI es la sucesión infinita de números naturales 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . donde el primer elemento es 0, el segundo es 1 y cada elemento restante es la suma de los dos anteriores. A cada elemento de esta sucesión se le llama número de Fibonacci. Se debe a Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. La ideó como la solución a un problema de la cría de conejos: Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también. [3] Página 7

Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

¿Cómo se construye? Se tienen que conocer los dos primeros valores, en este caso: f1 = 0 f2 = 1 y a partir de ellos obtenemos los demás teniendo en cuenta que el siguiente término es la suma de los dos anteriores, es decir: f3 = f1 + f2 = 0 + 1 = 1 f4 = f2 + f3 = 1 + 1 = 2 ...

fn = fn−2 + fn−1 En notación “más” funcional:  si x = 1  0 1 si x = 2 f (x) =  f (x − 2) + f (x − 1) si x ≥ 3 Ahora te toca, ¿puedes hacer un programa que calcule f (15)?. NOTA: Con este algoritmo para calcular términos para la sucesión de Fibonnaci, el número de sumas (y memoria) que utiliza el ordenador es muy elevado (está en el orden O(Φn ), √ donde Φ = 1+2 5 es el número de oro) es decir, es muy lento. Por ejemplo, para calcular f50 este algoritmo requiere efectuar 20365011073 sumas. [3] En este caso, los algoritmos usados son iterativos o una modificación del algoritmo recursivo (más complejo), versión Divide y Vencerás (Complejidad O(log n)) Página 8

Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

Podemos modificar los dos primeros valores y obtenemos “otras” sucesiones de Fibonacci (Sucesiones de Fibonnaci Generalizadas). Por ejemplo, si los dos primeros valores son: f1 = 2 f2 = 2 ¿Cuanto vale f4 ? Práctica: haz un programa que permita obtener un término cualquiera de una Sucesión de Fibonnaci Generalizada. El programa te tendrá que pedir tres valores. Para la sucesión anterior halla f10

3.3.

Torres de Hanoi

Las Torres de Hanoi es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas d’Amiens3 . Consiste en tres varillas verticales y una serie de discos de diferente tamaño, la dificultad a la hora de resolver el juego dependerá del número de discos con el que juguemos.

No hay dos discos iguales e inicialmente están colocados de mayor a menor en la primera varilla. El juego consiste en pasar todos los discos a la tercera varilla manteniendo la figura original. Las reglas para conseguirlo son: Sólo se puede mover un disco cada vez Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él. Sólo se puede mover en cada jugada el disco que se encuentra arriba de alguna de las tres varillas. 3.3.1.

Un poco de historia:

Una leyenda4 cuenta que Dios, después de crear el mundo, puso en la tierra tres barras hechas de diamantes, y 64 anillos de oro en la primera. Estos anillos son todos de diferente tamaño y al colocarlos se cuidó de ordenarlos por tamaño, estando el mayor en la parte inferior 3 Lo

publicó con el seudónimo de Profesor N. Claus de Siam, mandarín del colegio Li-Sou-Stian (trabajaba en el instituto de Sant Luis). Curioso el juego de letras del profe ¿verdad? 4 Esta leyenda fue un invento publicitario del creador del juego. [3] Página 9

Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

y el menor en la parte superior. También creó un monasterio junto a las barras. A los monjes del monasterio encargó un trabajo: se trataba de que tenían que trasladar todos lo anillos a la segunda barra, pero con la condición de que la única operación permitida es trasladar un sólo anillo de una barra a la otra de manera que nunca puede situar un anillo sobre otro de menor radio. El trato es que el día que estos monjes consigan terminar el juego, el mundo acabará. Si la leyenda fuera cierta, ¿cuándo será el fin del mundo?, veamos:

Supongamos que los monjes mueven un anillo por segundo, de día y de noche y sin equivocarse, en ese caso tienen que realizar al menos 264 − 1 movimientos (¿por qué?), es decir, 584.942.417.355,07202 años (poco menos de 585 mil millones de años, más de 25 veces la edad estimada del universo y unas 100 veces la edad de la tierra).

3.3.2.

Resolución

Para resolver el problema analicemos un poco qué pasa con: Un anillo: no hay problema, un sólo movimiento. Es el caso “trivial” (el n=0). Movimientos 1 = 2 − 1 Página 10

Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

Con dos: en este caso, ponemos el disco pequeño en el centro y el problema se reduce a mover el disco más grande. Movimientos=3 = 2 · 1 + 1

Con tres: se tata de que primero conseguimos el paso dos (mover dos discos tal cual hemos hecho antes, pero cuidando la posición de las varillas). Movimientos5 7 = 2 ∗ 3 + 1 = 23 − 1

El truco a la hora de resolverlo reside en fijarnos en el disco más pequeño. El primer movimiento de ese disco se realiza hacia la varilla auxiliar (C). El disco número dos, se 5 Se

demuestra por inducción que si llamamos Mn al número de movimientos para una Torre de Hanoi de n discos, entonces: Mn = 2 · Mn−1 + 1 A partir de ella, se obtiene que Mn Página 11

= 2n − 1 Luis Cabello & Paco Villegas

Ejemplos

Estalmat-Andalucía 07/08

mueve a la varilla B. Después el disco pequeño se mueve a la varilla B para que quede sobre el disco dos. Es el momento de situar el disco grande, que está aún en la varilla A, en la varilla C. Ya casi, ahora el disco más pequeño regresa de la varilla A, el mediano se coloca ya en su sitio definitivo (varilla C) y finalmente ponemos el disco pequeño en su lugar. Fijémosnos en que para cuatro discos (o n), de lo que se trata es de que siempre tenemos que llegar a una situación en la que en se queda sólo el disco grande (en la varilla A) y en la varilla de en medio (B) tenemos una torre de Hanoi de 3 (en general (n − 1)) discos. Es decir, ¡recursividad!.

Si numeramos los discos desde 1 hasta n, y llamamos A a la primera varilla, C a la tercera (destino) y B a la intermedia (auxiliar) el algoritmo de la función sería el siguiente: 1. Si n = 1, lleva el disco de la barra A a la C y termina 2. Mueve la torre de (n − 1) fichas de la barra Aa la B 3. Lleva el disco grande (que se ha quedado solo en la varilla origen (A)) a la varilla destino (C) 4. Traslada la torre de (n − 1) discos, usando este mismo algoritmo, de (B) a (C), pero usando ahora como varilla auxiliar la (A) En forma de “función” fun Hanoi(origen, destino, auxiliar, n) si n = 1 entonces escribe Mueve disco de poste origen a poste destino si no hacer Hanoi(origen,auxiliar, destino, n − 1) Hanoi(origen,destino, axiliar, 1) Hanoi(auxiliar,destino, origen, n − 1) fsi ffun Para pensar después: 1. A partir de la función anterior, ¿podemos calcular ya en nuestro ordenador Hanoi(64, A, B)? Página 12

Luis Cabello & Paco Villegas

REFERENCIAS

Estalmat-Andalucía 07/08

2. Más cuestiones matemáticas de interés: revisa la Web http://descartes.cnice.mecd.es/materiales_didacticos/rompecabezas/ TorresHanoi.htm y te proponemos que realices las actividades que te propone el autor.

Referencias [1] Peña Marí, R. (2006), De Euclides a Java. Historia de los algoritmos y de los lenguajes de programación, Madrid, Nivola libros y ediciones, S.L. [2] Garfunkel, S. y más (1999), Las matemáticas en la vida cotidiana, Madrid, Addison-Wesley Iberoamericana españa, S.A. [3] Wikipedia, http://es.wikipedia.org/wiki/Portada [4] Brassard, G. y Bratley, P. (1997), Fundamentos de Algoritmia, Madrid, Prentice Hall. [5] Charte, Francisco (2002), Programación con Visual Basic .NET, Madrid, Anaya Multimedia. [6] Gonzalo Arroyo, J. y Rodríguez Artacho, M. (1997), Esquemas algorítmicos: enfoque metodológico y problemas resueltos, Madrid, UNED.

Página 13

Luis Cabello & Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________

Programación matemática. Aplicaciones Recursividad SOLUCIONES

Índice de contenido Potencia de base entera y exponente natural....................................................................................1 Factorial de un número.....................................................................................................................5 Sucesión de Fibonnacci....................................................................................................................8 Torres de Hanoi...............................................................................................................................13 1. POTENCIA DE BASE ENTERA Y EXPONENTE NATURAL Para crear una aplicación que calcule el factorial de un número crearemos un nuevo proyecto del tipo Aplicación para Windows al que podríamos llamar CalculoPotencias.

Una vez creado el proyecto lo guardaremos con el mismo nombre. En el formulario que se crea añadiremos varios componentes a través de los cuales el usuario podrá interactuar con la aplicación. En primer lugar añadiremos desde el cuadro de herramientas dos campos de texto (TextBox) donde se introducirán la base y el exponente. Les daremos un nombre representativo a los dos controles que hemos creado modificando la propiedad Name. Al primer campo de texto le llamaremos cajaTextoBase y al segundo cajaTextoExponente.

Página 1

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ También añadiremos dos etiquetas (Label) asociadas a cada uno de los campos de texto. Modificaremos la propiedad Text de cada una de ellas y, al igual que hacíamos con los campos de texto, les cambiaremos también el nombre modificando la propiedad Name. Etiqueta 1: ● Name: etiquetaBase ● Text : Base Etiqueta 2: ● Name: etiquetaExponente ● Text : Exponente Añadiremos el botón responsable de llamar a la función encargada de realizar el cálculo y, por último, una nueva etiqueta en la que se escribirá el valor de la potencia. A estos dos últimos controles les modificaremos las siguientes propiedades: Botón: ● ●

Name: botonCalcular Text: Calcular

Etiqueta: ● Name: etiquetaPotencia. ● Text: POTENCIA Para terminar cambiaremos la propiedad Text del formulario por Cálculo de potencias. Una vez creado el formulario tendremos que decirle a nuestra aplicación que responda al hacer clik sobre el botón calculando la potencia y escribiéndola en la etiqueta correspondiente. Para ello haremos doble click sobre el botón, generándose de forma automática el siguiente método: Private Sub botonCalcular_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles botonCalcular.Click End Sub

Dentro del método escribiremos: Private Sub botonCalcular_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles botonCalcular.Click

(2^32)-1]

'definimos las variables que vamos a utilizar Dim base, exponente As Integer 'Enteros de

32

bits

[-2^32,

Dim potencia As Long 'Enteros de 64 bits [-2^64, (2^64)-1] 'obtenemos los números introducidos en las cajas de texto base = CInt(Me.cajaTextoBase.Text) exponente = CInt(Me.cajaTextoExponente.Text) 'calculamos la potencia

Página 2

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ potencia = obtenerPotencia(base, exponente) 'escribimos la potencia en la etiqueta correspondiente Me.etiquetaPotencia.Text = Me.cajaTextoBase.Text + " ^ " Me.cajaTextoExponente.Text + " = " + potencia.ToString()

+

End Sub

Pero todavía nos falta lo más importante, nuestra aplicación aún no sabe cómo obtener la potencia de un número. Para ello deberemos crear una función (obtenerPotencia) a la que le pasaremos como parámetros la base y el exponente y nos devolverá como resultado la potencia. Una función no es más que una secuencia de instrucciones que realizan una determinada tarea y que al terminar ésta devuelven un valor o resultado. Las funciones se pueden llamar desde otras partes de la aplicación. A las funciones se les pueden pasar parámetros que podrán ser utilizados dentro de la función para conseguir la tarea. Hemos visto anteriormente que al pulsar sobre el botón botonCalcular se ejecuta el procedimiento botonCalcular_Click. La diferencia entre una función y un procedimiento es que los procedimientos no devuelven ningún valor. La forma de declarar una función es muy parecida a la de los procedimientos, basta con sustituir Sub por Function e indicarle el tipo del valor que va a devolver. De esta forma podríamos crear nuestra función obtenerPotencia: Function obtenerPotencia(ByVal Integer) As Long

base

As

Integer,

ByVal

exponente

As

If exponente = 0 Then Return 1 Else Return base * obtenerPotencia(base, exponente - 1) End If End Function

A nuestra función le pasamos dos parámetros de tipo entero (Integer): la base y el exponente de la potencia, y le indicamos, al final de la definición, el tipo del resultado que devuelve (Long). Para devolver el resultado se utiliza la palabra reservada Return. Cuando se llega a alguna línea en la que se encuentra esta palabra la función finaliza, devolviendo el valor que aparece tras Return. Ahora vamos a analizar el código encargado de calcular la potencia: If exponente = 0 Then Return 1 Else Return base * obtenerPotencia(base, exponente - 1) End If

Si lo observamos un poco veremos que es bastante similar al algoritmo que hemos visto anteriormente para el cálculo de potencias: ● Si el exponente es 0 la función devuelve como resultado 1. ● Si el expontente es distinto de 0 devuelve:

Página 3

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ base * obtenerPotencia(base, exponente – 1

(base * (base ^ (exponente – 1))) Veamos un ejemplo concreto analizando cómo actúa esta función. Si como base introducimos 2 y como exponente 3 (2 ^ 3) tendríamos: potencia = obtenerPotencia(2, 3)

obtenerPotencia(2, 3) = 2 * obtenerPotencia (2, 2) obtenerPotencia(2, 2) = 2 * obtenerPotencia (2, 1) obtenerPotencia(2, 1) = 2 * obtenerPotencia (2, 0) obtenerPotencia(2, 0) = 1 Al llegar a exponente 0 finaliza el proceso y se van sustituyendo las sucesivas funciones por su valor hasta obtener el resultado buscado: obtenerPotencia(2, 0) = 1 obtenerPotencia(2, 1) = 2 * 1 = 2 obtenerPotencia(2, 2) = 2 * 2 = 4 obtenerPotencia(2, 3) = 2 * 4 = 8 potencia = 8

2. FACTORIAL DE UN NÚMERO Para crear la aplicación encargada de calcular el factorial de un número seguiremos los mismos pasos que en el ejemplo anterior: ● ● ●

Crearemos un proyecto basado en una aplicación para Windows llamado CalculoFactorial Guardaremos el proyecto con el mismo nombre Añadiremos al formulario los siguientes controles: ○ Caja de texto ■ Name: cajaTextoNumero ○ Etiqueta ■ Name: etiquetaNumero ■ Text: Introducir el número ○ Botón: ■ Name: botonCalcular ■ Text: Calcular ○ Etiqueta: ■ Name: etiquetaFactorial ■ Text: FACTORIAL

Página 4

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ Haremos doble click sobre el botón para que se cree el método que capturará el evento generado al hacer click sobre dicho botón, y escribiremos el siguiente código: Private Sub botonCalcular_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles botonCalcular.Click 'definimos las variables que vamos a utilizar Dim numero As Integer 'Enteros de 32 bits [-2^32, (2^32)-1] Dim factorial As Long 'Enteros de 64 bits [-2^64, (2^64)-1] 'obtenemos el número entero introducido en la caja de texto numero = CInt(Me.cajaTextoNumero.Text) 'calculamos el factorial

factorial = obtenerFactorial(numero) 'escribimos el factorial en la etiqueta correspondiente Me.etiquetaFactorial.Text = "El factorial de " + Me.cajaTextoNumero.Text + " es " + factorial.ToString() End Sub

Si observáis el código es bastante similar al que habíamos escrito para calcular las potencias. En este caso utilizamos una nueva función (obtenerFactorial), a la que pasamos como parámetro el numero del que queremos obtener el factorial. También podemos observar cómo el tipo de las variables que definimos son los mismos. El número lo definimos como un entero de 32 bits (Integer) y el factorial como un entero de 64 bits (Long). La función sería la siguiente: Function obtenerFactorial(ByVal numero As Integer) As Long If numero = 0 Then Return 1 'El factorial de 0 es 1 ElseIf numero > 0 Then Return numero * obtenerFactorial(numero - 1) End If End Function

A pesar de que la función devuelve un entero de tipo Long, la aplicación no permite calcular el factorial de números mayores de 20. Esto es debido a que una variable de tipo Long permite valores comprendidos entre -9223372036854775808 y 9223372036854775807, y el factorial de 21 es mayor que esta cifra. Si observamos el código de nuevo veremos que es similar al algoritmo matemático utilizado para el cálculo del factorial. ● ●

Si el número vale 0 devuelve (Return) 1 Si el número es mayor de 0 la función devuelve (Return) numero * obtenerFactorial(numero – 1) Página 5

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ Veamos un ejemplo concreto sobre cómo actúa la función calculando el factorial de 4: factorial = obtenerFactorial(4) obtenerFactorial(4) = 4 * obtenerFactorial(3) obtenerfactorial(3) = 3 * obtenerFactorial(2) obtenerFactorial(2) = 2 * obtenerFactorial(1) obtenerFactorial(1) = 1 * obtenerFactorial(0) obtenerFactorial(0) = 1 Finaliza el proceso Al llegar el número a 0 finaliza el proceso y se van sustituyendo las sucesivas funciones por su valor hasta obtener el resultado buscado: obtenerFactorial(0) = 1 obtenerFactorial(1) = 1 * 1 = 1 obtenerFactorial(2) = 2 * 1 = 2 obtenerFactorial(3) = 3 * 2 = 6 obtenerFactorial(4) = 4 * 6 = 24 Estamos suponiendo que los número introducidos para calcular el factorial son siempre enteros positivos, ya que en caso contrario los resultados no serían correctos. Por ejemplo, si introducimos números negativos, la función da como resultado 0. Está claro que este resultado no es correcto. Para evitar este tipo de errores habría que comprobar antes de llamar a la función que el texto introducido es un entero positivo. Os dejamos este trabajo como mejora de la aplicación. 3. SUCESIÓN DE FIBONACCI De forma similar a los ejemplos anteriores crearemos un nuevo proyecto llamado SucesionFibonacci, añadiendo al formulario los siguientes controles: ● ●

●

Caja de texto Name: cajaTextoElemento Etiqueta Name: etiquetaElemento Text: Elemento nº Botón: Name: botonCalcular Text: Calcular

Página 6

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ ● Etiqueta: Name: etiquetaFibonacci Text: FIBONACCI De forma similar a cómo hicimos en los ejemplos anteriores, en el método que se genera al hacer doble click en el botón Calcular escribiremos: Private Sub botonCalcular_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles botonCalcular.Click 'definimos las variables que vamos a utilizar Dim elemento As Integer 'Enteros de 32 bits [-2^32, (2^32)-1] Dim fibonacci As Long 'Enteros de 64 bits [-2^64, (2^64)-1] 'obtenemos el número entero introducido en la caja de texto elemento = CInt(Me.cajaTextoElemento.Text) 'calculamos el valor del elemento en la sucesión de Fibonacci fibonacci = obtenerFibonacci(elemento)

"

'escribimos el valor en la etiqueta correspondiente Me.etiquetaFibonacci.Text = "El valor del elemento " + Me.cajaTextoElemento.Text + " de la sucesión de Fibonacci es + fibonacci.ToString() End Sub

En este método para obtener el valor del elemento llamamos a la función obtenerFibonacci pasándole como argumento el elemento. El código de esta función podría ser el siguiente: Function obtenerFibonacci(ByVal elemento As Integer) As Long If elemento = 1 Then Return 0 'El primer elemento de la sucesión vale 0 ElseIf elemento = 2 Then Return 1 'El segundo elemento de la sucesión vale 1 ElseIf elemento > 2 Then 'A partir del tercer elemento el valor es la suma de los dos anteriores Return obtenerFibonacci(elemento - 1) + obtenerFibonacci(elemento - 2) End If End Function

De nuevo partimos de la base de que el texto introducido en la caja de texto es un valor válido (entero positivo). Al igual que los otros ejemplos os dejamos como ejercicio mejorar la aplicación para que realice las comprobaciones necesarias, y prevenir de esta forma los posibles errores que se producirán si se introducen valores no válidos. Veamos un ejemplo concreto sobre cómo actúa la función calculando el valor del elemento 5: fibonacci = obtenerFibonacci(5)

Página 7

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________

obtenerFibonacci(5) = obtenerFibonacci(4) + obtenerFibonacci(3) obtenerFibonacci(4) = obtenerFibonacci(3) + obtenerFibonacci(2) obtenerFibonacci(3) = obtenerFibonacci(2) + obtenerFibonacci(1) obtenerFibonacci(2) = 1 obtenerFibonacci(1) = 0 obtenerFibonacci(2) = 1 obtenerFibonacci(3) = obtenerFibonacci(2) + obtenerFibonacci(1) obtenerFibonacci(2) = 1 obtenerFibonacci(1) = 0 A pesar de que hemos seleccionado un elemento de los primeros, podéis observar como las funciones se repiten, esto hace que el número de sumas se vaya incrementando a medida que avanzamos en la sucesión.

Solución iterativa: para hacer después de la sesión Al igual que ocurre con la mayoría de los problemas matemáticos, no existe una única forma de solucionarlos. En este caso vamos a mostrar como se podría hacer de forma iterativa. Agregamos al formulario un nuevo botón con las propiedades: ● Botón: Name: botonCalcularIterativo Text: Calcular iterativo Como siempre hacemos doble clik en este nuevo botón y escribimos: Private Sub botonCalcularIterativo_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles botonCalcularIterativo.Click 'definimos las variables que vamos a utilizar Dim elemento As Integer 'Enteros de 32 bits [-2^32, (2^32)-1] Dim fibonacci As Long 'Enteros de 64 bits [-2^64, (2^64)-1] 'obtenemos el número entero introducido en la caja de texto elemento = CInt(Me.cajaTextoElemento.Text) 'calculamos el valor del elemento en la sucesión de Fibonacci

fibonacci = obtenerFibonacciIterativo(elemento) Página 8

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ 'escribimos el valor en la etiqueta correspondiente Me.etiquetaFibonacci.Text = "ITERATVO: El valor del elemento " + Me.cajaTextoElemento.Text + " de la sucesión de Fibonacci es + fibonacci.ToString()

" End Sub

Y creamos una nueva función llamada obtenerFibonacciIterativo: Function obtenerFibonacciIterativo(ByVal elemento As Integer) As Long 'definimos las variables que vamos a utilizar Dim penultimo, ultimo, actual As Long Dim i As Integer 'iniciamos los valores de las variables de los dos valores iniciales penultimo = 0 ultimo = 1 If elemento = 1 Then Return 0 'El primer elemento de la sucesión vale 0 ElseIf elemento = 2 Then Return 1 'El segundo elemento de la sucesión vale 1 ElseIf elemento > 2 Then 'A partir del tercer elemento el valor es la suma de los dos anteriores 'Calculamos el valor de cada elemento de forma iterativa hasta llegar al elemento buscado ' For i = 3 To elemento Step 1 actual = ultimo + penultimo penultimo = ultimo ultimo = actual Next Return actual End If End Function

Intentad obtener el valor del elemento 40 con cada una de las funciones y observad el tiempo que tarda cada una de ellas. Veamos cómo actúa este método para calcular el valor del elmento 5 de la sucesión de Fibonacci: fibonacci = obtenerFibonacciIterativo(5) penultimo = 0 ultimo = 1 Desde el elemento 3 hasta el 5 elemento 3:

Página 9

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ actual = ultimo (1) + penultimo (0) = 1 penultimo = 1 ultimo = 1 elemento 4: actual = ultimo (1) + penultimo (1) = 2 penultimo = 2 ultimo = 1 elemento 5: actual = ultimo (2) + penultimo (1) = 3 penultimo = 3 ultimo = 2 Termina el bucle y la función devuelve (Return) el valor actual (3) 4. TORRES DE HANOI Para este ejemplo crearemos un proyecto llamado TorresHanoi.

Añadiremos los controles necesarios para que el formulario quede como el de la imagen: Los controles que hemos añadido al formulario tienen las siguientes propiedades: Etiquetas: ● Name: etiquetaAnillos ● Text: Nº de anillos ● ● ● ● ● ● ● ● ● ●

Name: etiquetaOrigen Text: A = Origen Name: etiquetaAuxiliar Text: B = Auxiliar Name: etiquetaDestino Text: C = Destino Name: etiquetaHanoi Text: MOVIMIENTOS TORRES DE HANOI Name: etiquetaMovimientos Text: Nº total de movimientos

Cajas de texto:

Página 10

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ ● Name: cajaTextoAnillos ● ● ●

Name: cajaTextoMovimientos Multiline: true ScrollBars: Vertical

Botón: ● ●

Name: botonVerMoimientos Texto: Ver movimientos

En la caja de texto donde irán apareciendo los movimientos de los anillos (cajaTextoMovimientos) hemos modificado las propiedades Multiline a true para que admita varias líneas, y la propiedad ScrollBars a Vertical para que muestre una barra de desplazamiento vertical en caso de que el número de líneas a mostrar sea mayor que el número de líneas que caben en la caja de texto. También necesitamos hacer algo que no habíamos hecho en los ejemplos anteriores, y es declarar variables a nivel de la clase Form1, ya que las vamos a necesitar en varios de los métodos utilizados. Si observáis el código de los ejemplos anteriores podéis observar que hemos declarado variables (mediante la palabra reservada Dim) dentro de los métodos, ya que estas variables sólo iban a ser utilizadas dentro de dichos métodos (funciones o procedimientos). Las variables declaradas dentro de un método sólo son visibles dentro de ese método. Declaramos las siguientes variables: Public Class Form1 Dim movimientos As Long Dim origen, destino, auxiliar As String ................................. ................................. End Class

En el método que se genera al hacer doble click sobre el botón Ver movimientos escribimos el siguiente código: ByVal

Private Sub botonVerMovimientos_Click(ByVal sender As System.Object, e As System.EventArgs) Handles botonVerMovimientos.Click 'definimos las variables que vamos a utilizar Dim anillos As Integer 'Enteros de 32 bits [-2^32, (2^32)-1] 'obtenemos el número entero introducido en la caja de texto anillos = CInt(Me.cajaTextoAnillos.Text) 'reiniciamos el número de movimientos a 0, así como la letra asignada a cada barra

Página 11

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ 'y borramos el texto de cajaTextoMovimientos movimientos = 0 origen = "A" auxiliar = "B" destino = "C" Me.cajaTextoMovimientos.Text = "" 'realizamos los movimientos para pasar los anillos del origen al destino

moverAnillos(origen, destino, auxiliar, anillos) 'escribimos el valor en la etiqueta correspondiente Me.etiquetaMovimientos.Text = "Nº total de movimientos = " + movimientos.ToString() End Sub

Cada vez que pulsamos sobre el botón le damos los valores iniciales a las variables movimientos, origen, destino y auxiliar. También llamamos al procedimiento moverAnillos que tiene el siguiente código: Sub moverAnillos(ByVal origen As String, ByVal destino As String, ByVal auxiliar As String, ByVal anillos As Integer) If anillos = 1 Then movimientos = movimientos + 1 Me.cajaTextoMovimientos.Text = Me.cajaTextoMovimientos.Text + movimientos.ToString + ".- Mover anillo de " + origen + " a " + destino + vbCrLf Else 'movemos los n-1 anillos de arriba del origen al auxiliar moverAnillos(origen, auxiliar, destino, anillos - 1) 'movemos el que queda sólo, del origen al destino moverAnillos(origen, destino, auxiliar, 1) 'volvemos a mover los n-1 anillos del auxiliar al destino moverAnillos(auxiliar, destino, origen, anillos - 1) End If End Sub

Ya que en este ejemplo no necesitamos que el método devuelva ningún valor, creamos un procedimiento en lugar de una función. Para ello cambiamos la palabra Function que utilizábamos para crear las funciones por la palabra Sub. Veamos cómo funciona este procedimiento: Si el número de anillos a mover es 1: ● se realizará el movimiento, contabilizándose éste ● se escribirá en la caja de texto una nueva línea con el número del Página 12

Luis Cabello y Paco Villegas

ESTALMAT-Andalucía Oriental

Actividades 07/08

Sesión: 20 Fecha: 26-04-2008 Título: Programación Matemática. Aplicaciones _____________________________________________________________________________ movimiento y los datos del origen y el destino. Para que cada movimiento se escriba en una nueva línea añadimos al final del texto vbCrLf, que equivale a un salto de línea. Si el número de anillos a mover es mayor de 1: ● movemos los n-1 anillos de arriba del origen al auxiliar, convirtiéndose el auxiliar en el destino y el destino en el auxiliar. ● movemos el que queda sólo del origen al destino, quedándose ya correctamente colocado ● volvemos a mover los n-1 anillos del auxiliar al destino, convirtiéndose el auxiliar en el origen, y el origen en el auxiliar

Página 13

Luis Cabello y Paco Villegas