콘텐츠로 건너뛰기
Home » 오일러 프로젝트 66 » 페이지 2

오일러 프로젝트 66

Swift 풀이

이 문제의 Swift 풀이에서 어려운 점이라면 역시, 큰 수 계산에 관한 것이다. 이전까지 큰수의 덧셈과 곱셈 그리고 큰수와 정수의 곱셈과 덧셈을 구현해서 썼는데, 이번에는 “최대값”을 찾아야 하기 때문에 큰 수의 대소 및 동등 비교를 추가로 구현해야 한다.
하지만 이 역시 우리가 십진수에서 대소 비교하는 것과 동일한 방식으로 구현해주면 된다.

  1. 자리수가 많으면 많은쪽이 크다.
  2. 자리수가 같으면 앞쪽부터 숫자(계수)가 큰쪽이 크다.

동등 비교 역시, 자리수가 같고, 모든 항의 계수가 같다라고 비교하면 된다. 또한 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)
}
페이지 1 2