Matlab Uch1 Clase8

MATEMÁTICA DISCRETA Clase 7

¿RECURRIR?

•RECURSIVIDAD •ALGORTIMO DE LA DIVISIÓN.

1

RECURSIVIDAD INTRODUCCIÓN

Permite definir un objeto en términos de si mismo Un ejemplo en la vida real: basta con apuntar una cámara al monitor que muestra la imagen que muestra esa cámara Ejemplos típicos en estructuras de datos: Árboles y Listas enlazadas Ejemplos en matemáticas: El 1 es un número natural, el siguiente número de un número natural es natural. El factorial de un número.

Universidad de Ciencias y Humanidades Algebra Computacional

2

RECURSIVIDAD DEFINICIÓN

Un subprograma que se llama a si mismo se dice recursivo Hay dos formas diferentes Directa: el subprograma se llama a si mismo. En alguna parte de él aparece una llamada a si mismo Indirecta: el subprograma llama a otro subprograma y este a su vez llama al primero

Universidad de Ciencias y Humanidades Algebra Computacional

3

RECURSIVIDAD La definición de un subprograma recursivo consta de dos partes: 1ª. Ley de recurrencia. 2ª. Condición de salida o caso base. La ley de recurrencia del subprograma debe realizar una llamada al mismo subprograma, teniendo en cuenta que el valor de los parámetros debe cambiar en cada llamada. El caso base (condición de salida o parada) es el caso más simple conocido y es el que determinará el fin de la recursividad.

Universidad de Ciencias y Humanidades Algebra Computacional

4

RECURSIVIDAD EJEMPLO1: FACTORIAL DE N Definición no recursiva: n! = 1*2*3*4*. . . .*(n-1)*n Por definición 0! = 1 Definición recursiva:

si n = 0 ⎧⎪ 1 n! = ⎨ ⎪⎩ n ( n − 1) si n > 0

Universidad de Ciencias y Humanidades Algebra Computacional

5

Ejemplo 2: Serie de Fibonacci La serie es: 0, 1, 1, 2, 3, 5, 8, 13, 21, …. Cada número se obtiene de la suma de los dos precedentes Se define fib(0)=0 y fib(1)=1 entonces

n si n = 0 ∨ n = 1 ⎧⎪ fib ( n ) = ⎨ ⎪⎩ fib ( n − 2 ) + fib ( n − 1) si n ≥ 2

Universidad de Ciencias y Humanidades Algebra Computacional

6

Por ejemplo para n=6 tenemos

Universidad de Ciencias y Humanidades Algebra Computacional

7

VENTAJAS SIMPLICIDAD, para algunos programas la solución iterativa, es muy compleja. PRUEBA, los programas recursivos pueden ser probados fácilmente mediante “inducción matematica” ELEGANCIA, los programas recursivos pueden ser leídos y comprendidos fácilmente

DESVENTAJAS LENTITUD, algunas veces la solución recursiva demanda mas tiempo para su evaluación RECURSOS, un programa recursivo dependiendo de la cantidad de veces que se le llame consume mas recursos. INUTILIDAD, algunos programas no aceptan recursividad (fortran) Universidad de Ciencias y Humanidades Algebra Computacional

8

ALGORITMO DE LA DIVISIÓN Aunque el conjunto Z no es cerrado en la división entre números distintos de cero, existen casos en los que un entero divide exactamente a otro. Por ejemplo 3 divide a 12, 5 divide a 35 en estos casos la división es exacta. Así el hecho que 3 divida a 4 implica la existencia de un cociente (4) tal que 12=3.4. De manera formal diremos: DEFINICION.Si a,bєZ y b≠0 decimos que b divide a a y lo denotamos b|a, si existe un número entero n tal que a=bn. Diremos que b es un divisor de a o que a es un múltiplo de b. Ejemplos 1) 2|6 2 es divisor de 3 2) 3|21 21 es múltiplo de 3

Universidad de Ciencias y Humanidades Algebra Computacional

9

PROPIEDADES.Para cualquier a,b,c enteros. 1) 1|a y a|0 2) a|b y b|a entonces a=±b 3) a|b y b|c entonces a|c 4) a|b entonces a|bx para todo xєZ 5) a|b y a|c entonces a|(bx+cy) para todo x,yєZ

Ejemplo.¿Existen enteros x,y,z tales que 2x+6y+8z=123? Rpta.- ………. Universidad de Ciencias y Humanidades Algebra Computacional

10

ALGORITMO DE LA DIVISION.Si a,bєZ con b>0, entonces existen q,rєZ únicos tales que a=qb+r, con 0≤r
Universidad de Ciencias y Humanidades Algebra Computacional

11

NÚMEROS PRIMOS •Dado pєN, p>1, p es primo si para todo nєN n|p entonces n=p ó n=1 Nota.Todo natural mayor que 1 es divisible por, al menos, un número primo. Ejemplos 2, 17 y 41 ¿20071 es primo? ¿Como sabemos si este número es primo? ¿Cómo sería un programa que permita decirnos si un número natural es primo?

Universidad de Ciencias y Humanidades Algebra Computacional

12

MÁXIMO COMÚN DIVISOR Dados a,bєN, d es divisor común de a y b si d|ay d|b. Definimos el máximo común divisor de a y b como el mayor de los divisores de a y b al cual lo denotamos como mcd(a,b). Ejemplos.1) mcd(12,20)= 2) mcd(42,70)= 3) mcd(2008,3008)=

Universidad de Ciencias y Humanidades Algebra Computacional

13

ALGORITMO DE EUCLIDES •Sean a,bєN con a≥b>0, llamamos r0=a y r1=b. Aplicamos sucesivas veces la división euclídea: r0=q1·r1+ r2 r1=q2·r2+ r3 ................ rn-2=qn-1·rn-1+ rn rn-1=qn·rn+ rn+1

0< r2< r1 0< r3< r2 0< rn< rn-1 rn+1=0

Entonces, el mcd(a,b)=rn

Universidad de Ciencias y Humanidades Algebra Computacional

14

Ejemplos 1) mcd(6,9)=3 ya que 9=6·1+3 6=3·2+0 El último resto distinto de 0 es 3, el mcd. 2) mcd(24,62)=2 ya que 62=24·2+14 24=14·1+10 14=10·1+4 10=4·2+2 4=2·2+0 El último resto distinto de 0 es 2, el mcd. Universidad de Ciencias y Humanidades Algebra Computacional

15

ALGORITMO DE EUCLIDES: UN ALGORITMO VORAZ: • Los algoritmos voraces toman decisiones basándose en la información que tienen disponible de modo inmediato. En el caso de Euclides, la información que tengo disponible en cada momento es el valor del dividendo y del divisor actual. • Se busca en cada paso la solución localmente óptima. Cada vez que asigno un nuevo valor al dividendo y al divisor, busco el nuevo resto. • Para buscarla, se suelen emplear heurísticos. La regla del algoritmo de Euclides es: mientras el resto sea distinto de 0, dividendo = divisor_anterior y divisor = ultimo_cociente, y volver a calcular el nuevo resto

Universidad de Ciencias y Humanidades Algebra Computacional

16

LIMITACIONES DEL ALGORITMO: Éste algoritmo sólo permite calcular el MCD de dos números positivos mayores que 0. Siendo así, el programa retornará el resultado, o un mensaje, en el caso de que los dos valores sean primos entre si (el último cociente vale 1).

Universidad de Ciencias y Humanidades Algebra Computacional

17

Problemas complementarios 1.- Resuelva la siguiente pregunta mediante un programa ¿Cuántos pares de conejos pueden obtenerse a partir de una pareja de conejos en un año, si cada mes cada pareja engendra una nueva pareja la cual a partir del segundo mes se torna productiva, y no se producen muertes? 2.- Se define Sn recursivamente así: S0 = 1 Sn+1 = xSn + 1. Demostrar que Sn = 1 + x + x2 + x3 + ... + xn 3.- Sea Sn una sucesión definida recursivamente así: i) Base: S0 = 1 ii) Paso recursivo: Sn+1 = Sn + 1/2 , para todo natural n>0. Encuentre el valor de S100.

Universidad de Ciencias y Humanidades Algebra Computacional

18

4.- Cree un programa donde se ingrese un número en base 10 y nos devuelva el número en base 2. 5.- Cree un programa donde se ingresen dos números y nos devuelva su mcd. (Alg de Euclides)

Universidad de Ciencias y Humanidades Algebra Computacional

19