파이썬_실전 프로젝트

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

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.

 

저런 공식을 가진 수열이 있는데, 1백만 이하의 수중 가장 긴 수열을 가진 수를 찾으라고 합니다.

1백만 까지 루프문을 만들고, 모든 숫자에 대해서, 저 수열이 몇개인지를 조사하면 되겠네요.

 

먼저 루프문을 만듭니다.

while i<1000000:
    chain=collatz(i)
    if chain>max_chain:
        max_chain=chain
        max_i=i
    i+=1

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

함수를 무한루프문이나 재귀호출형식으로 만들고, 수열의 규칙에 따라 계산을 한후에, 카운트를 1씩 증가시키고, 마지막으로 숫자가 1이 되면, 그때의  count값을 리턴해줍니다.

 

댓글

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