Project Euler Problem 2 in F #

Question

Я немного застрял на последнем этапе получения решения problem 2 на Project Euler. Это источник, который я получил до сих пор.

#light 
module pe2 (* Project Euler Problem 2 solution *) 

    open System 

    let Phi = 1.6180339887;; 

    let invPhi = 1.0/Phi;; 

    let rootOfFive = 2.236067977;; 

    let maxFib = 4000000.0; 

    let Fib n = 
    System.Math.Round((Phi**n - invPhi**n)/rootOfFive);; 

    let FibIndices = Seq.unfold(fun i -> Some(i, i+3.0)) 3.0;; 

    let FibNos = FibIndices |> Seq.map(fun index -> Fib(index));; 

    let setAllowedFibNos = FibNos |> Seq.filter(fun fn -> (fn <= maxFib));; 

// let answer = setAllowedFibNos |> Seq.fold (+) 0.0; 

Когда я раскомментирую последнюю строку, процесс никогда не заканчивается. Поэтому я надеялся, что кто-то может слегка подтолкнуть меня в правильном направлении. Я смотрел на setAllowedFibNos, и это выглядит правильно, но это также бесконечная последовательность, поэтому я вижу только первые три условия.

Кроме того, может ли кто-нибудь указать мне на правильный путь, чтобы связать различные последовательности вместе? Я пробовал что-то вроде этого:

let answer = Seq.unfold(fun i-> Some(i, i + 3.0)) 3.0 
|> Seq.map (fun index -> Fib(index)) 
|> Seq.filter(fun fn -> (fn <= maxFib)) 
|> Seq.fold (+) 0.0;; 

Но это не сработало. Поскольку вы, вероятно, можете догадаться, что я просто изучаю F #, поэтому, пожалуйста, ласково, и если этот вопрос задан и ответили ранее, пожалуйста, напишите ссылку на ответ, и я заберу это.

Answer 1

'setAllowedFibNos' действительно бесконечное вычисление seq; «fold» нуждается в всей последовательности, поэтому «фильтр» будет вечно искать другой номер < = maxFib.

Взгляните на TakeWhile:

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.Core/Microsoft.FSharp.Collections.Seq.html

Я думаю, что это то, что вы хотите вместо фильтра.

Также обратите внимание, что вы можете использовать «sqrt 5.0».

Answer 2

Я все еще пытаюсь привыкнуть к подходу Seq. Но вот мое решение без него.

 

#light 
let rec fib n = 
    match n with 
    |0|1 -> n 
    |_ -> fib(n-1) + fib(n-2) 

let maxFib = 4000000 
let phi = (1.0 + sqrt(5.0))/2.0 
let upperBound = 1 + int(log10((float(maxFib) - 0.5) * sqrt(5.0))/log10(phi)) 

[1..upperBound] |> List.filter (fun x-> x%3=0) |> List.map fib |> List.filter (fun x -> x%2 = 0) |> List.filter (fun x -> x List.sum |> printfn "%d" 
 

Answer 3

let rec Fib(n) = 
    if (n < 2) then 
     1 
    else 
     Fib(n-2) + Fib(n-1) 

Seq.initInfinite Fib 
|> Seq.takeWhile (fun a -> a <= 4000000) 
|> Seq.filter (fun a -> (a % 2) = 0) 
|> Seq.fold (+) 0 

Answer 4

Мое решение:

Seq.unfold (fun state -> 
    if (fst state + snd state > 4000000) then None 
    else Some(fst state + snd state, (snd state, fst state + snd state))) (0,1) 
|> Seq.filter (fun x -> x % 2 = 0) 
|> Seq.sum;;