AlgorithmQuiz/3Plus1IteratorGenerator를 이용해서... --whitekid

   1 import sys
   2 from types import *
   3 
   4 class ThreePlusOneIterator(object):
   5     def __init__(self, num):
   6         object.__init__(self)
   7 
   8         assert type(num) == IntType
   9         assert 0 <= num and num<=1000000
  10 
  11         self._initial =  self._current = num
  12         self._cycleLength = None
  13 
  14     def __iter__(self): return self.next()
  15 
  16     def next(self):
  17         while self._current <> 1:
  18             if self._current % 2 == 0: self._current /= 2
  19             else: self._current = self._current * 3 + 1
  20 
  21             yield self._current
  22 
  23 
  24     def _getCycleLength(self):
  25         if not self._cycleLength:
  26             self._cycleLength = len(list(iter(ThreePlusOneIterator(self._initial)))) + 1
  27         return self._cycleLength
  28 
  29     cycleLength = property(_getCycleLength)
  30 
  31 
  32 
  33 class App:
  34     def run(self):
  35         for line in sys.stdin:
  36             (i, j) = line.strip().split()
  37             print i, j, self.getMaxCycle( int(i), int(j))
  38 
  39 
  40     def getMaxCycle(self, i, j):
  41         """ 주어진 수의 사이의 Max Cycle 구하기 """
  42         maxCycle = 0
  43         for x in range(min(i,j), max(i,j)+1):
  44             maxCycle = max(maxCycle, ThreePlusOneIterator(x).cycleLength )
  45         return maxCycle
  46 
  47 
  48 if __name__ == '__main__':
  49     App.run()

아래는 테스트케이스

   1 import unittest
   2 
   3 from ThreePlusOne import *
   4 
   5 class ThreePlusOneTestCase(unittest.TestCase):
   6     def testOneStep(self):
   7         assert 11 == iter(ThreePlusOneIterator(22)).next()
   8         assert 34 == iter(ThreePlusOneIterator(11)).next()
   9 
  10     def test(self):
  11         seq = map( lambda x: int(x), '11 34 17 52 26 13 40 20 10 5 16 8 4 2 1'.split())
  12         assert seq == list(iter(ThreePlusOneIterator(22)))
  13 
  14     def testCycleLength(self):
  15         assert ThreePlusOneIterator(22).cycleLength == 16
  16         assert ThreePlusOneIterator(1).cycleLength == 1
  17 
  18 
  19 class ThreePlusOneAppTestCase(unittest.TestCase):
  20     def testGetMaxCycles(self):
  21         assert App().getMaxCycle(3, 5) == 8
  22 
  23     def testRun(self):
  24         app = App()
  25 
  26 
  27 if __name__ == '__main__':
  28     unittest.main()

Generator를 사용하면

   1 def getCycle(seed):
   2     while True:
   3         yield seed
   4         if seed == 1: break
   5         seed = seed % 2 and seed * 3+1 or seed / 2
   6 
   7 def getCycleCountByRange(start, end):
   8     for i in range(start, end+1):
   9         yield len([x for x in getCycle(i)])
  10 
  11 def run(data):
  12     for line in data.split('\n'):
  13         start, end = map(int, line.split())
  14         print start, end, \
  15             max([count for count in getCycleCountByRange(start, end)])
  16 
  17 
  18 if __name__ == '__main__':
  19     run('''1 22
  20 2 999
  21 3 777
  22 3 98''')

AlgorithmQuiz/3Plus1/whitekid (last edited 2013-08-19 14:54:11 by 61)

web biohackers.net