mig cortess: lab de algoritmos(recursividad)

Hare referencia a la recursividad la cual consiste en hacer un problema mas censillo con una serie de pasos que simplifiquen dicho problema hasta llegar a un punto que la resoluciòn del mismo tenga una complejidad mas o menos trivial o de una forma mas o menos manejable para resolverlo de una forma no recursiva a este punto le llamamos caso base ia que es el limite de la recursividad por que si n se tiene ese caso base estaremos en una recursion que no tiene fin y no nos serviria de nada por que se repetiria una y otra vez sin alguna solucion ni llegar a nada para comprender mejor esto pondre un ejemplo de la recursividad de un Factorial(x: Entero): Sea N = x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

$n!= \begin{cases} \mbox{si }n=0 & \Rightarrow 1 \\ \mbox{si }n\geq1 & \Rightarrow n \;(n-1)! \end{cases}$

sacamos el factorial de 5 para ver si lo dicho anteriormente funciona

5! = 5 · (5-1)!
   = 5 · 4!
   = 5 · 4 · (4-1)!
   = 5 · 4 · 3!
   = 5 · 4 · 3 · (3-1)!
   = 5 · 4 · 3 · 2!
   = 5 · 4 · 3 · 2 . (2-1)!
   = 5 . 4 . 3 . 2 . 1!

= 5 . 4 . 3 . 2 . 1 . (1-1)!

= 5 . 4 . 3 . 2 . 1 . 0!

= 5 . 4 . 3 . 2 . 1 . 1

= 120

el resultado del factorial de 5 es 120 y es correcto y el caso base si funciono

y la operacion termina en el caso base por que sin el se hubieran echo infinitas

las operaciones y no abria resultado y a esta funciòn se le conoce como funciòn

recurrente ya que su dominio puede ser recursivamente definido

poder realizar esto es de gran ayuda ya que esto es base fundamental de diversos

algoritmos de gran importancia y por consigueinte parte fundametal de la programaciòn

dinamica

el codigo de el factorial en c quedaria de esta manera:

FACTORIAL

#include<stdio.h>
#include<stdlib.h>

int factorial(int)

main(){
  int x;
  printf("a que valor entero positivo desea sacar el factorial?");
  scanf"(%d",&x);
if(x<0){
  pritnf("el valor que se introdujo no es un valor positivo");}
 else {
   printf("el factorial es:", factorial(x));}

int factorial(int x)
{
  if(x<=1) return 1;
  return x*factorial(x-1);
}

donde la recursion se efectua hasta llegar al caso base que es x=1 termina

y se arroja el resultado tambien hay otras funciones en las que se aplica la recursividad

por ejemplo en los numeros de catalan forman una secuencia de numeros naturales

que aparece en varios problemas de conteo que habitualmente son recursivos, para obtener

el n-esimo numero de catalan apartir de esta formula aplicando coeficientes binomiales:

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ con }n\ge 0.$

la expresion alternativa a Cn:

$C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ con }n\ge 1.$

 los numeros de catalan satisfacen a las siguientes relaciones de recurrencia:

$C_0 = 1 \quad \mbox{y} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\mbox{con }n\ge 0.$

$C_0 = 1 \quad \mbox{y} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,$

 la cual puede ser una forma mas eficiente de calcularlos entonces la exprecion

en forma de recursion seria:

$C_{n} = \begin{cases} \mbox{si }n=0 & \Rightarrow 1 \\ \mbox{si }n>0 & \Rightarrow \cfrac{2(2n-1)}{n+1} \, C_{n-1} \end{cases}$

 que ya viendo las dos funciones anteriores resulta esta que claramente vemos que

 el caso base es n=0 el valor sera uno y hay mchas aplicaciones para estos numeros

en problemas de combinatoria por ejemplo:

C_n es el número de formas distintas de agrupar n + 1 factores mediante paréntesis (o el número de formas de asociar n aplicaciones de un operador binario). Para n = 3 por ejemplo, tenemos las siguientes formas distintas de agrupar los cuatro factores:

para dos letras, $ab$ , hay sólo una forma:

$(ab)$

Para tres letras, $abc$ , tenemos dos formas:

$((ab)c)$ y $(a(bc))$

Si tenemos cuatros letras, $abcd$ , se obtienen cinco formas:
$((ab)(cd)), (((ab)c)d), (a(b(cd))), (a((bc)d))$ y $((a(bc))d)$ y asi sucesivamente para las demas que siguen aqui tenemos 1,2,5,.... si seguimos realizando esta analogia obtemdremos 14,42,132,...... y se comprueba que es recursivo aparte tiene aplicacion para dar el numero total de arboles,planos,plantados y trivalentes pr ejemplo:

Las aplicaciones sucesivas de un operador binario pueden representarse con un árbol binario. En este caso, C_n es el número de árboles binarios de n + 1 hojas, en los que cada nodo tiene cero o dos hijos:

Catalan 4 leaves binary tree example.svg

y bien por ultimo la serie de catalan que incrementa asintoticamente a:

$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$

 

esto es todo por mi parte espero y sea de su agrado y les sirva en algo gracias

fuentes http://gaussianos.com/los-numeros-de-catalan/

             http://es.wikipedia.org/wiki/Recursi%C3%B3n

            http://www.alegsa.com.ar/Notas/115.php

mig cortess

viernes, 8 de julio de 2011

lab de algoritmos(recursividad)

1 comentario: