estructuras de datos

[Beginner Web]

hoal quiero apsar este algoritmos a recursivo e ayudan? solo tengo esto

Código (cpp) [Seleccionar] Expandir

int vertir-un-numero(int n)
{
tpila pila;
init_stack(pila);
while(n>0){
push_stack(pila,n%10);
n/=10;
}
for(int i=0;empty_stack(pila)==false;i++)
n+=pop_stack(pila)*pow(10.0,i);
return n;
}

[dijsktra]

Pero es que nadie va a responder a nuestra programadora argentina?  

hoal quiero apsar este algoritmos a recursivo e ayudan? solo tengo esto

Código (cpp) [Seleccionar] Expandir

int vertir-un-numero(int n)
{
tpila pila;
init_stack(pila);
while(n>0){
push_stack(pila,n%10);
n/=10;
}
for(int i=0;empty_stack(pila)==false;i++)
n+=pop_stack(pila)*pow(10.0,i);
return n;
}

Antes de dar la solución, aprecio un fallo de eficiencia... No es necesario en el segundo bucle expresar pow(10.0,i)... puedes poner

Código (c) [Seleccionar] Expandir


for(int i=0,power=1;empty_stack(pila)==false;i++)
{
n+=pop_stack(pila)*power;
power *=10 ;
}


Y te ahorras la función pow que trabaja con floats, algo que es "peligroso" en computación.


Lo normal es que te den el iterativo y tengas que hacer el recursivo. Si la función recursiva es lineal (con una sola llmada) entonces hay truco fácil. (Un poco largo para explicar aquí)

Lo que yo hago en estas lineas es dar el programa al que se aplica el truco. Es una función lineal no final, es decir, después de la llamada hay quqe hacer algo más, que en la veris'on iterativa realiza el segundo bucle...

Allá va:

Código (cpp) [Seleccionar] Expandir


int invertir_un_numeroG(const int N,int &power);

/*
P : A[0..log(N)) and N = \sum i : 0 <= i < log(N) : A[i]*10^i
Q : M = \sum i : 0 <= i < log(N) : A[i]*10^(log(N)-i)
*/
int invertir_un_numero(const int N)
{
 int power;
 return invertir_un_numeroG(N,power);
}


/* P' : P
  Q' : Q and power=10^log(N)
*/
int invertir_un_numeroG(const int N,int &power)
{
 if (N==0) { power = 1 ; return 0 ; }
 int result;
 result = invertir_un_numeroG(N/10,power);
 result += N%10 * power ;
 power *= 10;
 return result;
}

#include <iostream>

using namespace std;

int main(int argc, char* args[])
{
 int N;
 for( ; cin >> N ; )
   cout << invertir_un_numero(N) << endl;
 return 0;
}


Y algunos casos de prueba

Código [Seleccionar] Expandir

bash-2.04$ ./main
45
54
4678
8764
12345678
87654321