Pequeña duda con funcion recursiva

Iniciado por CCross, 16 Mayo 2013, 00:56 AM

0 Miembros y 1 Visitante están viendo este tema.

CCross

Hey!! buenas a todos los apasionados de esto de la programacion, me acabo de inscribir
en el foro. Yo soy unas de esas personas que cuando encuentra un codigo que no  
entiende, trata estudiar como funciona cada expresion, funcion etc;

En fin la cuestion es que me he topado con un codigo que me cuesta un poco comprenderlo
especificamente se trata de una funcion recursiva que lo que hace es convertir un un
numero decimal a binario miren esta es la funcion:

Código (cpp) [Seleccionar]
int binario(int dec)
{
   int resto = num % 2;
   int divide = num / 2;

   return divide > 0 ? binario(divide) * 10 + resto : resto;
}


Lo que llegue a entender es que si dvide es mayor que cero, se ejecuta la funcion
que luego es multiplicada por diez y se le suma uno. Por decirlo si yo le paso un siete
a la funcion, en un primer momento resto valdria 1 y divide seria 3 como ven
divide es mayor que cero, por lo que la funcion se ejecuta.

Lo mas logico es que la funcion binario(divide) retornara un cero que es
multiplicada por 10 que da 0 y luego se le suma 1 y asi sucesivamente en caso de que
divide no sea mayor que 0 se ejecuta el bloque correspondiente a false que le agrega
cero

Que me corrijan si esto no es asi saludos a todos  :rolleyes:

amchacon

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

CCross

#2
Cita de: amchacon en 16 Mayo 2013, 10:15 AM
Creo que no es num sino dec.

Si efectivamente habia cambia los parametros para que sea mas congruentes
me olvide hacer los cambios dentro jeje:.

Código (cpp) [Seleccionar]
int binario(int dec)
{
   int resto = dec % 2;
   int divide = dec / 2;

   return divide > 0 ? binario(divide) * 10 + resto : resto;
}


Y hiendo al tema que opinas estoy en lo corecto seria asi como funciona  o no¿?

Saludos

cypascal

Hola, el fundamento de la función es que un número binario se puede calcular como:
Binario(x)=Binario(x/2)&(x%2)
Donde & indica concatenación, lo que en base decimal, también se puede conseguir multiplicando por 10 y sumando ambos.
Este método es el que te enseñan en la escuela, el de dividir el número por dos e irte quedando con los restos en orden contrario al que los calculaste. (En wikipedia si pones número binario sale)

Salu10
Problemas interesantes de programación en C/C++ y Pascal en:
BLOG C/C++


WWW.CYPASCAL.BLOGSPOT.COM.ES

CCross

#4
Muchas gracias cypascal por la aclaracion, he buscado por internet
y he encontrado una funcion que hace esto de una menera mas simple:

Código (cpp) [Seleccionar]
void binario(int n)
{
   if (n!=0)
   {
       binario(n/2);
       printf("%i",n%2);
    }
}


Esta divide el numero entre dos hasta que quede 0 y apunta a los residuos
del ultimo al primero. Los restos generados en cada division forman el
numero binario el primer resto es el bit menos significativo (LSB) y el
último resto es el bit mas significativo (MSB) del numero binario.

Código (bash) [Seleccionar]
10/2 = 05 con residuo 0 <--- LSB
05/2 = 02 con residuo 1
02/2 = 01 con residuo 0
01/2 = 00 con residuo 1 <--- MSB


Código (bash) [Seleccionar]
Eso se imprimiria de esta forma 1010

En este caso segun entiendo la funcion printf imprime inversamente
los residuos resultante de la division, aprovecha esa propiedad de
imprimir el bit mas significativo primero y el LBS al ultimo siendo el
primero en originarse, podria alguien explicarme como esto es posible..

cypascal lo que entendi fue que al multiplicarlo por 10 consiste
una forma de ir ordenado los residuos de forma inversa seria algo asi no

Un saludo


leosansan

#5
sorry equivoqué el post

leosansan

Cita de: CCross en 17 Mayo 2013, 02:07 AM

En este caso segun entiendo la funcion printf imprime inversamente
los residuos resultante de la division, aprovecha esa propiedad de
imprimir el bit mas significativo primero y el LBS al ultimo siendo el
primero en originarse, podria alguien explicarme como esto es posible..


Pues una forma es ir guardando en un array y luego imprimirlo al revés, o bien lo pasa a binario con la función "itoa":

Código (cpp) [Seleccionar]
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int main()
{
    int j,num,num0,resto,i=0,binario[MAX],bin[MAX];
    printf("Introduzca un numero : ");
    scanf("%d",&num);
    num0=num;
    while(num>=1){
        resto=num%2;
        binario[i]=resto;
        i++;
        num=num/2;
        printf("%d",resto);
    }
    puts("\n");
    for (j=i-1;j>=0;j--)
        printf("%d ",binario[j]);
    itoa (num0,bin,2);
    printf ("\n\n%d en binario: %s\n\n",num0,bin);
    return 0;
}


Saluditos!. .... ..

CCross

#7
Hola leosansan excelete codigo lo de itoa no lo sabia muy bueno pero aun
no logro enterder del todo este codigo:

Código (cpp) [Seleccionar]
return divide > 0 ? binario(divide) * 10 + resto : resto;

Especificamente en la parte de la multiplicacion por diez y luego la suma me
gustaria saber que valor devuelve la funcion de cada llama a ella yo supongo
que seria cero.

Saludos  :rolleyes:

leosansan

#8
Cita de: CCross en 17 Mayo 2013, 20:40 PM
Hola leosansan excelete codigo lo de itoa no lo sabia muy bueno pero aun
no logro enterder del todo este codigo:

Código (cpp) [Seleccionar]
return divide > 0 ? binario(divide) * 10 + resto : resto;

Especificamente en la parte de la multiplicacion por diez y luego la suma me gustaria saber que valor devuelve la funcion de cada llama a ella yo supongo que seria cero.


Es cuestión de "escribir" lo que va haciendo el código. Suelen ser peleonas las funciones recursivas y no muy eficientes.

Te dejo un par de casos para que veas como actúa. Observa que  devuelve los dígitos en orden correcto, no hay que darles la vuelta:


Citar

binario(11)=b(11)=
=10*b(5)+1=
=10*(10*b(2)+1)+1=100*b(2)+11=
=100*(10*b(1))+0)+11=1000*b(1)+11=
=1000*(1)+11=1011

binario(12)=b(12)=
=10*b(6)+0=
=10*(10*(b(3)+0)=100*b(3)=
=100*(10*b(1))+1)=1000*b(1)+100=
=1000*(1)+100=1100



Saluditos!. .... ...

CCross

#9
leosansan gracia por darte el tiempo de aclararme la duda que tenia, esto de la
recursividad esta complicadita. Y efectivamente una solucion recursiva generalmente
es menos eficiente por el consumo de mayor de recursos que la iterativa. Sin embargo en
muchas situacion nos puede facilitar las cosas.

Saludos..  ;D