AlgorithmQuiz/3Plus1DynamicProgramming으로... --windist

캐쉬에 저장하고, 이미 계산한 값에 대해서는 캐쉬의 값을 이용. yong27의 코드보다 훨씬 빠르게 동작한다고함.

   1 cache = dict()
   2 def getCycleLength(i):
   3     if i == 1:
   4         cnt = 1
   5     elif cache.has_key(i):
   6         cnt = cache[i]
   7     else:
   8         if i % 2:
   9             j = i * 3 + 1
  10         else:
  11             j = i / 2
  12         cnt = getCycleLength(j) + 1
  13     cache[i] = cnt
  14     return cnt
  15 
  16 def getMaxCycleLength(i, j):
  17     cyclelist = list()
  18     for k in range(i, j + 1):
  19         cyclelist.append(getCycleLength(k))
  20     print i,j, max(cyclelist)
  21     return max(cyclelist)
  22 
  23 def main():
  24     i,j = map(int,raw_input().split())
  25     print i, j, getMaxCycleLength(i,j)
  26 
  27 if __name__=='__main__':
  28     import time
  29     pre = time.time()
  30     print getMaxCycleLength(1,100000)
  31     post = time.time()
  32     print post - pre

AlgorithmQuiz/3Plus1/windist (last edited 2013-08-07 13:30:11 by 61)

web biohackers.net