4

人の名前を含む 3 つのリストがあります。

3 つのリストはすべてアルファベット順に並べ替えられています。

ここで、3 つのリストすべてに表示される名前を少なくとも 1 つ見つける必要があります。

私が考えているアルゴリズムは次のようなものです。

3 つのリストから 3 つの表が出ます。

3 つの頭が互いに等しくない場合は、最大 1 つを保持し、頭を削除したばかりのリストから 2 つの新しい頭を取得します。

最初に説明したような要素が見つかるまで、上記の手順を続けます。

このアルゴリズムは正しいですか？

問題は、関数を記述するために ocaml を使用する方法がわからないことです。

4

2 に答える 2

7

これはあなたのアルゴリズムを使って2つのソートされたリストの交差を行うOCaml関数です（これは確かにこの問題を解決するための良い方法です）。

let rec intersect l1 l2 = match l1, l2 with
| [], _ | _, [] -> []
| h1 :: t1, h2 :: t2 ->
  if h1 < h2 then intersect t1 l2
  else if h1 = h2 then h1 :: (intersect t1 t2)
  else intersect l1 t2
于 2013-01-17T18:08:09.307 に答える
3

Thomash のアルゴリズムは を 2 回呼び出しintersectて中間リストを作成するので、効率的ではありません。

あなたのアルゴリズムは本質的に正しいです。余分なビットは、2 つの頭が最大に等しい場合があり、残りの頭だけをドロップする必要があることです。

OCaml で書かれた改訂されたアルゴリズムは次のとおりです。

let rec intersect xs ys zs =
    match xs, ys, zs with
    | [], _, _ | _, [], _ | _, _, [] -> None
    | x::xs', y::ys', z::zs' -> 
       if x = y && y = z then Some x
       else 
           let m = max x (max y z) in
           if x = m && y = m then intersect xs ys zs'
           else if x = m && z = m then intersect xs ys' zs
           else if y = m && z = m then intersect xs' ys zs
           else if x = m then intersect xs ys' zs'
           else if y = m then intersect xs' ys zs'
           else intersect xs' ys' zs
于 2013-01-17T18:45:47.453 に答える