在F中生成斐波那契數列＃

Question

我剛剛開始學習使用VS2010的F＃，下面是我第一次嘗試生成斐波那契數列。我正在試圖做的是建立所有號碼的列表小於400

let fabList = 
    let l = [1;2;] 
    let mutable a = 1 
    let mutable b = 2 
    while l.Tail < 400 do 
     let c = a + b 
     l.Add(c) 
     let a = b 
     let b = c 

我的第一個問題是，在最後的聲明，我收到一條錯誤消息「不完整的結構構造時或之前這一點在表達「在最後一行。我不明白我在這裏做錯了什麼。

儘管這似乎是一種以相當有效的方式（從C++/C＃程序員）建立列表的明顯方式，但從我對f＃知之甚少的情況來看，這似乎並不認爲是正確的方式做這個程序。我在這種感覺中糾正了嗎？

Answer 1

首先，你使用let，如果它是變異變量的語句，但事實並非如此。在F＃中，let用於聲明一個新值（可以隱藏任何以前的同名數值）。如果你想使用突變編寫代碼，那麼你需要使用類似：

let c = a + b // declare new local value 
l.Add(c) 
a <- b // mutate value marked as 'mutable' 
b <- c // .. mutate the second value 

與您的代碼的第二個問題是，你試圖通過添加元素，它發生變異F＃列表 - F＃列表是不可改變，所以一旦你創建它們，你就不能修改它們（特別是，沒有Add成員！）。如果你想寫使用突變這一點，你可以寫：

let fabList = 
    // Create a mutable list, so that we can add elements 
    // (this corresponds to standard .NET 'List<T>' type) 
    let l = new ResizeArray<_>([1;2]) 
    let mutable a = 1 
    let mutable b = 2 
    while l.[l.Count - 1] < 400 do 
    let c = a + b 
    l.Add(c) // Add element to the mutable list 
    a <- b 
    b <- c 
    l |> List.ofSeq // Convert any collection type to standard F# list 

但是，正如其他人已經指出，以這種方式編寫代碼是不地道的F＃的解決方案。在F＃中，您將使用不可變列表和遞歸來代替循環（例如while）。例如像這樣：

// Recursive function that implements the looping 
// (it takes previous two elements, a and b) 
let rec fibsRec a b = 
    if a + b < 400 then 
    // The current element 
    let current = a + b 
    // Calculate all remaining elements recursively 
    // using 'b' as 'a' and 'current' as 'b' (in the next iteration) 
    let rest = fibsRec b current 
    // Return the remaining elements with 'current' appended to the 
    // front of the resulting list (this constructs new list, 
    // so there is no mutation here!) 
    current :: rest 
    else 
    [] // generated all elements - return empty list once we're done 

// generate list with 1, 2 and all other larger fibonaccis 
let fibs = 1::2::(fibsRec 1 2) 

Answer 2

下面是F＃的好文章。淨大師斯科特Hanselman在上產生Fibonacci序列

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

http://www.hanselman.com/blog/TheWeeklySourceCode13FibonacciEdition.aspx

它還與其他語言的比較作爲參考

Answer 3

是的，可變的變量和while循環通常是一個很好的信號，表明你的代碼不是很有用。斐波那契數列也不是從1,2開始的，它取決於你問誰，從0,1或1,1開始。

以下是我會做：

所有的

let rec fabListHelper (a:int,b:int,n:int) = 
    if a+b < n then 
    a+b :: fabListHelper (b, a+b, n) 
    else 
    [];; 

let fabList (n:int) = 0 :: 1 :: fabListHelper (0,1, n);; 

(*> fabList 400;; 
val it : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377]*) 

Answer 4

其他職位告訴你如何使用遞歸函數編寫while循環。這是另一種方式在F＃中使用Seq庫：

// generate an infinite Fibonacci sequence 
let fibSeq = Seq.unfold (fun (a,b) -> Some(a+b, (b, a+b))) (0,1) 
// take the first few numbers in the sequence and convert the sequence to a list 
let fibList = fibSeq |> Seq.takeWhile (fun x -> x<=400) |> Seq.toList 

的解釋，請在F# for Project Euler Problems，其中第50個歐拉問題都解決了REF solution 2。我想你會對這些解決方案感興趣。

Answer 5

這是一個使用序列表達式的無限尾遞歸解決方案。這是非常高效的，在幾秒鐘內就可以生成第10萬學期。 「yield」運算符就像C＃的「yield return」和「yield！」一樣。操作符可能會被視爲「yield all」，在C＃中，您必須執行「foreach item ... yield return item」。

https://stackoverflow.com/questions/2296664/code-chess-fibonacci-sequence/2892670#2892670

let fibseq =  
    let rec fibseq n1 n2 = 
     seq { let n0 = n1 + n2 
       yield n0 
       yield! fibseq n0 n1 } 
    seq { yield 1I ; yield 1I ; yield! (fibseq 1I 1I) } 

let fibTake n = fibseq |> Seq.take n //the first n Fibonacci numbers 
let fib n = fibseq |> Seq.nth (n-1) //the nth Fibonacci number 

這種方法類似於在C＃以下（其利用了同時（真）循環，而不是遞歸）：

Finding Fibonacci sequence in C#. [Project Euler Exercise]

Answer 6

斯科特漢塞爾爾曼的很好的解決方案不報告fibonacci序列開頭的0。

所以這裏是他的解決方案的一個小的改變，也報告0. 我用一個從0到10的小列表來顯示序列的前11個項目。

let nums=[0..10] 
let rec fib n = if n < 1 then 0 else if n < 2 then 1 else fib (n-2) + fib(n-1) 
let finres = List.map fib nums 
printfn "%A" finres 

我是新的和無能的關於f＃，仍然不完全理解它的需要。但發現這是一個有趣的測試。

只是爲了好玩：如果找到一個計算第n個斐波納契數的Binet公式。 不幸的是，需要一些浮點功能，以獲得整數結果返回到底： [比奈的斐波納契式] [1]

http://i.stack.imgur.com/nMkxf.png

let fib2 n = (1.0/sqrt(5.0)) * ((((1.0 + sqrt(5.0)) /2.0)**n) - (((1.0 - sqrt(5.0)) /2.0)**n)) 
let fib2res = fib2 10.0 
System.Console.WriteLine(fib2res) 
let strLine = System.Console.ReadLine() 

一個快速和骯髒翻譯到f＃將如下如上所示。我相信其他人可以在風格和效率方面改善這一點。該示例計算第10個數字。其結果將是55

Answer 7

let rec fibSeq p0 p1 = seq { 
    yield p0 
    yield! fibSeq p1 (p0+p1) 
} 

Answer 8

還有一個codata'ish方式：

let rec fib = seq { 
    yield! seq {0..1} 
    yield! Seq.map (fun(a,b)->a+b) <| Seq.zip fib (Seq.skip 1 fib) 
} 
let a = fib |> Seq.take 10 |> Seq.toList 

Answer 9

一個一個數組：

let fibonacci n = [|1..n|] |> Array.fold (fun (a,b) _ -> b, a + b) (0,1) |> fst 

Answer 10

此功能 「謊」 將返回斐波那契名單不大於500的數字

let rec fib a b = 
    let current = a + b 
    match current with 
    | _ when current >= 500 -> [] 
    | _ -> current :: fib b current 

let testFib = fib 1 2;;