파이썬_실전 프로젝트

프로젝트 오일러 14번문제 - Collatz 수열

1로 수렴하는 어떤 수열이 있는데, 백만까지의 수중에서, 가장 긴 수열을 가진 수를 찾는 문제입니다.

 

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

nn/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

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.

 

먼저 예시의 13으로 테스트 하면서, 함수를 만든후에, 백만까지 적용하기로 하죠.

def collatz(num):
    count=1
    while True:
        if num%2==0:
            num=num/2
        elif num==1:
            return count
        else:
            num=num*3+1
        count+=1

i=1
while i<14:
    print("loop :",i,end='')
    chain=collatz(i)
    print(" chain :",chain)
    i+=1
loop : 1 chain : 1
loop : 2 chain : 2
loop : 3 chain : 8
loop : 4 chain : 3
loop : 5 chain : 6
loop : 6 chain : 9
loop : 7 chain : 17
loop : 8 chain : 4
loop : 9 chain : 20
loop : 10 chain : 7
loop : 11 chain : 15
loop : 12 chain : 10
loop : 13 chain : 10

 

그다음 100개까지 늘려보고, 최대값도 선별해주겠습니다.

def collatz(num):
    count=1
    while True:
        if num%2==0:
            num=num/2
        elif num==1:
            return count
        else:
            num=num*3+1
        count+=1

i=1;max_chain=0;max_i=0
while i<100:
    print("loop :",i,end='')
    chain=collatz(i)
    print(" chain :",chain)
    if chain>max_chain:
        max_chain=chain
        max_i=i
        print("new max_chain :",max_chain,)
    i+=1
    
print("max_chain :", max_chain,"loop ",max_i)
loop : 1 chain : 1
new max_chain : 1
loop : 2 chain : 2
new max_chain : 2
loop : 3 chain : 8
new max_chain : 8
loop : 4 chain : 3
loop : 5 chain : 6
loop : 6 chain : 9
new max_chain : 9
loop : 7 chain : 17
new max_chain : 17
loop : 8 chain : 4
loop : 9 chain : 20
new max_chain : 20
loop : 10 chain : 7
loop : 11 chain : 15
loop : 12 chain : 10
loop : 13 chain : 10
loop : 14 chain : 18
...
...

 

다음으로, 1만개까지입니다. 여기서부터는 출력문이 많으면 시간이 많이 걸리니, 최대값이 갱신될때만 출력문을 찍어보도록 하죠.

def collatz(num):
    count=1
    while True:
        if num%2==0:
            num=num/2
        elif num==1:
            return count
        else:
            num=num*3+1
        count+=1

i=1;max_chain=0;max_i=0
while i<10000:
    chain=collatz(i)
    if chain>max_chain:
        max_chain=chain
        max_i=i
        print("loop :",i,"# of chain :",chain,"new max_chain :",max_chain,)
    i+=1

print("max_chain :", max_chain,"loop ",max_i)

 

마지막으로 1백만까지 입니다. 시간이 꽤걸리는듯 해서, 시간도 같이 측정했습니다.

import time
start_time = time.time()

def collatz(num):
    count=1
    while True:
        if num%2==0:
            num=num/2
        elif num==1:
            return count
        else:
            num=num*3+1
        count+=1

i=1;max_chain=0;max_i=0
while i<1000000:
    chain=collatz(i)
    if chain>max_chain:
        max_chain=chain
        max_i=i
        print("loop :",i,"# of chain :",chain,"new max_chain :",max_chain)
    i+=1
    
print("max_chain :", max_chain,"loop ",max_i)
print("calculation time:",time.time()-start_time)

 

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
노마드
현재 버전
선택 버전
graphittie 자세히 보기