¶
보 . 는 무 .
딩 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
