Project Euler를 F#으로 푸는 작업은 계속 틈나는 대로 하고 있는데..
안그래도 구독자가 별로 없는 블로그에 계속 그것만 올리면..
구독자들에게 짜증을 줄까봐 자제하고 있습니다.ㅋ
아무튼 Neon군이 리플로 제안한 방식으로 구현해보았습니다.
일단 기존 방식은 무식하게 세자리 숫자의 곱을 모두 계산 하는 방식이었는데
새로운 방식은 세자리 숫자의 곱 중에서 큰 수 순서대로 숫자를 뽑습니다.
그리고, (123 * 312) 과 (312 * 123)은 같은 값이기 때문에 한번만 계산 합니다.
set [ (999*999, 999, 999) ]
|> Seq.unfold (fun pq ->
let head = pq.MaximumElement
let product, a, b = head
let newElements =
set [ ((a-1)*b, a-1, b); (a*(b-1), a, b-1) ]
|> Set.filter (fun (_, a, b) -> a <= b)
Some (product, ((pq.Remove head) + newElements)))
|> Seq.filter is_parlindrome
|> Seq.hd
|> printfn "Problem #4 = %d"
Priority Queue 구현에서 일반적으로 사용되는 Heap를 사용하는 것이 가장 좋아 보이지만...
F#에서 쓰기 쉬운 Set (Binary Tree) 기반으로 구현 하였습니다.
'내 생산물' 카테고리의 다른 글
| F#, Project Euler - Problem #4 (2) (0) | 2009/05/22 |
|---|---|
| F#, Project Euler - Problem #12 (0) | 2009/05/12 |
| F#, Project Euler - Problem #20 (0) | 2009/05/12 |
| F#, Project Euler - Problem #5 (0) | 2009/05/11 |
| F#, Project Euler - Problem #4 (2) | 2009/05/11 |
| F#, Project Euler - Problem #3 (0) | 2009/05/10 |
| F#, Project Euler - Problem #1 (2) | 2009/05/10 |
