imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:15Z

New page

== 첫째 ==
class AOI3nPlus1ProblemRunner:
def getMaximumCycleLength(self, aFrom, aTo):
max = 0
for i in range( aFrom, aTo + 1):
cycleLength = self.getCycleLength(i)
if max < cycleLength:
max = cycleLength
return max
def getCycleLength( self, aStart ):
n = aStart
cycleLength = 1
while n is not 1:
cycleLength = cycleLength + 1
if n % 2 is not 0:
n = 3 * n + 1
else:
n = n / 2
return cycleLength
def run(self):
numFrom = input("")
numTo = input("")
print self.getMaximumCycleLength(numFrom, numTo)

#########################################################################
import unittest

class AOI3nPlus1ProblemTestCase(unittest.TestCase):
def setUp(self):
self.runner = AOI3nPlus1ProblemRunner()
def testGetMaximumCycleLength(self):
self.assertEquals( 1, self.runner.getMaximumCycleLength( 1, 1 ) )
self.assertEquals( 20, self.runner.getMaximumCycleLength( 1, 10 ) )
self.assertEquals( 125, self.runner.getMaximumCycleLength( 100, 200 ) )
self.assertEquals( 89, self.runner.getMaximumCycleLength( 201, 210 ) )
self.assertEquals( 174, self.runner.getMaximumCycleLength( 900, 1000) )
def testGetCycleLength(self):
self.assertEquals( 1, self.runner.getCycleLength(1) )
self.assertEquals( 5, self.runner.getCycleLength(16) )
self.assertEquals( 16, self.runner.getCycleLength(22) )

#########################################################################
if __name__ == '__main__':
## unittest.main()
AOI3nPlus1ProblemRunner().run()

== 둘째 ==
import psyco
MAXIMUM = 10000
class AOI3nPlus1ProblemRunner:
def __init__(self):
self.cycleLens = {}
def getMaximumCycleLen(self, aFrom, aTo):
maximum = 0
for i in range( aFrom, aTo + 1):
if self.getCycleLen(i) > maximum:
maximum = self.getCycleLen(i)
self.cycleLens[i] = maximum
return maximum
def getCycleLen( self, n ):
if n not in self.cycleLens:
self.storeCycleLen( n )
return self.getStoredCycleLen(n)
def run(self):
numFrom = input("")
numTo = input("")
print self.getMaximumCycleLen(numFrom, numTo)

def storeCycleLen(self, aN):
n = aN
cycleLen = 1
while n is not 1:
if n in self.cycleLens:
cycleLen = cycleLen + self.cycleLens[n] - 1
break
cycleLen += 1
if n % 2 is not 0:
n = 3 * n + 1
else:
n = n / 2
self.cycleLens[aN] = cycleLen
def getStoredCycleLen(self, aN):
if aN not in self.cycleLens:
return 0
return self.cycleLens[aN]

#########################################################################
import unittest

class AOI3nPlus1ProblemTestCase(unittest.TestCase):
def setUp(self):
self.runner = AOI3nPlus1ProblemRunner()
def testGetMaximumCycleLen(self):
self.assertEquals( 1, self.runner.getMaximumCycleLen( 1, 1 ) )
self.assertEquals( 20, self.runner.getMaximumCycleLen( 1, 10 ) )
self.assertEquals( 125, self.runner.getMaximumCycleLen( 100, 200 ) )
self.assertEquals( 89, self.runner.getMaximumCycleLen( 201, 210 ) )
self.assertEquals( 174, self.runner.getMaximumCycleLen( 900, 1000) )
def testGetCycleLen(self):
self.assertEquals( 1, self.runner.getCycleLen(1) )
self.assertEquals( 5, self.runner.getCycleLen(16) )
self.assertEquals( 16, self.runner.getCycleLen(22) )
def testStoreCycles(self):
self.assertEquals( 0, self.runner.getStoredCycleLen(0) )
self.runner.storeCycleLen(22)
self.assertEquals( 16, self.runner.getStoredCycleLen(22) )
def testTime(self):
# goal = 999,999 in 4 sec
self.runner.getMaximumCycleLen(1,MAXIMUM)
## self.runner.getCycleLen(MAXIMUM)
self.runner.storeCycleLen(MAXIMUM)
#########################################################################
if __name__ == '__main__':
psyco.full()
unittest.main(argv=('','-v'))
## AOI3nPlus1ProblemRunner().run()

== 셋째 ==
# 45m after tuning
# total = 3h 11m 11s
import unittest
TEST_MAX = 100000
MAX = 1000000
##TEST_MAX = MAX - 1

storedCycleLens = [0] * MAX
CUTOFF = 100

def preProcessing():
i = 1
cycleLen = 1
while i < MAX:
storedCycleLens[i] = cycleLen
cycleLen += 1
i *= 2

def getCycleLen(aN):
n = aN
result = 1
while n != 1:
result += 1
if n % 2 != 0:
result += 1
n = (3*n+1) / 2
else:
n /= 2
if n < MAX and\
storedCycleLens[n] != 0:
result += storedCycleLens[n] - 1
break
## if getStoredCycleLen(n) is not 0:
## return getStoredCycleLen(n) + result - 1
return result
def storeCycleLen(aN):
storedCycleLens[aN] = getCycleLen(aN)

def getStoredCycleLen(aN):
if aN < 0 or aN >= MAX:
return 0
return storedCycleLens[aN]

def getMaxCycleLen(aStart, aEnd):
maximum = 0
interval = 1
if CUTOFF < aEnd - aStart:
interval = 2
if aStart % 2 == 0:
aStart -= 1
for n in range(aStart, aEnd+1, interval):
cycleLen = getCycleLen(n)
if maximum < cycleLen:
maximum = cycleLen
storedCycleLens[n] = cycleLen
return maximum

class MyTestCase(unittest.TestCase):
def testGetCycleLen(self):
tests = [(1,1), (9,20), (16,5), (MAX-1,259)]
for n, expected in tests:
self.assertEquals( expected, getCycleLen(n) )
for n in range(MAX-1000, MAX):
getCycleLen(n)
def testgetMaxCycleLen(self):
tests = [(1,1,1), (1,16,20), (900,1000,174), (1,1000,179)]
for start, end, expected in tests:
self.assertEquals(expected, getMaxCycleLen( start, end ) )
def testStoreCycleLen(self):
tests = [(1,1), (16,5), (MAX-1,259)]
for n, expected in tests:
storeCycleLen( n )
self.assertEquals( expected , getStoredCycleLen(n) )
def testTime(self):
getMaxCycleLen(1, TEST_MAX)
## self.assertEquals(525, getMaxCycleLen(1, MAX))
if __name__ == '__main__':
preProcessing()
## unittest.main()
timeTest = MyTestCase("testTime")
runner = unittest.TextTestRunner()
runner.run(timeTest)

== Thread ==
절대 쉽지 않은 문제였다. 아직 수행시간이 턱없이 길다. 사전형 멤버를 이용해 계산했던 부분은 저장해두어 다시 쓰도록 하였다. 답답하다. PsyCo라는 모듈을 새롭게 알알게되었다. --[[Leonardong]]
싸이코? --[[강희경]]

셋째 코드에서 해본 새로운 시도는 다음과 같다.
* MAX(100000)개의 원소를 가진 리스트에 계산했던 CycleLength를 저장한다.
* 3n+1은 항상 짝수이므로 짝수 검사를 한 번 건너뛴다.
* 2의 제곱수들은 CycleLength를 예상할 수 있으므로 입력 받기 전에 미리 계산해둔다.
* CycleLength를 구하는 과정에서 n이 짝수일 때만 저장된 값이 있는지를 검사한다.
* 구하는 범위가 Cutoff보다 크면 시작하는 수가 홀수일 때 CycleLength가 클 것이므로 홀수부터 시작해서 짝수는 무시하고 구한다.

파이선만으로 12초가 걸린다. 새로운 걸 한 번씩 시도할 때마다 시간이 줄어들어 신기했다. 중간에 코드를 고치면서 시간 테스트만 돌리다가 답이 잘못 나오는 코드를 가지고 한동안 작업했었다. 새로운 기능을 추가하면 테스트를 전부 돌려야겠다. --[[Leonardong]]

확신이 가지 않는 cutoff부분을 빼더라도 PsyCo를 쓰면 2초 안에 통과한다. 3시간 동안 10초 정도를 줄였는데, 10분만에 10초를 줄였다. 시간을 줄여야 하는데 정말 수가 안 떠오르면 PsyCo가 꽤 도움이 될 것이다. 남용은 조심해야겠다.--[[Leonardong]]
----
[[AOI]], [[3N+1Problem]]

3N+1Problem/Leonardong - Revision history

imported>Unknown at 05:22, 7 February 2021