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.0135 sec