一位面试官最近问了我这样一个问题:给定三个布尔变量a、b和c，如果三个变量中至少有两个为真，则返回true。
我的解决方案如下:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改进，但如何改进呢?
当前回答
这个问题的非约简解是:
a'bc + abc' + abc + ab'c
减少使用k - map，可以得到:
bc + ab + ac
可以通过在a'bc和abc' minterms上使用exclusive或，并结合abc和ab'c minterms来进一步减少此值:
b(a ^ c) + ac
其他回答
当我看到这个问题时，我的第一个想法是:
int count=0;
if (a)
++count;
if (b)
++count;
if (c)
++count;
return count>=2;
在看了其他帖子后，我承认
return (a?1:0)+(b?1:0)+(c?1:0)>=2;
更优雅。我想知道相对运行时是什么。
不过，无论如何，我认为这种解决办法比那种解决办法要好得多
return a&b | b&c | a&c;
variety because is is more easily extensible. What if later we add a fourth variable that must be tested? What if the number of variables is determined at runtime, and we are passed an array of booleans of unknown size? A solution that depends on counting is much easier to extend than a solution that depends on listing every possible combination. Also, when listing all possible combinations, I suspect that it is much easier to make a mistake. Like try writing the code for "any 3 of 4" and make sure you neither miss any nor duplicate any. Now try it with "any 5 of 7".
字面解释适用于所有主要语言:
return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;
但是我可能会让人们更容易阅读，并且扩展到三个以上——这一点似乎被许多程序员遗忘了:
boolean testBooleans(Array bools)
{
int minTrue = ceil(bools.length * .5);
int trueCount = 0;
for(int i = 0; i < bools.length; i++)
{
if(bools[i])
{
trueCount++;
}
}
return trueCount >= minTrue;
}
X = OR(a+b,c)
a b c X
1, 1, 0, 1
0, 0, 1, 1
0, 1, 1, 1
通过真值表计算:
return (a & b) | (c & (a ^ b));
在Clojure中:
(defn at-least [n & bools]
(>= (count (filter true? bools)) n)
用法:
(at-least 2 true false true)
