근 ¶
기 . 각 결과 간 까 .
5 , 기고 .
~cpp 1 2 8 3 6 9 17 4 20 7 9 1 6 -5 3 3 8 -13 17 -13 2간 계 , UglyNumber 근(DynamicProgramming) . 계값 계 까 각 .
~cpp n 값 1 : 1 2 : 2 -> 1 3 : 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 4 : 4 -> 2 -> 1 . .n 값 count cycle Length 값 고 과, 값 caching 겠 각 .
~cpp
class CycleLength:
def __init__(self):
self._cache = {1:1}
def createTable(self,i,j):
return [self.value(each) for each in range(i,j)]
def value(self,n):
if self._cache.get(n) is not None: return self._cache.get(n)
if n % 2 == 1:
self._cache[n] = self.value(3*n+1)+1
return self._cache[n]
else:
self._cache[n] = self.value(n/2)+1
return self._cache[n]
def maxCycleLengthInRange(self,i,j):
#return max(self.createTable(i,j))
maxValue=0
for each in range(i,j):
maxValue = max(maxValue,self.value(each))
return maxValue
def testOne():
r"""
>>> c=CycleLength()
>>> [c.value(n) for n in range(1,5)]
[1, 2, 8, 3]
>>> c.maxCycleLengthInRange(1,10)
20
>>> c.maxCycleLengthInRange(100,200)
125
>>> c.maxCycleLengthInRange(201,210)
89
>>> c.maxCycleLengthInRange(900,1000)
174
"""
def main():
import doctest
doctest.testmod()
def main2():
c=CycleLength()
print c.maxCycleLengthInRange(1,999999)
if __name__=="__main__":
import time
start=time.time()
import psyco
psyco.bind(main2)
main2()
end = time.time()
print "time :", end-start
