어떤 특수한 규칙으로 1로 수렴하는 수열이 있는데, 백만까지의 수를 대입했을때, 수열의 길이가 가장 긴 수를 찾는 문제입니다.
Longest Collatz sequence
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
함수정의
collatz 함수의 정의입니다.
def collatz(num):
if num == 1: return
elif num%2==0:
return num/2
else:
return num*3+1
collatz(13)
40
수열생성
연속으로 생성되는 수열입니다.
def collatz(num):
print(num)
while not num==1:
if num%2==0:
num=num/2
else:
num=num*3+1
print(num)
return
collatz(13)
def collatz(num):
print(num)
if num == 1: return
elif num%2==0:
collatz(num/2)
else:
collatz(num*3+1)
collatz(13)
수열 COUNT
이제 수열길이를 count해서 count값만 리턴시켜주겠습니다. 프린트문 대신 count를 계산해주면 됩니다.
def collatz(num):
count=1
while not num==1:
if num%2==0:
num=num/2
else:
num=num*3+1
count+=1
return count
collatz(13)
재귀호출의 경우에 count를 계산하려면, 매개변수로 넘겨주면서 누적을 하던지, 아니면 리턴받는 시점에 누적을 할수 있습니다. 아래코드의 경우에는 리턴받는 시점에 1을 증가시키고 다시 리턴하는 방식으로 최종 10이라는 결과가 나오게 하였습니다.
def collatz(num):
if num == 1: return 1
elif num%2==0:
return collatz(num/2) +1
else:
return collatz(num*3+1) +1
collatz(13)
10
메인 루프
이제 메인 루프문을 만들어서 문제에 적용시켜보기로 하죠.
def collatz(num):
count=1
while not num==1:
if num%2==0:
num=num/2
else:
num=num*3+1
count+=1
return count
i=1;maxValue=0
while i<100:
value = collatz(i)
if value>maxValue :
maxValue = value
print(i,maxValue)
i+=1
1 1 2 2 3 8 6 9 7 17 9 20 18 21 25 24 27 112 54 113 73 116 97 119
100정도만 주고, 값을 확인한 다음에,
이상없으면 루프를 100만까지 늘려줍니다. 속도가 느리면 프린트문은 제거하고, 시간도 체크해 주면 좋겠네요.
import time
start_time = time.time()
def collatz(num):
count=1
while not num==1:
if num%2==0:
num=num/2
else:
num=num*3+1
count+=1
return count
i=1;maxValue=0
while i<1000000:
value = collatz(i)
if value>maxValue :
maxValue = value
i+=1
print(maxValue)
print("calculation time:",time.time()-start_time)
아톰cpu 이기도 하지만,, 속도가 많이 느립니다. 최신컴퓨터는 20-30초 정도면 될라나요,,
아래 재귀호출형식은 시간이 더많이 걸립니다. 함수호출하는 과정이 많아서 그런것 같네요.
import time
start_time = time.time()
def collatz(num):
if num == 1: return 1
elif num%2==0:
return collatz(num/2) +1
else:
return collatz(num*3+1) +1
i=1;maxValue=0
while i<1000000:
value = collatz(i)
if value>maxValue :
maxValue = value
i+=1
print(maxValue)
print("calculation time:",time.time()-start_time)
525 calculation time: 226.32076573371887
속도개선
2-3분 정도야 기다릴수 있다쳐도, 문제는 이런식으로는 규모가 더 커질경우 계산이 불가능합니다.
위 코드가 느린 이유는 루프마다 중복된 계산을 하기 때문입니다. 예를 들면 메인루프값에서 13을 주게 되면, 예제에 나온대로 13부터 시작해서 아래와 같은 수열이 생성되고, count값은 10이 반환됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
메인루프값이 26일때는
26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
앞에 26만 다르고, 나머지부분은 똑같습니다. 그래서 26다음부터는 저장된 루프(13)의 값 10을 불러와서 11을 결과로 출력하면 되겠죠.
이렇게 중복된 계산값을 메모리에 저장하고, 시간을 절약하는 방버을 다이나믹 프로그래밍(Dynamic Programming)이라고 합니다. 컴퓨터 알고리즘중의 하나입니다.
이제 위의 설명을 코드로 만들면, 루프(13)의 값 10 은 cache{13:10} 라는 딕셔너리 타입 변수에 저장되고, 불러올때는 cache[13] 이라고 불러냅니다. cache 변수는 모든결과값을 저장하기 때문에, 계산이 진행될수록 점점 커집니다.
{1: 1, 2: 2, 3: 8, 4: 3, 5: 6, 6: 9, 7: 17, 8: 4, 9: 20, 10: 7, 11: 15, 12: 10, 13: 10,,,,}
import time
start_time = time.time()
def collatz(num):
count=1
while num != 1:
if (num) in cache : # 수열만드는동안, 저장된값이 있는지 확인.
count += cache[num]-1 # 있으면, 저장된 값으로 대체.
num = 1
else :
if num%2 == 0:
num=num/2
else:
num=num*3+1
count+=1
return count
cache={} # 값을 저장할 변수. Dictionary 타입.
i=1;maxValue=0
while i < 1000000:
value = collatz(i)
if value > maxValue :
maxValue = value
cache[i] = value # 변수에 결과값 저장.
i+=1
print(maxValue)
print("calculation time:", time.time()-start_time)
525 calculation time: 14.966171503067017
재귀호출문에도 똑같이 적용할수 있습니다. 코드는 일반루프문보다 좀더 간결한데, 시간은 살짝 더 걸립니다만, 처음에 비해서는 차이가 별로 크지 않습니다.
import time
start_time = time.time()
def collatz(num):
if num == 1:
return 1
elif (num) in cache :
return cache[num]
elif num%2==0:
return collatz(num/2) +1
else:
return collatz(num*3+1) +1
cache={}
i=1;maxValue=0
while i < 1000000:
value = collatz(i)
if value > maxValue :
maxValue = value
cache[i] = value
i+=1
print(maxValue)
print("calculation time:", time.time()-start_time)
