Ver Mensaje Individual
  #4 (permalink)  
Antiguo 23/02/2014, 11:46
CalgaryCorpus
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 15 años, 9 meses
Puntos: 61
Respuesta: Desafíos 2014 - Semana 4

Muestro unas pequeñas optimizaciones al programa mostrado por sukoy, basado en la observacion que en el rango (a,b) es posible que exista un rango (a..lowlimit) en que cada indice sea la mitad de otro indice dentro del rango (lowlimit+1,b) y por tanto cada uno de los num[i] sera menor que los num[j] con i en el primer rango y j en el segundo y como se busca el valor mayor resulta superfluo revisar ese rango.

Ademas, si al recorrer hacia atras, se encuentran elementos en el cache, quiere decir que pertenecen a un recorrido previo y por tanto el indice actual no puede ser el maximo y se puede descartar de manera segura.

Aqui van:

Código Python:
Ver original
  1. def max_cycle(a, b):
  2.  
  3.     cache = {1:1}
  4.  
  5.     def num(cache, n):
  6.         if n in cache: return cache[n]
  7.         if n % 2:
  8.             r = cache[n] = 1 + num(cache, 3 * n + 1)
  9.         else:
  10.             r = cache[n] = 1 + num(cache, n >> 1 )
  11.         return r
  12.  
  13.     def sec(a, b):
  14.         if a == b: return num(cache,a)
  15.         maxim = 0
  16.         if a > b: a,b = b,a
  17.         lowlimit = max(a,b/2,2)
  18.         for i in xrange(b,lowlimit-1,-1):
  19.             if i in cache: continue
  20.             tr = num(cache, i)
  21.             if tr > maxim:
  22.                 maxim = tr
  23.         return maxim
  24.  
  25.     return sec(a, b)
__________________
Visita mi perfil en LinkedIn

Última edición por CalgaryCorpus; 24/02/2014 a las 11:55