使用 OCaml 中的给定列表和运算符计算最大值

Question

使用给定的正整数列表和加法和乘法作为运算符，我想计算最大值。

因此，如果我的列表是 [2,3,4]，它将是：2 * 3 * 4 = 24。如果列表中至少有一个1，那就有点困难了。我通过测试几个示例发现要计算最高值，我必须将 1 添加到列表的最小值等等......直到列表中不再有 1 并计算所有整数的乘积。例如：[1,2,3,4] 会 return ( 2 + 1 ) * 3 * 4 = 36； [1,1,2,3,4] 会 return ( 1 + 1 ) * 2 * 3 * 4 = 48。

我的第一个问题是关于算法部分的：如何正确证明我的方法是正确的并且总是return最高值？

我的第二个问题是实施：

我在 OCaml 中编写了以下代码来对其进行编程：

(* Return 'list' with the first occurence of 'x' removed *)
let rec remove list x =
match list with
| [] -> []
| hd :: tl -> if hd = x then tl else hd :: remove tl x
;;

(* Return the maximum value which can be computed with the given list*)
let rec test_max list = match list with
  | [] -> 0
  | hd :: [] -> hd
  | hd :: tl ->
    (* If the list contains 1 : remove it from the list, then sort the list to get the min value and add 1 to it *)
    if List.mem 1 list then begin
      let list = List.sort (fun x y -> if (x < y) then 1 else 0) (remove list 1) in
      let test = (List.hd list) + 1 in
      test_max test::(List.tl list);
    end
    else
     List.fold_left ( * ) 1 list;;

并按照说明

let test = (List.hd list) + 1 in
          test_max test::(List.tl list);

在 test_max 我得到错误：

Error: This expression has type 'a list
       but an expression was expected of type int

嗯，我真的不明白 w为什么它在递归调用中期望一个 int 类型的表达式 ... ?

提前谢谢你:)

Answer 1

您的 OCaml 代码被解析为：

(test_max test)::(List.tl list)

你想要的是

test_max (test::(List.tl list))

除此之外，您的实施似乎是正确的。您应该使用 compare 作为 List.sort.

的参数

Answer 2

函数应用的优先级高于::。所以，你的代码 test_max test::(List.tl list) 确实应该是 test_max (test::List.tl list).

此外，您不应在此处使用 ;，因为它用于分隔单元指令。什么都不放就没事了

至于一些证明提示：

n + m > n * m
<=> ( n + m ) / (n * m) > 1
<=> 1/m + 1/n > 1

因为我们使用正整数，并且因为 / 在其第二个参数中递减。很容易看出这是真的当且仅当m or n = 1（当n and m = 2时可以达到平等）。

现在，我们如何使用这个 +1？

(n+1) * m > n * (m+1)
<=> n * m + m > n * m + n
<=> m > n

这是你的两个引理。我会让你搜索完整的证据。

使用 OCaml 中的给定列表和运算符计算最大值

Compute the highest value with a given list and operators in OCaml

algorithm

list

ocaml

proof