斐波那契 OCAML 的 N 步代码

Question

所以我正在尝试为我的 class 编写一些代码，它将输出 n 步斐波那契数列中前 k 项的 int 列表。

所以对于那些不知道的人来说，n 步斐波那契数列是当您在它之前添加 n 个数字以获得下一个数字时，

so for n=1 it'd be 1,1,1,1,1,...
n=2, it'd be 1,1,2,3,5,...
n=3 it'd be 1,1,2,4,7...

我的方法是从一个基本案例开始，所以

let rec n_step n k= 

if k=1 then [1] else 

if n=1 then 1::nacci n k-1 else

但现在我被困在这里了。我知道我需要遍历并添加列表中的术语，但我不确定如何完成此操作。

我做了一个辅助函数sum

let rec sum lst =
  match lst with
  | [] ->  0
  | h::t -> h + sum t

我试图让它有选择地添加列表的最后 n 个数字以获得下一个值，但我也被卡住了

提前致谢！

Answer 1

这是作业，所以我只建议一些步骤，而不是完整的解决方案：

如果您来自命令式背景，请首先尝试命令式解决方案，例如打印结果的循环，而不是立即构建列表和绑定递归。您可以将所需状态存储在全局中，然后逐渐更改它以传递参数。
从 n=2 开始，使用元组而不是列表。首先这样做会容易得多，在使用列表之前手动扩展到 fixed n=3 和 fixed n=4。

应用这两条建议，第一步可能是：

let print_fib_2 () =
  let previous_ref = ref (1, 1) in
  for i = 0 to 10 do
    let (a, b) = !previous_ref in
    let next = a + b in
    previous_ref := (next, a);
    Printf.printf "%d\n" next
  done

我首先概括为使用将 n=2 更改为 n=3：(a, b) 和 (next, a) 这对会发生什么？列表是什么意思？

按照工作示例中的小步骤，您应该能够找到解决方案。

Answer 2

我已经使用许多辅助函数解决了这个问题。

所以我制作了一个求和函数，可以对列表中的值求和一个 gather 函数，它只会从整个列表中获取 n 个值

然后在我原来的函数中，我对 k 使用了模式匹配，如果 k=1，它会产生一个，否则它会递归。如果不是，我使用 helper

附加下一个值

斐波那契 OCAML 的 N 步代码

N-step code for fibonacci OCAML

algorithm

ocaml

fibonacci