3n+1 문제
임의의 자연수 n에 대해 다음과 같은 조작을 반복합니다.
n이 짝수면 2로 나누고, n이 홀수면 3n+1을 구한다.
예를 들어, n=5로 시작하면, 5 → 16 → 8 → 4 → 2 → 1 이 됩니다.
어떤 자연수 n에 대해서도, 이 조작을 유한 번 시행하면 1이 될 것이라고 예상하는데, 7000 0000 0000보다 작은 모든 짝수에 대해 성립한다는 것이 밝혀져 있긴 하지만, 아직 아무도 증명하지 못했습니다.
유명한 헝가리 수학자 폴 에르되시(Paul Erd\”os)는, “우리의 수학은 아직 이 문제를 풀 준비가 되어 있지 않다.”라고 했습니다.
심심해서 이걸 파이썬 코딩을 해봤다.
알고리즘 트레이닝 북에 나온 문제다…39page 문제1 참고하시오.. (저작권 문제때문에 여기서 문제는 못올리겠당…^^;)
class firstProg:
#생성자
def __init__(self):
self.maxcount = 0
#n이 짝수 인지 홀수 인지 판별해서 약정된 계산 수행
def calc(self, val):
if val%2 == 0:
return self.evennum(val)
elif val%2 == 1:
return self.oddnum(val)
def evennum(self, val):
val = val/2
return val
def oddnum(self, val):
val = (val*3) +1
return val
def loopdef(self, start, end):
for i in range(start, end+1):
countcycle = 1
while 1:
i = self.calc(i)
countcycle += 1
if i == 1:
break
self.setmaxcount(countcycle)
def setmaxcount(self, count):
if count > self.maxcount:
self.maxcount = count
def getmaxcount(self):
return self.maxcount
if __name__==”__main__”:
#입력
i,j = raw_input().split()
#출력
first = firstProg()
first.loopdef(int(i),int(j))
print i, j, first.getmaxcount()