f# - F# 中更高效的递归 Tetranacci 函数
问题描述
我正在尝试尽可能高效地使用 F# 编写 tetranacci 函数,但我想出的第一个解决方案确实效率低下。你能帮我想出一个更好的吗?我如何能够在线性时间内实现这一点?
let rec tetra n =
match n with
| 0 -> 0
| 1 -> 1
| 2 -> 1
| 3 -> 2
| _ -> tetra (n - 1) + tetra (n - 2) + tetra (n - 3) + tetra (n - 4)
解决方案
您可以通过设计一个计算 4 元组下一次迭代的状态的函数来节省成本。然后序列生成器函数Seq.unfold
可用于构建包含每个状态四元组的第一个元素的序列,这是一个“惰性”操作——序列的元素仅在消耗时按需计算。
let tetranacci (a3, a2, a1, a0) = a2, a1, a0, a3 + a2 + a1 + a0
(0, 1, 1, 2)
|> Seq.unfold (fun (a3, _, _, _ as a30) -> Some(a3, tetranacci a30))
|> Seq.take 10
|> Seq.toList
// val it : int list = [0; 1; 1; 2; 4; 8; 15; 29; 56; 108]
请注意,标准的 Tetranacci 序列 ( OEIS A000078 ) 通常会在开始状态下生成(0, 0, 0, 1)
:
// val it : int list = [0; 0; 0; 1; 1; 2; 4; 8; 15; 29]
推荐阅读
- reactjs - 如何在地图内的返回内使用条件
- html - 医学研究人员试图制作一个网站来展示互动人物
- javascript - 如何仅在小屏幕上的特定页面上隐藏元素,而无需刷新 webapp?
- javascript - 带有wordpress的Ajax,400错误请求
- python - 如何编写解码器,然后可以用 pytest 进行测试?
- amazon-ec2 - google cloud sdk 安装在我的 EC2 实例中,我可以访问 gcloud。但是 bq 不可用,即使我在组件列表中看到它
- typo3 - TYPO3 10中的多扩展扩展一扩展
- html - org-mode html 导出中的文本字体大小
- nlp - 是否有任何具有多个答案的 NLP 问答数据集?
- c# - UIDatePicker 停止工作 Xamarin IOS14