0

我试图制作一个利用匹配来创建斐波那契数列的递归函数。我让 Euler2 工作，但在 Euler2a 中，我试图让整个函数自包含，除了迭代约束 j。

Euler2a 必须如何改变才能提供序列？

任何指针都非常感谢。:)

Euler2的结果

val Euler2 : list:int list -> i:int -> j:int -> int list

val z : int list = [1; 2；3；5个；8个；13; 21; 34; 55; 89]

Euler2a的结果

val Euler2a : j:int -> (int list -> int -> int -> int list)

val z2 : (int list -> int -> int -> int list)

欧拉2

let rec Euler2 (list: int list) i j =
    match i with
    | 1 | 2         ->  Euler2 list (i+1) j
    | _ when (i<=j) ->  let newList = list @ [list.[list.Length - 1] + list.[list.Length - 2]]
                        Euler2 newList (i+1) j
    | _             ->  list

let z = Euler2 [1;2] 1 10

欧拉2

let rec Euler2a (j:int) =
    let i = 1
    let list = [1;2]
    let rec Euler2b (list: int list) i j =
        match i with
        | 1 | 2         ->  Euler2b list (i+1) j
        | _ when (i<=j) ->  let newList = list @ [list.[list.Length - 1] + list.[list.Length - 2]]
                            Euler2b newList (i+1) j
        | _             ->  list
    Euler2b

let z2 = Euler2a 10
4

2 回答 2

4

您的 Euler2a 返回值，该值Euler2b是一个接受列表和 2 个整数参数的函数。您需要通过将行从

Euler2b

至

Euler2b list i j

以便将参数提供给函数。然后一切正常。

于 2013-10-17T01:16:18.423 回答
4

除了从约翰的答案地址的Euler2b正文递归调用内部函数的格式的直接问题之外，与所采取的方法相关的问题不太明显。Euler2a

  • 您的实现使用F# 列表作为基本数据结构。虽然它允许解决Project Euler Problem 2，但它更像是一个数组，而不是惯用的 F# 列表。表达式list @ [list.[list.Length - 1] + list.[list.Length - 2]]在计算上非常昂贵，不仅来自索引器的使用list.[i]，而且来自 append 运算符@，它在每次迭代中完全丢弃当前列表并重新创建新的、更长的元素，从而对垃圾收集造成不必要的压力。一个惯用的 F# 使用 list 将其从左侧增长并在最后一步反转，如下所示：

    let euler2c len =
    let rec inner (list: int list) i len =
        match list with
        | l::p::tail when (i < len) -> inner ((l + p)::l::p::tail) (i+1) len
        | _  ->  List.rev list
    inner [2;1] 2 len

  • 拥有一定长度的斐波那契数列不便于解决原始问题，因为解决方案应基于最后一个元素的值，这可能需要额外的参数/条件。更惯用的方法是从F# 序列list切换到懒惰地表示任意长度的斐波那契序列。使用库函数Seq.unfold允许以下简洁的一个线性实现：

    let fibnums = Seq.unfold (fun(curr,next) -> Some(curr,(next,curr+next)))(1,2)

    现在fibnums具有seq<int>允许使用库函数和组合器惯用地操作的类型。特别是，使最后一个元素不超过 4000000 的序列可以表示为微不足道的fibs |> Seq.takeWhile ((>=) 4000000)。

于 2013-10-17T07:08:13.203 回答