1

更新：我不能使用任何 List.function 的东西。

我是 OCaml 的新手，我正在学习这门课程，我应该从值列表中计算出非递减值的列表。

因此，例如，我有一个列表 [1; 2；3；1个；2；7; 6]

因此，接受列表的函数 mono 返回以下内容：

# mono [1; 2; 3; 1; 2; 7; 6];;
- : int list = [1; 2; 3; 7]

我执行以下操作：

let rec calculateCheck value lst = (
    match lst with
     [] -> true
    | x :: xs -> (
        if (value < x) then
            false
        else
            calculateCheck value xs
    )
);;


let rec reverse_list lst = (

    match lst with
     [] -> []
    | x :: xs -> (
        reverse_list xs @ [x]
    )
);;

let shouldReverse = ref 1;; 

let cancelReverse somelist lst = (
    shouldReverse := 0;
    reverse_list lst
);;

let rec mono lst = (
    let somelist = ref lst in
        if (!shouldReverse = 1) then
            somelist := cancelReverse somelist lst
        else
            somelist := lst;

    match !somelist with
     [] -> []
    | x :: xs -> (
        if (calculateCheck x xs) then
            [x] @ mono xs
        else
            [] @ mono xs
    );
);;

问题？

  1. 由于 shouldReverse，这只适用于一次。
  2. 我无法反转价值；mono list应该返回非递减列表。

问题？

  1. 有什么简单的方法可以做到这一点？
  2. 具体如何获取列表的子集。例如对于 [1; 2；3；5个；6]，我想要[1; 2；3] 作为 5 的输出，以便我可以递归地解决这个问题。另一件事是，您可以将列表设为 [1; 2；3；5个；6；5]:: 所以对于第二个 5，输出应该是 [1; 2；3；5个；6]。

有任何想法吗？

谢谢

4

1 回答 1

3

解决此类问题的一个好方法是强迫自己以数学上正确的方式正式制定您正在寻找的内容。通过一些培训，这通常会给你一个接近你将要编写的最终程序的描述。

我们试图定义一个incr li包含 的严格递增子序列的函数li。正如 Jeffrey Scoffield 所问的那样，您可能正在寻找 最长的 此类子序列：这是一个经过充分研究的有趣且非平凡的算法问题，但鉴于您是初学者，我想您的老师要求的是更简单的东西。这是我对更简单规范的建议：您正在查找列表中大于它们之前的所有元素的所有元素。

产生易于转化为算法的数学定义的一个好方法是通过归纳P(n)推理：根据前任定义自然数上P(n-1)的属性，或者根据在一个小于的列表上的该属性定义给定列表上的属性。元素。考虑您要定义incr [x1; x2; x3; x4]. 你可以用 and 来表达它，也可以用and来incr [x1; x2; x3]表达。x4x1incr [x2; x3; x4]

  • incr [x1;x2;x3;x4]是incr[x1;x2;x3]，加上x4它是否大于列表中它之前的所有元素，或者等效地，它的最大元素incr[x1;x2;x3]

  • incr [x1;x2;x3;x4]是incr[x2;x3;x4]所有小于x1已删除的元素（它们不大于它们之前的所有元素），并x1添加

这两个精确的定义当然可以推广到任何长度的列表，并且它们给出了两种不同的写法incr。

(* `incr1` defines `incr [x1;x2;x3;x4]` from `incr [x1;x2;x3]`,
   keeping as intermediate values `subli` that corresponds to
   `incr [x1;x2;x3]` in reverse order, and `biggest` the biggest
   value encountered so far. *)
let incr1 li =
  let rec incr subli biggest = function
    | [] -> List.rev subli
    | h::t ->
      if h > biggest
      then incr (h::subli) h t
      else incr subli biggest t
  in
  match li with
    | [] -> []
    | h::t -> incr [h] h t

(* `incr2` defines `incr [x1;x2;x3;x4]` from `incr [x2;x3;x4]`; it
   needs no additional parameter as this is just a recursive call on
   the tail of the input list. *)
let rec incr2 = function
  | [] -> []
  | h::t ->
    (* to go from `incr [x2;x3;x4]` to `incr [x1;x2;x3;x4]`, one
       must remove all the elements of `incr [x2;x3;x4]` that are
       smaller than `x1`, then add `x1` to it *)
    let rec remove = function
      | [] -> []
      | h'::t ->
        if h >= h' then remove t
        else h'::t
    in h :: remove (incr2 t)
于 2013-02-10T09:16:30.143 回答