3N+1 Problem/황재선

~cpp 
#include <iostream> 
using namespace std; 
 
void input(); 
int process(); 
int findMaxCycle(int aNum, int aCount); 
void output(int aMaxCycle); 
 
int inputNum[2]; 
 
int main() 
{ 
        input(); 
        int max = process(); 
        output(max); 
        return 0; 
} 
 
void input() 
{        
        cout << "<< "; 
        cin >> inputNum[0] >> inputNum[1]; 
} 
 
int process() 
{ 
        int interNum = inputNum[0];      
        int maxCycle; 
        int temp; 
        int count = 1; 
 
        while (interNum <= inputNum[1]) 
        { 
                count = 1;               
                temp = findMaxCycle(interNum, count); 
                if (maxCycle < temp) 
                        maxCycle = temp; 
                interNum++; 
        } 
        return maxCycle; 
} 
 
int findMaxCycle(int aNum, int aCount) 
{ 
        if (aNum == 1) 
                return aCount; 
        if (aNum % 2)    
                aNum = 3 * aNum + 1;     
        else     
                aNum = aNum / 2;         
        aCount++; 
        findMaxCycle(aNum, aCount); 
} 
 
void output(int aMaxCycle) 
{ 
        cout << aMaxCycle << endl; 
} 

2005.1.9

~cpp 
import unittest
import psyco

class ThreeNPlusOne: 
    def __init__(self): 
        self.cycleLength = 0
        self.cycleDic = {}
         
    def compute(self, num):
        self.cycleLength = 0
        while (num != 1):
            self.cycleLength += 1

            if num % 2:
                num = 3 * num + 1
            else:
                num /= 2
            if str(num) in self.cycleDic:
                return self.cycleLength + self.cycleDic[str(num)]

        self.cycleLength += 1
        
        return self.cycleLength
        
    def computeAll(self, num1, num2): 
 
        maxLength = 0 
         
        for n in range(num1, num2+1):
            length = self.compute(n)
            self.cycleDic[str(n)] = length
            
            if length > maxLength: 
                maxLength = length

        return maxLength
 
class ThreeNPlusOneTest(unittest.TestCase): 
    def setUp(self): 
        self.u = ThreeNPlusOne() 
 
    def testOneCal(self): 
        num = 22 
        expected = 16 
        self.assertEquals(expected, self.u.compute(num)) 
         
    def testTwoCal(self):
        self.assertEquals(20, self.u.computeAll(1,10))
        self.assertEquals(125, self.u.computeAll(100, 200))
        self.assertEquals(89, self.u.computeAll(201, 210))
        self.assertEquals(174, self.u.computeAll(900, 1000))
        self.assertEquals(525, self.u.computeAll(1, 999999)) 

def main():
    n = raw_input()
    n1, n2 = n.split()
    o = ThreeNPlusOne()
    result = o.computeAll(int(n1), int(n2))
    print n1, n2, result
    
         
if __name__ == '__main__':
    psyco.full()
    unittest.main(argv=('','-v'))
    #main()

2005.1.13

~cpp 
import unittest 
import psyco 

cycleDic = dict()
def compute(num):    
    cycleLength = 1
    while (num != 1):
        num = (num %2 and 3 * num + 1) or num / 2
        if num in cycleDic:
            return cycleLength + cycleDic[num]
        cycleLength += 1
    return cycleLength
     
def computeAll(num1, num2):
    maxLength = 0
    for n in range(num1, num2+1):
        length = compute(n)
        cycleDic[n] = length
        if length > maxLength:  
            maxLength = length
    return maxLength 
  
class ThreeNPlusOneTest(unittest.TestCase):
    def testOneCal(self):
        num = 22  
        expected = 16  
        self.assertEquals(expected, compute(num))  
          
    def testTwoCal(self): 
        self.assertEquals(20, computeAll(1,10)) 
        self.assertEquals(125, computeAll(100, 200)) 
        self.assertEquals(89, computeAll(201, 210)) 
        self.assertEquals(174, computeAll(900, 1000)) 
        self.assertEquals(525, computeAll(1, 999999))  
 
def main(): 
    n = raw_input() 
    n1, n2 = n.split()
    result = computeAll(int(n1), int(n2))
    print n1, n2, result      
          
if __name__ == '__main__':
    psyco.full() 
    unittest.main(argv=('','-v'))
    #main()

입력은 0과 1000000 사이의 값을 갖는 한 쌍의 정수이다. 1과 999999를 입력한 경우 몇 초 이내에 답이 나올까. Python으로 4초 이내를 목표로 구현했다. 하지만 만족할 만한 결과가 나오지 않았다. 안타깝게도 더이상 최적화할 묘안이 떠오르지 않는다 -- 재선

http://bioinfo.sarang.net/wiki/AlgorithmQuiz_2f3Plus1 에서 yong27님의 소스코드를 보았다. 소스가 정말 깔끔했다. 실행속도가 빨라서 그 원인을 분석해가며 지난번 작성했던 코드를 수정했다. 나의 목적은 0.001초라도 빠르게 결과를 출력하는 것이었다. 실행시간을 최소화하기위해 클래스마저 없앴다. 특히 두 부분을 수정하니 실행시간이 현저히 줄었다. 하나는 클래스 멤버변수를 제거하고 지역변수화한 경우인데 왜 그런지 모르겠다. 둘째는 사전형 타입인 cycleDic 에서 key를 문자열에서 숫자로 바꾼 부분이었다. 지난번 구현시 무엇때문에 수치형을 문자열로 변환하여 key로 만들었는지 모르겠다. -- 재선

멋진 코드

~cpp 
num = (num %2 and 3 * num + 1) or num / 2

~cpp 
i,j = map(int,raw_input().split())

둘다 무슨 의미인지 정확히 모르겠다. -- 재선

3N+1Problem