3N+1 Problem/강희경

파이선 ¶

파이선으로 재귀호출을 한번 구현해보았으나, 엄청 느리다.

~cpp 
def TreeNPlusOne(aNumber):
    print aNumber,
    if aNumber == 1:
        return
    elif aNumber%2 == 0:
        aNumber /= 2
    else:
        aNumber = 3*aNumber+1
    TreeNPlusOne(aNumber)

[edit]

알고리즘 ¶

1. 22의 경우 22, 11, 34...이렇게 되는데 22의 싸이클 안에 11, 34등의 싸이클도 포함되니 최대값에서 그들을 배제하는 것이 가능하다.
2. 범위 안에 어떤수의 2의 배수가 있는 경우(또는 (x - 1)/3이 있는 경우) 1과 같은 이유로 그 수는 최대값에서 배제한다.

범위(Range)를 인위적으로 줄여야한다는 결론에 도달.

[edit]

소스 ¶

~cpp 
def TreeNPlusOne(aNumber, aMin, aMax, aBinaryMap):
    count = 1
    while(aNumber != 1):
        if(IsInRange(aMin, aMax, aNumber) and aBinaryMap[aNumber-aMin]):
            aBinaryMap[aNumber-aMin] = False
        if(aNumber%2 == 0):
            aNumber = aNumber/2
        else:
            aNumber = aNumber*3+1
        count = count + 1
    return count

def InputRange():
    min, max = input('최소, 최대: ')
    while IsCorrectInput(min, max) == False:
        min, max = input('최소, 최대: ')      
    return min, max

def MakeBinaryMap(aMin, aMax):
    rangeOfMap = aMax - aMin + 1
    binaryMap = range(rangeOfMap)
    for i  in range(rangeOfMap):
        binaryMap[i] = True
    return binaryMap

def FindMaxCycleLength(aMin, aMax, aBinaryMap):
    maxCycleLength = 0
    for i in range(aMin, aMax+1):
        if(aBinaryMap[i-aMin]):
            cycleLength = TreeNPlusOne(i, aMin, aMax, aBinaryMap)
            if(maxCycleLength < cycleLength):
               maxCycleLength = cycleLength
    return maxCycleLength

def OutputResult(aMin, aMax, aMaxCycleLength):
    print aMin, aMax, aMaxCycleLength

def IsInRange(aMin, aMax, aNumber):
    if(aMin <= aNumber and aMax >= aNumber):
        return True
    else:
        return False

def PreInspection(aMin, aMax, aBinaryMap):
    for i in range(aMin, aMax/2+1):
        tempI = i
        while(IsInRange(aMin, aMax, 2*tempI)):
            aBinaryMap[tempI-aMin] = False
            tempI = 2*tempI

def IsCorrectInput(aMin, aMax):
    if(aMin > 0 and aMax < 1000000 and aMin < aMax):
        return True
    else:
        print 'Not Accept'
        return False

if __name__ == '__main__':
    min, max = InputRange()
    binaryMap = MakeBinaryMap(min, max)
    PreInspection(min, max, binaryMap)
    OutputResult(min, max, FindMaxCycleLength(min, max, binaryMap))

3N+1Problem