2

私が遭遇した一見単純なアルゴリズムの質問。私は3回以下の操作でそれをやってのけようとしていますが、数学で解決できると合理的に確信していますが、理解できません(質問のソースには回答がありませんでした)。

編集：

(a[0] == a[1] + a[0] == a[2] + a[1] == a[2]) == 1

と当初は思っていたのですが、少ない操作でできるかどうか見てみたいです(1比較は操作です)。

4

4 に答える 4

7

3 つの数値がa、bおよびであると仮定するとc、

(b == c) ? (a != c) : (a == b || a == c)
  • (a, b, c) = (1, 1, 1) の場合、b == c(true) を呼び出し、次にa != c(false) を呼び出して完了します。
  • (a, b, c) = (1, 1, 2) の場合、b == c(false) を呼び出し、次にa == b(true) を呼び出して完了します。
  • b == c(a, b, c) = (1, 2, 1) の場合、(false) 、a == b(false)、 (true)を呼び出しa == cて完了です。
  • (a, b, c) = (2, 1, 1) の場合、(true) を呼び出し、b == c次にa != c(true) を呼び出して完了します。
  • (a, b, c) = (1, 2, 3) の場合、(false) を呼び出しb == c、次にa == b(false) とa == c(false) を呼び出して完了します。

そのため、最大で 3 つの比較が実行されます。

andにも 2 つの条件分岐点があります?:が||、OP ではカウントされません。

于 2012-10-22T18:33:25.670 に答える
3

あなたが「操作」と見なすものに応じて...

以下は、配列から 3 つの比較のみを使用します。== 1ただし、正確に 1 つの一致があることを確認するための 4 番目の比較があります。大量の分岐を使用して条件付きで比較の一部を排除できると思いますが、これが最適化である場合、分岐によってパフォーマンスが低下する可能性があります。

正確に 3 つの結果があります。

  • どの値も同じにはなりません (合計はゼロです)
  • 2つは同じになります（合計は1です）
  • 3 つすべて同じ (合計は 3)

if (((array[0] == array[1]) +
     (array[1] == array[2]) +
     (array[0] == array[2])) == 1)
{
    // stuff
}

これは比較と分岐を交換して、最大 3 つの比較と 2 つだけを必要とするルートを実現します。

if (array[0] == array[1]) // if these are equal
    return !(array[1] == array[2]); // and these are not equal, return true
else
    return (array[0] == array[2]) || (array[1] == array[2]); // otherwise, if these are equal, we already know the others are not equal because we already tested them so return true
于 2012-10-22T18:23:03.347 に答える
2

次の式を書くことができます。

((b == a) | (b == c)) ^ (a == c)

これはコストが一定で、常に 3 つの比較と 2 つの論理演算を実行します。分岐がないため、プロセッサで簡単に実行できるはずです。

アーキテクチャによっては、

((b == a) || (b == c)) ^ (a == c)

より高速になる可能性があります (これは 2 つまたは 3 つの比較、1 つの論理演算と 1 つの分岐を実行します)。

于 2012-10-22T19:14:53.487 に答える
1

私の試み...

return (ab ? (!ac) : (ac ? true : bc));

どこ：

ab = (a==b)
ac = (a==c)
bc = (b==c)

これは、条件付きジャンプを犠牲にして、2つまたは3つの比較を使用します。それぞれの場合の操作の数を確認しましょう。

  • a == c == b：（a == b）+ジャンプ+（a == c）+否定[a！=cを返す]4つの演算
  • a == b！= c：上記と同じ、4つの操作
  • a！= b == c：（a == b）+ジャンプ+（a == c）+ジャンプ+（b == c）[この値を返す]5回の操作
  • a == c！= b：（a == b）+ジャンプ+（a == c）+ジャンプ[trueを返す]4つの操作
  • a！= c！= b：上記と同じ、4つの操作

もちろん、これは操作の概念によって異なります...ジャンプが考慮されていない場合...

于 2012-10-22T18:38:58.290 に答える