프로젝트 오일러 26번 - 순환소수의 순환마디

1부터 1000까지 역수를 만든다음, 순환소수들의 순환마디가 가장 긴수를 찾는 문제입니다.

특별한 방법은 없고, 1000까지 루프를 만들고, 역수의 소수부분을 문자열로 바꿔서 함수로 넘겨주면,

함수는 그문자열 길이만큼 다시 루프문을 돌면서, 문자열의 slice 기능을 이용해서, 여러가지 크기로 잘라서, 뒷부분과 비교를 하겠습니다.

소수점 생성

value=1/7
print(value)

0.14285714285714285

그냥 계산하면 소수점 길이가 충분히 나오지 않습니다.

from decimal import *
getcontext().prec = 100   #소수점이하 100자리까지 설정.

print(Decimal(1)/Decimal(7)) # -> 이표현식 사용.
print(Decimal(1/7))   # 사용불가.

0.1428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571429
0.142857142857142849212692681248881854116916656494140625

위코드처럼 Decimal(1)/Decimal(7) 사용해줘야 합니다.

루프문 작성

일단 100까지 순환하면서, 함수를 호출하겠습니다.

from decimal import *

def get_cycle_string(string):
    return None

decimalSize=100
getcontext().prec = decimalSize

for d in range(1,100):
    string=str(Decimal(1)/Decimal(d))
    string=string[string.find(".")+1:]
    cycle = get_cycle_string(string)
    print(cycle)

함수

함수는 문자열을 받아서, 순환구간을 판단하고 문자열로 리턴하는 구조입니다.

from decimal import *

def get_cycle_string(string):
    length = len(string)
    for i,v in enumerate(string):
        end=int(string.find(v,i+1))
        while end != -1 and end < length*0.5:
            target = string[i:end]
            target_len = end-i
            test=string[end:end+target_len]
            if target == test and string.count(target)*target_len > length*0.9:
                return target
            else :
                end=int(string.find(v,end+1))

decimalSize=2000
getcontext().prec = decimalSize
max_length=0
for d in range(1,1000):
    string=str(Decimal(1)/Decimal(d))
    string=string[string.find(".")+1:]
    cycle = get_cycle_string(string)
    if not cycle == None and len(cycle)>max_length:
        max_length = len(cycle)
        print(d,max_length)

판단하는 방식은, 문자열을 다양한 크기로 자르고, 그다음 구간에도 같은패턴이 존재하는지, 존재한다면, 전체 문자열의 95% 이상을 대체할수 있는지를 판단해서, 순환마디라고 판단해줍니다.

구간을 잘라볼때, 모든 경우의 수를 다 검사하면, 시간이 많이 걸리기 때문에, 특정숫자가 반복되는 위치를 찾아서, 그 구간만큼만 검사합니다.

프로젝트 오일러 26번 - 순환소수의 순환마디

소수점 생성

루프문 작성

댓글