Planteos Recursivos
Resolución de Problemas y
Algoritmos
Segundo Cuatrimestre 2014
La recursividad puede ser utilizada para resolver problemas que exhiban
las siguientes propiedades:
1. Resolver cualquier instancia del problema - excepto el caso
trivial - requiere resolver una o varias instancias más
pequeñas del mismo problema.
2. La instancia más pequeña de un problema, el caso trivial,
puede ser resuelto directamente.
Este principio no sólo nos dice cuándo usar recursividad, sino también
nos orienta acerca de cómo usarla.
Para resolver un problema recursivo es necesario:
1. Identificar el caso trivial, es decir, una instancia que pueda
ser resuelta directamente.
2. Identificar una o más instancias más pequeñas que puedan
ser resueltas en forma más sencilla y usadas luego para
resolver el problema original.
Una cuestión que puede resultar algo imprecisa es cómo
determinar que un problema es más "pequeño" que el
problema original, ilustraremos esta cuestión con ejemplos
específicos.
Para algunos de estos problemas existe una definición
formal, posiblemente matemática, de la cual deriva
directamente un planteo fácilmente implementable.
En otros problemas no tenemos un planteo recursivo
explícito en el enunciado. Deberíamos comenzar entonces
escribiendo uno .
El planteo NO DEBE MOSTRAR
detalles de implementación
Problema: Calcular la potencia n de m, esto es mn , con m <>0
y n no negativo dada la definición:
m
n
1
n es 0
m x mn-1
n>0
1. Identificar el caso trivial, es decir, una instancia que pueda ser resuelta
directamente.
2. Identificar una o más instancias más pequeñas que puedan ser resueltas en
forma más sencilla y usadas luego para resolver el problema original.
Escriba el planteo recursivo que determine si los dígitos de un
número natural están dispuestos de forma creciente, esto es, si
N=dm dm-1….d2 d1 se verifica que di+1 <= di. Por ejemplo: para
1227, 359, 88 o 139 debería retornar verdadero
Empezamos con un ejemplo
CT: si N tiene un solo dígito, entonces es creciente
Creciente (N)
CR: si N tiene mas de un dígito, es verdadero si
N’ es creciente y el último dígito de N es mayor o
igual que el último dígito de N’, donde N’ es N sin
su último dígito. Caso contrario es falso
Leer una cadena de caracteres de longitud arbitraria
finalizada en # y mostrar la cadena en orden inverso. Ej.: si
se tipea animal# deberá imprimirse en pantalla lamina
Empezamos con un ejemplo
CT: No mostrar nada si la secuencia es vacía
Mostrar la
secuencia S en CR: Mostrar la secuencia S’ en orden
orden inverso es: inverso y a continuación mostrar el primer
elemento de la secuencia S, donde S’ es la
secuencia S sin su primer elemento
Escriba un planteo recursivo que dado un número entero E y
un dígito D retorne cuantos dígitos de E son menores a D. Por
ejemplo menores(123456, 4) retornará 3, menores(8756,5)
retornará 0 y menores(123123,4) retornará 6
CB: si E tiene un solo dígito entonces si E < D es
1, en caso contrario es 0
Menores(E,D)
CR: si E tiene más de un dígito, es la cantidad de
dígitos menores a D en E’, mas 1 si el último
dígito de E es > D; de lo contrario es la cantidad
de dígitos menores a D en E’ (donde E’ es E sin
su último dígito)
CR: si E tiene más de un dígito, es Menores(E’,D)+1 si
el último dígito de E es > D, ó Menores (E’,D) en caso
contrario (donde E’ es E sin su último dígito)
En un planteo recursivo
NO DEBEN UTILIZARSE
frases como las siguientes:
- Llamo recursivamente
- Invoco a la función (o procedimiento)
- Y así sucesivamente
- Leo el primer elemento de….
- Así recursivamente hasta que se haga …
- Por cada dígito del número lo comparo….
- Por cada dígito analizo… hasta llegar a …
CB: si E tiene un solo dígito entonces si E < D es 1, en caso contrario es 0
Menores(E,D)
CR: si E tiene más de un dígito, es la cantidad de dígitos menores a D en
E’, mas 1 si el último dígito de E es > D; de lo contrario es la cantidad de
dígitos menores a D en E’ (donde E’ es E sin su último dígito)
CR: tiene mas de un dígito lo divido por 10, hasta que
tenga 1 dígito y cuento por cada dígito del número que sea
menor al dígito dado
CT Si estoy en el ultimo dígito analizo si es menor a D,
de ser así la cantidad aumenta en 1
CR: Por cada dígito de E, analizo si es menor a D y de
ser asi la cantidad aumenta en 1 por cada uno de ellos
CR: Dados É y D, llamar a la función contar, Si E dividido
10=0 y E> 0 entonces retornará contar=0
CR: se lo achica al número hasta que sea menor a 10 y
después de eso comparo su módulo con el dígito ingresado
CR: Si un número tiene mas de un dígito: evalúo del
número si es menor que D cuento 1, caso contrario no
cuento. Vuelvo a evaluar con el número reducido en un
dígito
CR: si tiene mas de un dígito a la función se le asigna el
valor que tenía mas 1
La única manera de aprender a
escribir planteos recursivos
correctos…
…es escribiendo planteos recursivos
Descargar

Planteos Recursivos (06/nov)