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 のため、これは 1 回しか機能しません。
  2. 値を逆にすることはできません。mono list非減少リストを返す必要があります。

質問？

  1. これを行う簡単な方法はありますか？
  2. 具体的には、リストのサブセットを取得する方法。たとえば、[1; 2; 3; 5; 6]、[1; が欲しい。2; 3] 5 の出力として、この問題を再帰的に解決できるようにします。もう 1 つは、リストを [1; として使用できることです。2; 3; 5; 6; 5]:: したがって、2 番目の 5 の出力は [1; 2; 3; 5; 6]。

何か案は？

ありがとう

4

1 に答える 1

3

この種の問題にアプローチする良い方法は、数学的に正しい方法で、探しているものを正式に定式化することです。ある程度のトレーニングを行えば、通常は、作成する最終的なプログラムに近い記述が得られます。

incr liの厳密に増加するサブシーケンスを含む関数を定義しようとしていますli。Jeffrey Scoffield が尋ねたように、あなたはそのような最長のサブシーケンスを探しているかもしれません : これは興味深く、自明ではないアルゴリズムの問​​題であり、十分に研究されていますが、あなたが初心者であることを考えると、先生はもっと単純なものを求めていると思います。ここに、より単純な仕様の提案があります。リスト内でそれらの前にあるすべての要素よりも大きいすべての要素を探しています。

アルゴリズムに変換しやすい数学的定義を生成する良い方法は、帰納法P(n)による推論です:前任者に関して自然数のプロパティをP(n-1)定義するか、1 少ないリスト上のこのプロパティに関して特定のリストのプロパティを定義します。エレメント。を定義したいと考えてくださいincr [x1; x2; x3; x4]。incr [x1; x2; x3]とx4、またはx1とのいずれかで表現できますincr [x2; x3; x4]。

  • incr [x1;x2;x3;x4]リスト内のそれより前のすべての要素よりも大きい場合、または同等に、の最大の要素でincr[x1;x2;x3]あるx4incr[x1;x2;x3]

  • incr [x1;x2;x3;x4]incr[x2;x3;x4]より小さいすべての要素がx1削除され (それらの前のすべての要素よりも大きくない)、x1追加された場所です。

もちろん、これら 2 つの正確な定義は任意の長さのリストに一般化でき、2 つの異なる書き方を提供します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 に答える