Last active
December 20, 2015 11:39
-
-
Save locatw/a86b4a6f138b3534ef4b to your computer and use it in GitHub Desktop.
マヨイドーロ問題の解答
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| open System | |
| open System.Collections.Generic | |
| open System.Numerics | |
| // マヨイドーロ問題を解く。 | |
| // http://www.hyuki.com/codeiq/#c19 | |
| // | |
| // Pが大きな数になるのでBigIntegerを使う。 | |
| [<EntryPoint>] | |
| let main _ = | |
| // n番目のフィボナッチ数を格納する。 | |
| let dic = new Dictionary<BigInteger, BigInteger>() | |
| let bigTwo = new BigInteger(2) | |
| // n番目のフィボナッチ数を計算する。 | |
| // 高速化のためメモ化を使って計算済みのfib(n)については覚えておく。 | |
| // ただfib(0) = 1, fib(1) = 2, fib(2) = 3,...になるので | |
| // 一般的なフィボナッチ数の定義と違うかもしれない。 | |
| let rec fib n = | |
| match n with | |
| | _ when n < bigTwo -> n + BigInteger.One | |
| | _ -> | |
| match dic.TryGetValue(n) with | |
| | (true, r) -> r | |
| | _ -> | |
| let result = (fib (n - BigInteger.One)) + (fib (n - bigTwo)) | |
| dic.Add(n, result) | |
| result | |
| // 上限NのときのPを計算する。 | |
| // N = 4までを手で列挙して、 | |
| // Nが偶数 => P(n)はP(n - 1)と等しい | |
| // Nが奇数 => P(n)はP(n - 1) + fib(n) | |
| // という法則なんじゃないかと思って実装。 | |
| let rec calcP n = | |
| match n with | |
| | x when x = BigInteger.Zero -> BigInteger.Zero | |
| | _ when n % bigTwo = BigInteger.Zero -> calcP (n - BigInteger.One) | |
| | _ -> (calcP (n - BigInteger.One)) + (fib n) | |
| seq { | |
| while true do | |
| match Int32.TryParse(Console.ReadLine()) with | |
| | (true, x) -> yield Some(calcP (new BigInteger(x))) | |
| | _ -> yield None | |
| } | |
| |> Seq.takeWhile Option.isSome | |
| |> Seq.iter (fun x -> Console.WriteLine(x.Value)) | |
| 0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment