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 == btrue) 并完成。
  • 如果 (a, b, c) = (1, 2, 1)，那么我们将调用b == c(false) 然后调用 (false a == b) 和a == c(true) 并完成。
  • 如果 (a, b, c) = (2, 1, 1)，那么我们将调用b == c(true)，然后调用 (true a != c) 并完成。
  • 如果 (a, b, c) = (1, 2, 3)，那么我们将调用b == c(false) 然后调用 (false a == b) 和a == c(false) 并完成。

所以最多进行 3 次比较。

在 and也有 2 个条件分支点，?:但||OP 不计算它。

于 2012-10-22T18:33:25.670 回答
3

取决于您认为是“操作”的内容...

以下仅使用数组中的 3 个比较。但是，还有第四个比较，== 1以确保只有一个匹配项。我相信你可以使用大量的分支来有条件地消除一些比较，但如果这是一种优化，分支可能会使其性能更差。

正好有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)

它具有恒定的成本，总是执行三个比较和两个逻辑运算。没有分支，它在处理器上应该很容易。

根据架构，

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

可能更快（这个执行两个或三个比较，一个逻辑运算和一个分支）。

于 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) + jump + (a==c) + 否定 [返回 a!=c] 4 次操作
  • a == b != c：同上，4个操作
  • a != b == c: (a==b) + jump + (a==c) + jump + (b==c) [返回此值] 5 次操作
  • a == c != b: (a==b) + jump + (a==c) + jump [返回 true] 4 次操作
  • a != c != b：同上，4个操作

当然，这取决于你的操作概念......如果不考虑跳跃......

于 2012-10-22T18:38:58.290 回答