U E D R , A S I H C RSS

3N+1 Problem/Leonardong

์ฒซ์งธ

~cpp 
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()

๋‘˜์งธ

~cpp 
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() 


์…‹์งธ

~cpp 
# 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

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:15
Processing time 0.0077 sec