Una implementación mejor está aquí.
En la página de
PuntoPeek encontré el siguiente problema propuesto: "Calcular los n primeros
números del conjunto de Wirth".
El conjunto de Wirth se
define de la siguiente manera:
"El conjunto de Wirth es un
subconjunto de los enteros positivos que cumple con la siguiente regla: el 1
pertenece al conjunto y si un numero k pertenece al conjunto entonces los
números 2*k+1 y 3*k+1 pertenecen al conjunto."
La solución de PuntoPeek es
mucho mejor. No calcula números extra.
Por mi parte, no
hubiera seguido insistiendo con el problema del Conjunto de Wirth si no
hubiera tenido la sensación que la solución es mucho, pero mucho más
simple.
Para empezar me basé en la
solución propuesta de PuntoPeek. Luego de analizarla a simple vista, noté que
todo se reduce a:
1. En un array de tamaño
fijo n ingreso el 1 como primer elemento,
2. Recorro todos los números
naturales y le pregunto a cada uno: ¿eres el resultado de tomar un número k del
array y realizar las operaciones: 3k+1 ó 2k+1? si es así, te añado al array.
3. Me detengo hasta
completar todos los elementos del array.
Lo curioso es que el
postulado del conjunto de Wirth hace pensar en una operación "y" (and
lógica):
"Si un número k es elemento del conjunto, también lo son los números
3k+1 y 2k+1", cuando en realidad es un or lógico: cada número k del
conjunto genera 3k + 1
y 2k + 1. Entonces, para que otro número i sea del conjunto debe cumplir
cualquiera de estas dos condiciones: i = 3k + 1 ó i = 2k + 1. O mejor
dicho:
(i-1)/3 ó (i-1)/2 debe darnos un número k que ya está en nuestro array..
Con el método de PuntoPeek
se buscan los primeros números n preguntando si cumplen
cualquiera de las dos condiciones. La variable k es conocida, pues ya está
almacenada en el array.
En Python, el algoritmo es:
Uso datos de tipo float
(coma flotante) para descartar los números que den resultados decimales (la
variable i es en realidad un entero con representación flotante). Así evito
falsos positivos o falsos rechazados por los errores que se introducen al
redondear la división entre enteros.
El resultado es:
Lo interesante de este
algoritmo es que sirve para generar cualquier serie de números que cumplan una
condición. Basta cambiar los primeros elementos del array y la condición, pues
lo que en realidad hace es extraer del conjunto de los números naturales todos
aquellos números que cumplen una condición.
La serie Fibonacci se genera
de la siguiente forma (como no implica divisiones, no necesito números de coma
flotante):
Para las potencias de 2:
Para los factoriales
(números que son el factorial de otro):
def Wirt(n):
result = [1.0]
i=1.0
while len(result)<=n:
i+=1.0
if (i not in result and ((i-1)/2 in result or (i-1)/3 in result)):
result.append(i)
return [int(x) for x in result]
def Fib(n):
result = [0, 1]
i=0
while len(result)<=n:
i+=1
if i== result[-1] + result[-2]:
result.append(i)
return result
def Pot2(n):
result = []
i=0
p=0
while len(result)<=n:
i+=1
if i== 2**p:
result.append(i)
p+=1
return result
def Fact(n):
def fact(p):
if p==1:
return p
else:
return p*fact(p-1)
result = []
i=0
p=1
while len(result)<=n:
i+=1
if i== fact(p):
result.append(i)
p+=1
return result
print Wirt(50)
print Fib(10)
print Pot2(10)
print Fact(5)
result = [1.0]
i=1.0
while len(result)<=n:
i+=1.0
if (i not in result and ((i-1)/2 in result or (i-1)/3 in result)):
result.append(i)
return [int(x) for x in result]
def Fib(n):
result = [0, 1]
i=0
while len(result)<=n:
i+=1
if i== result[-1] + result[-2]:
result.append(i)
return result
def Pot2(n):
result = []
i=0
p=0
while len(result)<=n:
i+=1
if i== 2**p:
result.append(i)
p+=1
return result
def Fact(n):
def fact(p):
if p==1:
return p
else:
return p*fact(p-1)
result = []
i=0
p=1
while len(result)<=n:
i+=1
if i== fact(p):
result.append(i)
p+=1
return result
print Wirt(50)
print Fib(10)
print Pot2(10)
print Fact(5)
Lo malo de este
algoritmo:
para el caso del factorial y las potencias de dos es lentísimo. Tarda
horas (literalmente) en calcular potencias de 2 mayores a 2^20, y lo
mismo
sucede para factoriales mayores al factorial de 10. Ir preguntando a
cada número
si cumple una condición es muy ineficiente para series de números cuyos
valores
crecen de forma geométrica o exponencial.
Pero ha sido una buena práctica de aprendizaje :)
