-1 
int choose_pivot(int lo, int hi){
   int mid = ((hi-lo)/2)+1;
   if((arr[hi]<arr[lo])^(arr[hi]<arr[mid])){
      return hi;
   }
   else if((arr[lo]<arr[hi])^(arr[lo]<arr[mid])){
      return lo;
   }
   else{
      return mid;
   }
}

この関数は、次のようにピボットを選択する必要があります。指定された配列の最初、中間、および最後の要素を検討してください。(配列の長さが奇数の場合、「中間」要素が何であるかを明確にする必要があります。長さが 2k の偶数の配列の場合、k 番目の要素を「中間」要素として使用します。これらの 3 つの要素のどれが中央値であるかを識別します。その価値。

この関数が意図したとおりに機能しない可能性があるという問題はありますか? 関数が望ましい結果をもたらさないケースを見逃していますか?

4

3 に答える 3

1

致命的なエラーと考えられることが 1 つあります。それは、前提条件に関するドキュメントがないことです。lo == hi特に、リーガルかどうかでそれを呼んでいます。(正当な場合、コードは未定義の動作をします。) そして、何loをhi 表し、何を表すのでしょうか? 通常の C++ 規則の下では、非常にうまく機能すると思いますloが、包括的かつhi排他的です。しかし、繰り返しになりますが、コードの正確性を判断する必要があるかどうかを知ることが重要であるという事実にもかかわらず、あなたは私たちに教えてくれません。（あなたがそうしているという事実はarr[hi]、両端を包括的にするというやや変わった慣習を採用したと私に思わせます。）

そのような情報がなければ、文体的なコメントをする以外に何もできません (たとえば、結果を比較するのではなく使用する!=、ではなくと使用するなど)。^return?:if ... else if ... else

于 2013-02-06T10:48:05.490 に答える
1

coursera.org からタスクを解決しようとしている場合は、使用する必要があります

int mid = ((hi-lo)/2);
于 2013-02-06T10:37:06.307 に答える
0

  1. ブール値の結果を不等式で比較する!=代わりに、おそらく使用する必要があります。^

  2. テキストの説明に基づいて、arr[hi]代わりにhi(および , についても同様) をmid返す必要がありますlo。

于 2013-02-06T10:33:01.883 に答える