We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Memoization and DP
  4. Fibonacci
  5. Discussions

Fibonacci

  • lematero
     + 0 comments

    f# my first attempt hand with made cache no modulo property used: (a + b) % n = ((a % n) + (b % n)) % n.

    open System
open System.Collections.Generic

let rec fib =
    let dict = new Dictionary<_, _>()

    fun n ->
        match dict.TryGetValue(n) with
        | true, v -> v
        | false, _ ->
            let temp =
                if n = 0I then 0I
                elif n = 1I then 1I
                else fib (n - 1I) + fib (n - 2I)

            dict.Add(n, temp)
            temp

[ 1 .. Console.ReadLine() |> int ]
|> List.iter (fun _ ->
    Console.ReadLine()
    |> int
    |> bigint
    |> fib
    |> (fun x -> x % 100000007I)
    |> string
    |> Console.WriteLine)