时间戳

首页 > 解决方案 > 递归计算列表平均值

recursion - 递归计算列表平均值

问题描述

我在 OCaml 中有作业要做，一个问题是关于计算列表的平均值。我在一两年前就已经用另一种语言做过了，就像我第一次做的那样，我决定不仅将所有元素相加并除以长度。主要原因是担心浮点溢出。

所以我在维基百科上找到了我上次使用的公式：递归平均公式。

我在 OCaml 中这样编码：

let average = function
| []    -> raise Empty_list
| hd::l ->
    let rec aux average count = function
        | hd::l -> aux ((average*.(float (count-1))+.hd)/.(float (count))) (count+1) l
        | _     -> average
    in aux hd 1 l
;;

对我来说，这看起来像是 OCaml 中公式的精确转录。

但是它没有用，但是，在拿了一张纸，一支笔并考虑它之后，我设法通过更换线让它工作：

| hd::l -> aux ((average*.(float (count-1))+.hd)/.(float (count))) (count+1) l

和：

| hd::l -> aux ((平均*.(float ( count ))+.hd)/.(float ( count+1 ))) (count+1) l

它奏效了。

我告诉自己第二行在逻辑上是计算正确答案的好方法，但我一开始不明白哪里出了问题。我翻译了一个有偏见的公式吗？还是我在翻译时遗漏了什么？

在这一点上，我仍然觉得第一行是公式的转录，第二行是计算正确答案的方法。但我相信这里有一些我无法理解的东西。有人可以为我解释一下吗？

标签： recursionocamlaverage

解决方案

作为参考，这是一个不会以正确的时间复杂度溢出的函数版本：

let avg l =
  let mu_n' (n,mu_n) x =
    let n' = n + 1 in
    n', mu_n +. (x -. mu_n) /. float n' in
  snd (List.fold_left mu_n' (0,0.) l)

let x = avg [max_float; 1.; 2.; max_float;2.; 3.; max_float; 5.; 6.]
let relative_error = (x -. max_float /. 3.) /. (max_float /. 3.)

val relative_error : float = -1.66533453693773481e-16

推荐阅读