Foro de elhacker.net

Programación => Scripting => Mensaje iniciado por: h0oke en 27 Marzo 2010, 15:57 pm



Título: Python - Duda Algoritmo
Publicado por: h0oke en 27 Marzo 2010, 15:57 pm
Código
  1. import math
  2.  
  3. def menor(a,b):
  4.    return a if(a <= b) else b
  5.  
  6. def raiz2(a,b):
  7.    c = a//b
  8.    if(math.fabs(b - c) <= 1):
  9.        return menor(b,c)
  10.    else:
  11.        raiz2(a,(b + c)//2)
  12.  
  13.  
  14.  
  15. a = 170000
  16. b = raiz2(a,3)
  17. print(b)
  18.  

¿Por qué razón no devuelve el valor que es 412?

PD: Depuré hasta que llega al printf y ahí no hallo el error.


Título: Re: Python - Duda Algoritmo
Publicado por: leogtz en 27 Marzo 2010, 23:23 pm
Código
  1. import math
  2.  
  3. def menor(a,b):
  4.    return a if(a <= b) else b
  5.  
  6. def raiz2(a,b):
  7.    c = a//b
  8.    if(math.fabs(b - c) <= 1):
  9.        return menor(a,b)
  10.    else:
  11.        raiz2(a,(b + c)//2)
  12.  
  13.  
  14.  
  15. a = 170000
  16. b = raiz2(a,3)
  17. print(b)
  18.  

¿Por qué razón no devuelve el valor que es 412?

PD: Depuré hasta que llega al printf y ahí no hallo el error.

¿Qué algoritmo estás usando?
Pon el pseudocódigo del mismo, para ver si alguno que use python te ayuda.


Título: Re: Python - Duda Algoritmo
Publicado por: h0oke en 28 Marzo 2010, 04:45 am
Código:
Raiz2(a) = iter(a,3)
donde
        iter(a,x) =
                      sea c = [a/x] {[] = piso}
                      si |x - c| <= 1 contestar min(x,c)
                      sino
                            iter(a,[(x+c)/2]

PD: Modifiqué el menor(a,b) por menor(b,c)


Título: Re: Python - Duda Algoritmo
Publicado por: Novlucker en 29 Marzo 2010, 02:20 am
Aún no entiendo la lógica del algoritmo :xD .. es decir, la finalidad :-\

Saludos


Título: Re: Python - Duda Algoritmo
Publicado por: leogtz en 29 Marzo 2010, 19:20 pm
Se supone que para calcular una raíz cuadrada.

¿Cómo se llama el algoritmo?


Título: Re: Python - Duda Algoritmo
Publicado por: Masita en 29 Marzo 2010, 20:19 pm
No entiendo muy bien la logica de tu algoritmo.... De todos modos si lo que quieres es hacer una raiz cuadrada, puedes hacerlo con el modulo math.

math.sqrt(a)


Título: Re: Python - Duda Algoritmo
Publicado por: gabymar en 29 Marzo 2010, 23:24 pm
Hola algorithm, parece que la recursividad te da un pequeño problema, la iteracion que encuentre el resultado devolvera con return el valor de la raiz, pero he ahi el problema, ¿ a quien le devuelve el valor?, pues a la iteracion anterior que es la que le llamo, y esta se queda con el valor, pues no hay un retorno hacia atras de este resultado.

   una solucion puede ser esta, si te das cuenta la funcion devuelve None o sea nada si no llegamos a la solucion, entonces cuando la solucion se alcance cada iteracion respondera a la anterior con el valor x.

   modifico, no es necesario comprobar la respuesta de las siguientes iteraciones, puesto que no habra respuesta hasta que el resultado sea el esperado.
   Saludos : Gaby

Código:

import math
 
def menor(a,b):
    return a if(a <= b) else b
 
def raiz2(a,b):
    c = a//b
    if(math.fabs(b - c) <= 1):
        return menor(b,c)  
    else:
        return raiz2(a,(b + c)//2)

 
 
 
a = 170000
b = raiz2(a,3)
print(b)



Título: Re: Python - Duda Algoritmo
Publicado por: h0oke en 30 Marzo 2010, 03:12 am
Muchas gracias gabymar, excelente respuesta...

Con respecto a las dudas anteriores, es simplemente un algoritmo para encontrar la raíz cuadrada de un número por método de bisección utilizando únicamente operaciones de alu.