AlgorithmQuiz/3Plus1을 DynamicProgramming으로... --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