2

我正在尝试实现一个递归函数，它接受一个浮点数并返回一个整数列表，表示浮点数的连分数表示（https://en.wikipedia.org/wiki/Continued_fraction）一般我想我理解算法是如何应该工作。它相当简单。我到目前为止是这样的：

let rec float2cfrac (x : float) : int list = 
    let q = int x
    let r = x - (float q)
    if r = 0.0 then
         []
    else 
         q :: (float2cfrac (1.0 / r ))

问题显然与基本情况有关。似乎 r 的值永远不会减少到 0.0，而是算法继续返回类似于 0.0 .....[number] 的值。我只是不确定如何进行比较。我到底应该怎么做。该函数所基于的算法说基本情况是 0，所以我自然将其解释为 0.0。我没有看到任何其他方式。另外，请注意这是一个任务，明确要求我递归地实现算法。有人对我有一些指导吗？将不胜感激

4

1 回答 1

2

似乎 r 的值永远不会减少到 0.0，而是算法继续返回类似于 0.0 .....[number] 的值。

这是浮点比较的经典问题。您需要使用一些epsilon容差值进行比较，因为r永远不会完全 0.0达到：

let epsilon = 0.0000000001
let rec float2cfrac (x : float) : int list =
  let q = int x
  let r = x - (float q)
  if r < epsilon then
    []
  else 
    q :: (float2cfrac (1.0 / r))

> float2cfrac 4.23
val it : int list = [4; 4; 2; 1]

有关更多信息，请参阅此 MSDN 文档。

您可以为此定义一个辅助函数：

let withinTolerance (x: float) (y: float) e =
  System.Math.Abs(x - y) < e

另请注意，您的原始解决方案不是尾递归的，因此它在递归时会消耗堆栈并且可能会溢出堆栈。您可以重构它，以便 afloat可以在unfold没有递归的情况下进行编辑：

let float2cfrac (x: float) =
  let q = int x
  let r = x - (float q)
  if withinTolerance r 0.0 epsilon then None
  else Some (q, (1.0 / r))

4.23 |> Seq.unfold float2cfrac // seq [4; 4; 2; 1]
于 2018-03-17T12:30:47.737 回答