3N+1 Problem/1002_2

연습장에서 이것저것 적어보기 시도. 처음에는 각 결과 수 간에 무언가 수열이 있을까 해서 적어봄.

~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 을 하여 이용할 수 있겠다는 생각이 들다.
연습장에 의사 코딩 5분정도 한 뒤, 바로 코드로 옮기고 실행.

~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

지난번의 문제를 풀었을때 '접근법' 도 같이 생각하여 문제 해결방법을 익힌것이 추후의 문제(결과 상으로는 전혀 다른 알고리즘)의 해결법을 알아내는데 좋은 접근법을 제공해준 것이 느낌이 좋았다. 새 해결책을 떠올리는데 10분이 안걸리고, 비교적 효과적인 알고리즘이 나온 점에서 기분이 좋은 중.
--1002