ACM (
Association for Computing Machinery) organiza unas competencias de programación llamadas
ICPC (
International Collegiate Programming Contest). En esta dirección hay muchos problemas de las competencias:
http://acm.uva.es/problemset/.
Este es el enunciado del primer problema de la guía: http://acm.uva.es/p/v1/100.html
El fin de semana hice esta solución:
(nota: los lenguajes soportados por las competencias son C y Java, mi solución está escrita en Python por que me resulta más ágil. De todas formas importa más el algoritmo que el lenguaje.)
def odd(n):
return not (n%2 == 0)
def tnu(n=1):
print n
if (n == 1): return
elif (odd(n)): n = 3*n+1
else: n = n/2
tnu(n) # la recursividad por la cola es evitable
>>> tnu(22)
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1
La longitud del ciclo para un n dado es la cantidad de valores que la función tnu() develve (incluido el 1 final)
El problema pide leer un archivo con pares i,j y para cada par devolver la mayor longitud de ciclo para todos los enteres enter i y j incluyendo a i y a j.
Solución Exaustiva
Una solución exaustiva podría consistir en calcular para cada par i,j todos las longitudes de ciclo asociadas y devolver la mayor.
Redefino tnu para que en lugar de imprimir los sucesivos valores de n devulva una lista con los valores, el segundo argumento de la función es una lista vacía.
def tnu(n,l):
#print n
l.append(n)
if (n == 1): return l
elif (odd(n)): n = 3*n+1
else: n = n/2
return tnu(n,l) # la recursividad por la cola es evitable
Suponiendo que ya se leyeron los pares del archivo correspondiente y se tienen en una lista llamada pairs:
def solv1(pairs):
for i,j in pairs:
maxc = 0
for n in range(i,j+1):
maxc = max(len(tnu(n,[])),maxc)
print i, j, maxc
>>> pairs = [(1,10),(88,123),(7,1),(55,455),(10000,10003)]
>>> solv1(pairs)
1 10 20
88 123 119
7 1 0
55 455 144
10000 10003 180
>>> pairs = [(1,10),(100,200),(201,210),(900,1000)]
>>> solv1(pairs)
1 10 20
100 200 125
201 210 89
900 1000 174
Bien, esta solución ANDA, pero no es óptima. De hecho probablemente sea la solución menos eficiente :-) la de la fuerza bruta.
Solución Dinámica
La idea es almacenar los resultados ya calculados para no tener que hacerlos una y otra vez. Si se pide la máxima longitud de ciclo (mlc) enter 100 y 200 y obtengo 125 y luego se pide la máxima longitud de ciclo enter 1 y 300, voy a calcular la mlc para el par 1,100, luego lo haré para 200,300 y luego compararé los resultados con 125 quedándome con el mayor de los 3.
Pero.. que pasa si ya he calculado la mlc para los valores entre 2 y 99?
def solv1din(pairs,dic):
for i,j in pairs:
maxc = f_maxc(i,j,dic)
print i, j, maxc
dic[i,j]=maxc
def f_maxc(i,j,dic):
wide = 0
for a,b in dic.keys():
if a == i and b == j: return dic[a,b]
if (i<=a and b<=j and b-a > wide):
f,g = a,b
wide = b-a
if (wide == 0): #ningún rango del diccionario estaba dentro de i,j
maxc = 0
for n in range(i,j+1):
maxc = max(len(tnu(n,[])),maxc)
return maxc
else:
return max(f_maxc(i,f,dic),dic[f,g],f_maxc(g,j,dic))
>>> solv1din(pairs,{})
1 10 20
100 200 125
201 210 89
900 1000 174
Una versión no recursiva de tnu podría ser algo como esto:
def tnu(n):
l = []
while(n != 1):
l.append(n)
if (odd(n)): n = 3*n+1
else: n = n/2
l.append(1)
return l
Download
- Una implementación completa que resuelve el problema: 3n+1.py
- Un archivo de entrada de ejemplo: input100.txt
Ejemplo de uso
juanjo@sarge:~/problemas$ ./3n+1.py input100.txt
1 10 20
100 200 125
201 210 89
900 1000 174
88 123 119
7 1 0
55 455 144
10000 10003 180
