recursividad (divide y vencerás)

RecursividadDivide y Vencerás

ProgramaciónLester Sánchez

Universidad de La Habana

2013 – 2014

Divide y Vencerás

1. Dividir el problema complejo en subproblemassimples

2. Conquistar (resolver) los problemas simples

3. Vencer (resolver) el problema original a partir de las soluciones de los problemas simples

Programación, UH 2013-2014 2

Estructura general de un algoritmorecursivo


Algoritmo RECURSIVO

IF (Problema Simple)

Resolverlo directamente

ELSE

Dividir en subproblemas P1, P2, ..., Pn

Resolver(P1); Resolver(P2); ... Resolver(Pn)

Combinar las soluciones de cada subproblema

Dividir

Conquistar

Vencer

Composition with Large Red Plane, Yellow, Black, Gray and BluePiet Mondrian, 1921


Quiero generar esta figura


1

Problema Inicial: Dividir el rectánguloen varias regiones

Subproblema: Dividir el rectángulo en dos rectángulos

más pequeños, y resolver el mismo problema en cada uno


1

2

Subproblema 1: Resolverlo de la misma forma

Subproblema 2: CasoBase. No hay que

dividirlo más

Caso Base: CuandoAlto o Ancho sean

demasiado pequeños


1 2

3

54 6

7 8 9

11

1

10 2 3

4 5

6 7

8 9

10 11

k Problema Complejo

k Problema Simple (Caso Base)

Cada problema complejo se divide en dos nuevos subproblemas

Ejemplo: Mondrian


Dividir los dos nuevos rectángulos

que se forman

Dividir los dos nuevos rectángulos

que se forman

Obtenerpunto de división

Dibujarlínea

divisoria

DEMOMondrian


Ejemplo: Máximo de un Array


4, 17, 44, 10, 30, 25, 6

4, 17, 44, 10

4 17

4

44 10

44

Max (17, 44)=44

20, 25, 6

20 25

20

6

Max (25, 6)=25

Max (44, 25)=44

Cada problema se divide en dos nuevos subproblemas (buscar máximo en cada mitad)Hasta que la mitad tenga 1 elemento (caso base), el máximo

17 10 25

Max (4, 17)=17 Max (44, 10)=44 Max (20, 25)=25

Ejemplo: Máximo de un Array


Método Recursivo. Recibe índices para

limitar el rangodonde buscar

El método públicose limita a invocaral recursivo con los parámetros iniciales

Si hay un únicoelemento, es el máximo

El máximo del array es el máximo de los máximos

de cada mitad

Búsqueda Binaria

Ejemplos de la vida cotidiana

‐ Buscar una palabra en un diccionario

‐ Buscar un nombre en el directorio telefónico

‐ Buscar una página de un libro

‐ Retomar la visualización de un video


En general optimizamos la búsqueda cuando los elementos están ordenados

Optimización en este caso significa hacer menos comparaciones para encontrar el elemento… o determinar que no está

Búsqueda Binaria


4 6 10 12 17 25 29 30 41 44

0 1 2 3 4 5 6 7 8 9

29 > 17

25 29 30 41 44 29 < 30

25 29 29 > 25

29 = 2929

Se encontró el elemento haciendo solo 4 comparaciones!

Búsqueda Binaria


4 6 10 12 17 25 29 30 41 44

0 1 2 3 4 5 6 7 8 9

28 > 17

25 29 30 41 44 28 < 30

25 29 28 > 25

28 != 2929

Se determinó que el elemento no está haciendo solo 4 comparaciones!

Búsqueda Binaria


1 2 3 4 5 6 7 8 … n n/2

(n/2)/2 = n/4 = n/22

((n/2)/2)/2 = n/8 = n/23

(((n/2)/2)/2) … /2 = n/2k

k es la cantidadmáxima de divisiones

Cuando n/2k = 1 no hay nada más que dividir

.

.

.

Cantidad de elementosdel nuevo fragmento

Búsqueda Binaria


O sale por aquí

O sale por aquí

Buscar en la 2da mitad

Buscar en la 1ra mitad

Ordenación por Mezcla (Merge Sort)


Si se tienen dos arrays ordenados, se pueden mezclarde forma tal que el array resutante siga ordenado

ALGORITMO RECURSIVO

1. Dividir el array en dos mitades

2. Ordenar cada mitad de la misma forma

3. Mezclar las dos mitades

4. Una mitad de 1 elemento está ordenada

Ejemplo: Ordenación por Mezcla


38 27 43 3 9 82 10

38 27 43 3 9 82 10

38 27 43 3

38 27 43 3

9 82 10

829

27 38 3 43

3 27 38 43

9 82

9 10 82

3 9 10 27 38 43 82

Ordenación por Mezcla


Si el fragmento tiene un solo elemento, está ordenado!

Ordenar la 1ra mitad

Ordenar la 2da mitad

Mezclar las dos mitades ordenadas

Se utiliza para hacer la mezcla

Ordenación por Mezcla


Copiar los restantesde la 1ra mitad

Copiar los restantesde la 2da mitad

Copiar el fragmentoordenado al array original

Clase Práctica

Implementar la búsqueda en un array desordenado

int Buscar (int[] a, int n)

Determinar cantidad mínima de inserciones requeridas para convertir una cadena en palíndromo

Ejemplo: A la cadena “abcb” basta con insertarle una “a” pordetrás para convertirla en palíndromo (abcba) y a “abecba” basta con insertarle una “e” en el medio (abeceba) o una “c” (abcecba).

int InsercionesPalindromo(string s)


Clase Práctica

Implemente el algoritmo de ordenación QuickSort.

void QuickSort(int[] a)

El QuickSort se basa en la idea de reorganizar los elementosde un array, seleccionando un elemento (pivote) y colocandotodos los menores que él al inicio del array y los mayores e iguales al final. Implemente esta estrategia en un algortimorecursivo utilizando la técnica de divide y vencerás.


Clase Práctica

Un TAXISTA se desplaza por una ciudad en la que solo estápermitido conducir hacia el ESTE y hacia el SUR. Calcule la cantidad de caminos desde un origen hasta un destino.

int CantidadCaminos(int xOrig, int yOrig, intxDest, int yDest)

Calcule la cantidad de cadenas balanceadas que puedenformarse con n pares de paréntesis.

int CadenasBalanceadas(int n)


Clase Práctica

Implemente un método que imprima en la Consola la descomposición en sumandos de un número n.

Ejemplo: n = 5

1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 2

1 + 2 + 2

1 + 1 + 3

1 + 4

2 + 3

5

void DescomposicionSumandos(int n)


recursividad (divide y vencerás)

Education