오일러 프로젝트 26 번은 단위분수에서 가장 긴 순환마디를 갖게 만드는 분자의 값을 구하는 문제이다. 20번대 문제라 하기에는 많이 쉽다.
분자가 1인 분수를 단위분수라고 합니다.
분모가 2에서 10까지의 단위분수는 아래와 같습니다.
숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 “6”으로 0.166666…처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다. d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?
http://euler.synap.co.kr/prob_detail.php?id=26
접근
분모/분자 형태로 표기한 값을 소수로 표현하기 위해서는 실제로 분자를 분모로 나눠보면 된다. 소수점 이하의 나누기를 손으로 하는 경우, 자리수를 계속 내려가면서 나누는데, 앞자리의 나머지가 다음자리의 몫이되는 것이 반복된다. 순환마디가 나타나는 것은 특정 단계의 몫과 나머지가 반복되는 시점이다. 따라서 매 순간의 (몫, 나머지) 쌍을 기록하다가, 방금 나온 결과가 이전에 나온 적이 있는지, 그리고 그게 몇 번 전에 나왔는지를 알면 그게 바로 순환마디의 길이가 된다.
def test(d):
n = 1 ## 몫
paths: list[(int, int)] = []
while True:
result = divmod(n, d)
if result[1] is 0: ## 나눠져버렸...
return 0
if result in paths: ## 몫, 나머지가 동일했던 패턴찾기
return len(paths[paths.index(result):])
else:
paths.append(result)
n = result[1] * 10 ## 다음 나누기의 몫은 지금의 나머지임
xs = [(x, test(x)) for x in range(2, 1001)]
print(max(xs, key=lambda x: x[1])[0])보너스 : Swift 풀이
사실 로직이 간단해서 따로 쓰지 않으려고 했는데, 몇가지 노트할 만한 것이 있다.
- Swift의 튜플은 파이썬과 달리 배열/사전의 키가 될 수 없고, 그 자체로는
Equatble이 아니다. 따라서index(of:)를 쓸 수 없고,index(where:{ $0.0 == x.0 && $0.1 == x.1 })이런식으로 비교해줘야 한다.
typealias Result = (Int, Int)
func divmod(_ a: Int, _ b: Int) -> DivResult { return (a / b, a % b) }
func test(_ d: Int) -> Int {
var q = 1
var paths: [Result] = []
while true {
let res = divmod(q, d)
if let pos = (path.index{ $0.0 == res.0 && $0.1 == res.1 }) {
return paths.count - pos
} else {
paths.append(res)
}
q = res.1 * 10
}
}
let result = (2...1000).map{ ($0, test($0)) }
.reduce((0, 0)){ $0.1 > $1.1 ? $0 : $1}
print(result.0)그외
나누기 혹은 분수 계산과 관련된 문제가 오일러 프로젝트 내에 몇 개 있는데, 정말 헷갈림이 많이 유발된다. 코드는 간단해 보이지만, 중간중간에 여러 숫자들을 넣고 테스트해볼 것을 권장한다.