Monthly Archives: August 2010

Factorial de forma sencilla en C++

Ya vimos como calcular el factorial de un número c++ en forma recursiva, sin embargo hay una forma mucho mas fácil de entender y de aplicar (pero menos eficiente). Vamos viendo:

Si el factorial de un número es la multiplicación de cada número desde 1 hasta ese número (por ejemplo factorial de 4 = 1*2*3*4 = 24), entonces es muy sencillo crear un ciclo de 1 hasta el número pedido en c++ para hacer el cálculo.

#include
using namespace std;

int main()
{
    int num,fact=1;
    cout << "::FACTORIAL::" << endl;
    cout <> num;
    for(int i=2; i<=num; i++)
    {
        fact = fact * i;
    }
    cout << "Su factorial es: " << fact;
    cin.get();cin.get();
    return 0;
}

¿Entonces porqué el ciclo empieza en 2? Si comenzara en 1, el proceso para el numero 3 (por poner un ejemplo) sería así:

  • fact = fact * i -> fact = 1 * 1 -> fact = 1
  • fact = fact * i -> fact = 1 * 2 -> fact = 2
  • fact = fact * i -> fact = 2 * 3 -> fact = 6

Como ven, el primer paso es totalmente innecesario.

Advertisements

Recursividad aplicada: Torres de Hanoi

Este juego matemático es clásico de los problemas de programación. Hoy vamos a ver cómo calcular el número de movimientos necesarios para resolver el juego según el número de discos, de forma recursiva en C++.

#include
int hanoi(int n)
{
    if(n==1)
        return 1;
    else
        return 2 * hanoi(n-1) + 1;
}
int main()
{
    int disc, mov;
    printf("::TORRES DE HANOI::n");
    printf("Numero de discos: ");scanf("%i",&disc);
    printf("tMovimientos necesarios: %in", hanoi(disc));
    return 0;
}

Otro algoritmo raro. Lo que sabemos es que si tenemos 1 disco el número de movimientos es 1 y que ese es nuestro caso base (si n==1 retorna 1), a partir de ahí el número de movimientos se puede calcular si multiplicamos por dos el número de movimientos para n-1 y le sumamos 1, o sea: 2 + hanoi(n-1) + 1

  • Si son 2 discos, entonces 2 * hanoi(1) + 1 = 2 * 1 + 1 = 3
  • Si son 3 discos, entonces 2 * hanoi(2) + 1 = 2 * 3 + 1 = 7
  • etc

Recursividad aplicada: Máximo Común Divisor

Ooootro post sobre recursividad, pero no se preocupen ya solo queda este y otro. Esta vez vamos a calcular el máximo común divisor de dos números de forma recursiva en c++.

#include
int MCD(int x, int y)
{
    if(y==0)
        return x;
    else
        return MCD(y, x%y);
}
int main()
{
    int num1=0,num2=0;
    printf("::MAXIMO COMUN DIVISOR::n");
    printf("Introduce el primer numero: ");scanf("%i",&num1);
    printf("Introduce el segundo numero: ");scanf("%i",&num2);
    printf("tEl resultado es: %in", MCD(num1, num2));
    return 0;
}

Este es uno de esos algoritmos recursivos raros o, mejor dicho, difíciles de comprender, mi cerebro estuvo un buen rato echando humo tratando de comprender la lógica con que lo armaron y mi conclusión es que funciona de pura rana. Bueno, al final si supe como funciona pero no porque.

Recursividad aplicada: Serie de Fibonacci

0, 1, 1, 2, 3, 5, 8, 13, 21, …, la serie de Fibonacci es bastante interesante e incluso aparece en la naturaleza. Comienza con un 0, luego un 1 y a partir de ahí cada número es la suma de los dos siguientes. Eso último nos indica recursividad. Veamos como mostrar n números de la serie de Fibonacci de forma recursiva en C++.

#include
int fibonacci(int n)
{
    if (n<2)
        return n;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
    int num=0,res=0;
    printf("::NUMEROS DE FIBONACCI::n");
    printf("Introduce el numero de numeros: ");scanf("%i",&num);
    printf("t");
    for(int i=0;i<=num-1;i++)
    {
        res = fibonacci(i);
        printf("%i  ", res);
    }
    printf("n");
    return 0;
}

Es la primera vez que vemos un la llamada a la función dentro de un ciclo. Eso es porque la función calcula el n-ésimo número de la serie, y para mostrarlos todos tenemos que hacer un ciclo que repita la función tantas veces como sea necesario.

Recursividad aplicada: Convertir Decimal a Binario

Siguiendo con esto de la recursividad hoy les traigo un nuevo programín, Convertir Decimal a Binario de forma recursiva.

#include
void binario(int n)
{
    if (n!=0)
    {
        binario(n/2);
        printf("%i",n%2);
    }
}
int main()
{
    int num=0;
    printf("::CONVERTIR DECIMAL A BINARIO::n");
    printf("Introduce un numero: ");scanf("%i",&num); //Pedir variable num
    printf("t");binario(num);printf("n"); //Llamar la función
    return 0;
}

Está basado en el método que usamos para convertir un número decimal a binario “a mano”: dividir el número entre dos hasta que quede 0 y apuntar los residuos del último al primero.

Recursividad aplicada: Factorial

Hola de nuevo, ¿cuánto tiempo pasó? mmm no sé pero bueno… lo importante es que ya estoy de vuelta y ahora sí me voy a dar el tiempo de actualizar este blog más seguido, pero basta de cosas personales.

No me quiero meter en rollos de explicar lo que es la recursividad (googleen y diviértanse leyendo), lo que quiero es mostrarles algunos ejemplos muy sencillos de dónde podemos aplicar la recursividad. Hoy toca calcular el factorial de un numero de forma recursiva.

Es el código recursivo más fácil que se pueden encontrar:

#include
int factorial(int n)
{
  if(n<2)
    return 1;
  else
    return n * factorial(n-1);
}
int main()
{
  int num=0;
  printf("::CALCULAR FACTORIAL::n");
  printf("Introduce un numero: ");scanf("%i",&num); //Pedir variable num
  printf("tEl resultado es: %in", factorial(num)); //Llama la funcion e imprime resultado
  return 0;
}

Explicación

El caso base es que cuando n valga 1 o 0 retorna un 1, de lo contrario retorna la multiplicación de n * el factorial del numero anterior n-1. Supongamos que introducimos el número 3, cuyo factorial es 6 (3*2*1 = 6).

  1. n=3 No entra al caso base. Guardamos para después la operación 3 * factorial(2)
  2. n=2 No entra al caso base. Guardamos para después la operación 2 * factorial(1)
  3. n=1 Entra al caso base. Retorna 1, por lo tanto factorial(1) = 1
  4. Hacemos la última operación que guardamos 2 * factorial(1) = 2 * 1 = 2, por lo tanto factorial(2) = 2
  5. Hacemos la siguiente operación que guardamos 3 * factorial(2) = 3 * 2 = 6
  6. El factorial es 6

¡Uh que fácil!