miércoles, 1 de mayo de 2013

De decimal a binario con una función recursiva

Tengo una versión de éste programa que es bastante más complicada, pero por mucho tiempo recordé que lo había visto resuelto usando recursión. Ahora he pensado algunas formas de hacerlo, por ejemplo ésta:
Supongamos que tenemos el número 41, y que queremos convertirlo de su notación decimal a binario.
41 En binario  = 1 0 0 0 0 0 + (41 - 32) En binario

                                   9 En binario = 1 0 0 0 +  (9 - 8) En binario

                                                                1 En binario = 1.
El problema se va reduciendo cada vez por medio de llamadas a sí mismo con argumentos más simples. Al final sólo es necesario sumar las representaciones binarias de 32 + 8 + 1. Sin embargo no es ésto lo que yo quiero aquí. Además, sumar será en éste caso más complicado que la propia conversión. Por lo tanto descarté ésta posibilidad.
Otra forma es sugerida por el siguiente proceso, que puede encontrarse por ejemplo en el libro de Diseño Digital, de Morris Mano:
Número          División       Residuo          Binario
  41/2     =       40/2    +     1/2              1
  
  20/2     =       20/2    +      0               0

  10/2     =       10/2    +      0               0
 
   5/2     =        4/2    +     1/2              1
 
   2/2     =        2/2    +      0               0

   1/2     =          0    +     1/2              1
Éste algoritmo es fácilmente programable usando el operador %. Sin embargo, tiene el gran inconveniente de que los dígitos se imprimen en el orden inverso, como puede verse al ejecutar el siguiente código

#include <stdio.h>

/*////////////////////////////////////
 * Funcion Binario                   *
 *///////////////////////////////////*/

void Binario( int x)

{  /* Abre binario*/
if ( x != 0 )
{ /* Abre if*/
printf("%d\t", x%2);

Binario(x/2);

} /*Cierra if */

else;
 /*printf("0\n");*/

}  /*Cierra binario*/

/****************************************
 * main                                 *
 ***************************************/
int main()

{  /*Abre main */
 int num; 

 printf("\nIntroduzca un numero entero: ");
 scanf("%d", &num);

 Binario(num);

 return 0;
}  /*Cierra main */


La ejecución es la siguiente

[hernandez@localhost Programas]$ ./a.out 

Introduzca un numero entero: 41
1       0       0       1       0       1  

De nuevo el problema es que se está imprimiendo el número al revés. Ésto es grave, porque el código es muy bueno, y cualquier intento por corregir el defecto, requiere algoritmos más complicados que la propia conversión.
Sin embargo, después de pensarle, la solución es muy simple. En la función Binario, basta con cambiar el orden de los dos únicos enunciados. Primero hay que hacer una llamada a Binario, y ésto llevará la ejecución hasta el final, hasta el caso más simple, y el control se regresará desde el último caso, imprimiendo los dígitos binarios en el orden inverso. El programa correcto es el siguiente:

#include <stdio.h>

/*////////////////////////////////////
 * Funcion Binario                   *
 *///////////////////////////////////*/

void Binario( int x)

{  /* Abre binario*/
if ( x != 0 )
{ /* Abre if*/
Binario(x/2);

printf("%d\t", x%2);
} /*Cierra if */

else;
 /*printf("0\n");*/

}  /*Cierra binario*/

/****************************************
 * main                                 *
 ***************************************/
int main()

{  /*Abre main */
 int num; 

 printf("\nIntroduzca un numero entero: ");
 scanf("%d", &num);

 Binario(num);

 return 0;
}  /*Cierra main */


La ejecución,
[hernandez@localhost Programas]$ ./a.out 

Introduzca un numero entero: 41
1       0       1       0       0       1
Comopuede verse, son muy pocas las líneas que se requieren para hacer la conversión de binario a decimal usando la recursión, y es un cambio mínimo el que hace esta diferencia.

7 comentarios:

  1. Ejemplo para el número 4:

    n = 4: <-------- Viene de main()

    a_binario (4) --------> n = 4
    {
    int r;
    r = 4 % 2; --------> r = 0
    if (4 >= 2) <-- Verdadero

    a_binario (4/2) --------> n = 2
    {
    int r;
    r = 2 % 2; --------> r = 0
    if (2 >= 2) <-- Verdadero

    a_binario (2/2) --------> n = 1
    {
    int r;
    r = 1 % 2; --------> r = 1
    if (1 >= 2) <-- Falso
    putchar('0' + 1)--------> Imprime 1
    return;
    }

    putchar('0' + 0)--------> Imprime 0
    return;
    }

    putchar('0' + 0)--------> Imprime 0
    return;
    } <-------- Vuelve el control a main()

    Impresión final: 100

    ResponderEliminar
  2. muy bueno:)jejej aunque medio confuso pero grax, ya me lo recibieron

    ResponderEliminar
  3. Para el ejemplo de binario de 8, imprimiría 0001. Es mejor que primero haga Binario(x/2) y después imprima el residuo x%2, así para el binario de 8 imprimirá 1000.
    Es sólo un comentario, en caso de estar equivocada espero mi error sea corregido. Gracias. Excelente día!

    ResponderEliminar
  4. En realidad el numero decimal 41, representado en binario es: 00101001, quedaría imprimir los ceros en los casos que corresponde tomando en cuenta distintos factores como el de ir recorriendo 1 bit a la derecha, usando la suma de bits o la sucesión aritmética de Gauss seria otra opción.

    ResponderEliminar
    Respuestas
    1. El número 41 en sistema de numeración binario es 101001, que es lo que imprime el programa. Tal vez agregas esos dos ceros a la izquierda porque el tamaño de un byte son ocho bits, pero eso nada tiene qué ver con el problema planteado.

      Eliminar

Related Posts Plugin for WordPress, Blogger...