1

私は compsci の学生で、Analysis & Design II のクラスで次の問題を受けました。

順序付けられていないセットの中央値は、同点がないと仮定して、中央値よりも少ない要素の数が、より多い要素の数の 1 つの範囲内にあるような要素です。

(a) 3 つの異なる値 a、b、c の中央値を見つけるアルゴリズムを書きます。

(b) アルゴリズムが平均的なケースと最悪のケースで行う比較の回数を決定します。

私が検索して学んだことから、これは、ソートされていない配列の k 番目の要素を見つけること、または中央値の中央値を見つけることと呼ばれているようです。

しかし、私たちはまだクイックソートを学んでいません。とはいえ、この問題で提示されている定義を完全に理解しているとは言えません。また、3つの異なる値a、b、cの中央値を見つけることは、サイズ3のセットの中央値を見つけることを意味しますか?

私は必ずしも答えを探しているわけではありません。簡単な説明や説明だけです。ありがとう。

試み #1

(a) templatetypedef のアドバイスに従って、これを解決するための単純なアルゴリズムを考え出しました。

medianOf(int a, int b, int c)
    if a < b
        if a > c
            return a
    else //a > b
        if a < c
            return a    

    if b < c
        if b > a
            return b
    else //b > c
        if b < a
            return b

    if c < a
        if c > b
            return c
    else //c > a
        if c < b
            return c

非常にナイーブで醜いことは承知していますが、より良い解決策を思いつくことができず、すでに時間がかかりすぎています。

(b) c < a < b で比較が 2 回の場合が最良のケースで、比較が 9 回で a < c < b の場合が最悪のケースのようです。では、平均は (2+9)/2 で、5 回または 6 回の比較になりますか?

それとも私は今ナイーブですか？

試み #2

(a) では、thang のアドバイスに従って、比較の数を 3 に最小限に抑えるために一生懸命努力しました。数学的に言えば、あなたの言いたいことは理解できます。残りの州をチェックa<b, b<c, a<cして差し引くだけで十分ですが、コード化する方法が見つかりませんでした...これが私の最善の試みです:

medianOf(int a, int b, int c)
    if a < b                                  1
        if c < a                              1
            return a    //c < a < b
        else  // a < b && a < c
            if b < c                          1
                return b    //a < b < c
            else
                return c    //a < c < b    

    else    //a > b
        if c > a                              1
            return a    //c > a > b
        else //a > b && a > c
            if b > c                          1
                return b    //a > b > c
            else                
                return c    //a > c > b

これよりもうまくやる方法がわかりません：

(b) 最良のケース: 1 回の比較。平均的なケース: 5/2 = 2 ～ 3 回の比較。最悪の場合: 5 回の比較。

もっといい？

最終的解決

おかげさまで、苦労してようやく手に入れることができました。私の最後のアルゴリズムは正しいのですが、カウントが間違っていました。

(b) 最良のケース: 2 つの比較。平均的なケース: 2 つの比較。最悪の場合: 3 回の比較。

4

2 に答える 2

4

幸いなことに、あなたはこれを考えすぎていると思います。:-) このように考えてみてください。この関数を実装できますか?

 int medianOf(int a, int b, int c) {
      ...
 }

任意のセットの中央値を見つけることについて心配する必要はありません。3 つの入力の中央値を見つけるだけです。

それが終わったら、行った比較を見て、最良の場合、最悪の場合、平均的な比較の数について考えてください。コードはかなり短くする必要があるため、行っている比較の数を直接数えることができます。

あなたが考えている中央値の手法は、任意の数の要素があり、それらすべての中央値を取得したい、より一般的なケースのためのものです。それは間違いなくこれよりも複雑ですが、それはあなたが求められていることではないようです.

お役に立てれば！

于 2015-02-18T20:56:33.433 に答える
0

ヒント：

a <= b かつ b <= c の場合、b は中央値です。

a <= b かつ b > c かつ c >=a の場合、c は中央値です。

a<=b かつ b > c かつ c < a の場合、a は中央値です。

a >= b かつ b >= c の場合、b は中央値です。

a >= b かつ b < c かつ a >= c の場合、c は中央値です。

a >=b かつ b < c かつ a < c の場合、a は中央値です。

ネストされた if/else ステートメントでこれをコーディングして、回答を返す前に 2 つまたは 3 つの比較を実行することができます。唯一の問題は、比較回数の最悪のケース、最良のケース、および平均的なケースです。平均的なケースでは、おそらく 3 つの数値すべてが異なる (ただし順序はランダムである) と想定する必要があります。そうでない場合、「等しい」ケースでは、発生頻度に応じて比較の平均回数が変わる可能性があります。

于 2015-02-19T00:59:23.510 に答える