Swift 풀이
이 문제의 Swift 풀이에서 어려운 점이라면 역시, 큰 수 계산에 관한 것이다. 이전까지 큰수의 덧셈과 곱셈 그리고 큰수와 정수의 곱셈과 덧셈을 구현해서 썼는데, 이번에는 “최대값”을 찾아야 하기 때문에 큰 수의 대소 및 동등 비교를 추가로 구현해야 한다.
하지만 이 역시 우리가 십진수에서 대소 비교하는 것과 동일한 방식으로 구현해주면 된다.
- 자리수가 많으면 많은쪽이 크다.
- 자리수가 같으면 앞쪽부터 숫자(계수)가 큰쪽이 크다.
동등 비교 역시, 자리수가 같고, 모든 항의 계수가 같다라고 비교하면 된다. 또한 BigNumber의 각 항(노드)들은 생성 원리에 의해서 작은 차수부터 생성되기 때문에 비교적 간단하게 구현할 수 있다.
extension BigNumber {
static func == (left: BigNumber, right: BigNumber) -> Bool {
if left.nodes.count != right.nodes.count { return false }
for (x, y) in zip(left.nodes, right.nodes) {
if x.value != y.value { return false }
}
return true
}
static func > (left: BigNumber, right: BigNumber) -> Bool {
if left.nodes.count != right.nodes.count { return left.nodes.count > right.nodes.count }
for i in stride(from: left.nodes.count - 1, through: 0, by: -1) {
if left.nodes[i].value > right.nodes[i].value { return true }
}
return false
}
}이 이후에는 이전 문제에서 만든 BigFraction 을 그대로 쓰면 된다.
자연수의 제곱근을 연분수로 표현하는 함수
파이썬과 대동소이한 구현.
func squaredInfo(of n: Int) -> [Int]? {
let m = Int(sqrt(Double(n)))
var (a, b, c) = (m, -m, 1)
var cache = Set<String>()
var result = [Int]()
func next(_ a1:Int, _ b1: Int, _ c1: Int) -> (Int, Int, Int)? {
let c2 = (n - b1 * b1) / c1
if c2 == 0 { return nil }
let a2 = (m - b1) / c2
let b2 = -b1 - (a2 * c2)
return (a2, b2, c2)
}
while case let s = "\(a),\(b),\(c)", !cache.contains(s) {
if let (x, y, z) = next(a, b, c) {
cache.insert(s)
result.append(a)
(a, b, c) = (x, y, z)
} else { return nil }
}
return result
}연분수 전개를 계산하는 함수
func calc(_ x: [Int], _ i: Int = 1) -> BigFraction {
var xs = x
let a = xs.removeFirst()
var i = i
if i == 0 { return BigFraction(a) }
var pos = (i - 1) % xs.count
var f = BigFraction(xs[pos])
while i > 1 {
pos = (pos > 0) ? pos - 1 : xs.count - 1
f = xs[pos] + f.reversed()
i -= 1
}
f = a + f.reversed()
return f
}역시 파이썬과 같은 방식으로 테스트 해볼 수 있다. 테스트는 각자가 해보고… 드디어 본 문제 풀이.
do {
var result: (BigNumber, Int) = (BigNumber(integer: 0), 0)
for d in 2...1000 {
guard let s = squaredInfo(of: d) else { continue }
var i = 1
while true {
let g = calc(s, i)
let (x, y) = (g.n, g.d)
if x*x == (y*y*d) + BigNumber(integer:1) {
if x > result.0 { result = (x, d) }
break
}
i += 1
}
}
print(result)
}