最近、インタビュアーから次の質問がありました。3 つのブール変数 a、b、c が与えられた場合、3 つのうち少なくとも 2 つが true の場合に true を返します。
私の解決策は次のとおりです。
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
彼は、これはさらに改善できると言いましたが、どのように？
書くのではなく：
if (someExpression) {
return true;
} else {
return false;
}
書く：
return someExpression;
式自体については、次のようなものです。
boolean atLeastTwo(boolean a, boolean b, boolean c) {
return a ? (b || c) : (b && c);
}
またはこれ（把握しやすい方）：
boolean atLeastTwo(boolean a, boolean b, boolean c) {
return a && (b || c) || (b && c);
}
aこれは、 and をb正確に 1 回、多くても 1 回テストしcます。
XORを使用して比較的簡単な問題に答えるためだけに...
return a ^ b ? c : a
文字通り実装しないのはなぜですか？:)
(a?1:0)+(b?1:0)+(c?1:0) >= 2
Cでは、書くことができますa+b+c >= 2（または!!a+!!b+!!c >= 2非常に安全です）。
TofuBeerの Java バイトコードの比較に応じて、簡単なパフォーマンス テストを次に示します。
class Main
{
static boolean majorityDEAD(boolean a,boolean b,boolean c)
{
return a;
}
static boolean majority1(boolean a,boolean b,boolean c)
{
return a&&b || b&&c || a&&c;
}
static boolean majority2(boolean a,boolean b,boolean c)
{
return a ? b||c : b&&c;
}
static boolean majority3(boolean a,boolean b,boolean c)
{
return a&b | b&c | c&a;
}
static boolean majority4(boolean a,boolean b,boolean c)
{
return (a?1:0)+(b?1:0)+(c?1:0) >= 2;
}
static int loop1(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority1(data[i], data[j], data[k])?1:0;
sum += majority1(data[i], data[k], data[j])?1:0;
sum += majority1(data[j], data[k], data[i])?1:0;
sum += majority1(data[j], data[i], data[k])?1:0;
sum += majority1(data[k], data[i], data[j])?1:0;
sum += majority1(data[k], data[j], data[i])?1:0;
}
}
return sum;
}
static int loop2(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority2(data[i], data[j], data[k])?1:0;
sum += majority2(data[i], data[k], data[j])?1:0;
sum += majority2(data[j], data[k], data[i])?1:0;
sum += majority2(data[j], data[i], data[k])?1:0;
sum += majority2(data[k], data[i], data[j])?1:0;
sum += majority2(data[k], data[j], data[i])?1:0;
}
}
return sum;
}
static int loop3(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority3(data[i], data[j], data[k])?1:0;
sum += majority3(data[i], data[k], data[j])?1:0;
sum += majority3(data[j], data[k], data[i])?1:0;
sum += majority3(data[j], data[i], data[k])?1:0;
sum += majority3(data[k], data[i], data[j])?1:0;
sum += majority3(data[k], data[j], data[i])?1:0;
}
}
return sum;
}
static int loop4(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority4(data[i], data[j], data[k])?1:0;
sum += majority4(data[i], data[k], data[j])?1:0;
sum += majority4(data[j], data[k], data[i])?1:0;
sum += majority4(data[j], data[i], data[k])?1:0;
sum += majority4(data[k], data[i], data[j])?1:0;
sum += majority4(data[k], data[j], data[i])?1:0;
}
}
return sum;
}
static int loopDEAD(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majorityDEAD(data[i], data[j], data[k])?1:0;
sum += majorityDEAD(data[i], data[k], data[j])?1:0;
sum += majorityDEAD(data[j], data[k], data[i])?1:0;
sum += majorityDEAD(data[j], data[i], data[k])?1:0;
sum += majorityDEAD(data[k], data[i], data[j])?1:0;
sum += majorityDEAD(data[k], data[j], data[i])?1:0;
}
}
return sum;
}
static void work()
{
boolean [] data = new boolean [10000];
java.util.Random r = new java.util.Random(0);
for(int i=0;i<data.length;i++)
data[i] = r.nextInt(2) > 0;
long t0,t1,t2,t3,t4,tDEAD;
int sz1 = 100;
int sz2 = 100;
int sum = 0;
t0 = System.currentTimeMillis();
for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop1(data, i, sz1, sz2);
t1 = System.currentTimeMillis();
for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop2(data, i, sz1, sz2);
t2 = System.currentTimeMillis();
for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop3(data, i, sz1, sz2);
t3 = System.currentTimeMillis();
for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop4(data, i, sz1, sz2);
t4 = System.currentTimeMillis();
for(int i=0;i<data.length-sz1-sz2;i++)
sum += loopDEAD(data, i, sz1, sz2);
tDEAD = System.currentTimeMillis();
System.out.println("a&&b || b&&c || a&&c : " + (t1-t0) + " ms");
System.out.println(" a ? b||c : b&&c : " + (t2-t1) + " ms");
System.out.println(" a&b | b&c | c&a : " + (t3-t2) + " ms");
System.out.println(" a + b + c >= 2 : " + (t4-t3) + " ms");
System.out.println(" DEAD : " + (tDEAD-t4) + " ms");
System.out.println("sum: "+sum);
}
public static void main(String[] args) throws InterruptedException
{
while(true)
{
work();
Thread.sleep(1000);
}
}
}
これにより、私のマシンに次のように出力されます（Intel Core 2 + sun java 1.6.0_15-b03でUbuntuを実行し、HotSpot Server VM（14.1-b02、混合モード））：
1 回目と 2 回目の反復:
a&&b || b&&c || a&&c : 1740 ms
a ? b||c : b&&c : 1690 ms
a&b | b&c | c&a : 835 ms
a + b + c >= 2 : 348 ms
DEAD : 169 ms
sum: 1472612418
その後の反復:
a&&b || b&&c || a&&c : 1638 ms
a ? b||c : b&&c : 1612 ms
a&b | b&c | c&a : 779 ms
a + b + c >= 2 : 905 ms
DEAD : 221 ms
(a + b + c >= 2) の場合、時間の経過とともにパフォーマンスが低下する Java VM は何ができるのだろうか。
-clientVM スイッチを使用して Java を実行すると、次のようになります。
a&&b || b&&c || a&&c : 4034 ms
a ? b||c : b&&c : 2215 ms
a&b | b&c | c&a : 1347 ms
a + b + c >= 2 : 6589 ms
DEAD : 1016 ms
神秘...
GNU Java Interpreterで実行すると、ほぼ 100 倍遅くなりますが、その場合はa&&b || b&&c || a&&cバージョンが優先されます。
OS X を実行している最新のコードを使用した Tofubeer の結果:
a&&b || b&&c || a&&c : 1358 ms
a ? b||c : b&&c : 1187 ms
a&b | b&c | c&a : 410 ms
a + b + c >= 2 : 602 ms
DEAD : 161 ms
Mac Java 1.6.0_26-b03-383-11A511 を使用した Paul Wagland の結果
a&&b || b&&c || a&&c : 394 ms
a ? b||c : b&&c : 435 ms
a&b | b&c | c&a : 420 ms
a + b + c >= 2 : 640 ms
a ^ b ? c : a : 571 ms
a != b ? c : a : 487 ms
DEAD : 170 ms
return (a==b) ? a : c;
説明：
の場合a==b、両方がtrueまたは両方がfalseです。両方がtrueの場合、2つのtrueブール値が見つかり、trueを返すことができます（を返すことによってa）。両方がfalseの場合、trueであっても2つのtrueブール値は存在できないcため、falseを返します（を返すことによりa）。それがその(a==b) ? a一部です。どう: cですか？がfalseの場合、またはa==bの1つがtrueである必要があるため、最初のtrueブール値が見つかりました。重要なのはifもtrueであるため、答えとして戻ります。abcc
この種の質問は、カルノー マップで解決できます。
| C | !C
------|---|----
A B | 1 | 1
A !B | 1 | 0
!A !B | 0 | 0
!A B | 1 | 0
そこから、最初の行に 1 つのグループ、最初の列に 2 つのグループが必要であると推測し、polygenelubricants の最適解を取得します。
(C && (A || B)) || (A && B) <---- first row
^
|
first column without third case
読みやすさが目標であるべきです。コードを読んだ人は、すぐにあなたの意図を理解する必要があります。だからここに私の解決策があります。
int howManyBooleansAreTrue =
(a ? 1 : 0)
+ (b ? 1 : 0)
+ (c ? 1 : 0);
return howManyBooleansAreTrue >= 2;
演算子の短絡形式を使用する必要はありません。
return (a & b) | (b & c) | (c & a);
これは、バージョンと同じ数の論理演算を実行しますが、完全にブランチレスです。
これは、テスト駆動型の一般的なアプローチです。これまでに提供されたほとんどのソリューションほど「効率的」ではありませんが、明確で、テストされ、機能し、一般化されています。
public class CountBooleansTest extends TestCase {
public void testThreeFalse() throws Exception {
assertFalse(atLeastTwoOutOfThree(false, false, false));
}
public void testThreeTrue() throws Exception {
assertTrue(atLeastTwoOutOfThree(true, true, true));
}
public void testOnes() throws Exception {
assertFalse(atLeastTwoOutOfThree(true, false, false));
assertFalse(atLeastTwoOutOfThree(false, true, false));
assertFalse(atLeastTwoOutOfThree(false, false, true));
}
public void testTwos() throws Exception {
assertTrue(atLeastTwoOutOfThree(false, true, true));
assertTrue(atLeastTwoOutOfThree(true, false, true));
assertTrue(atLeastTwoOutOfThree(true, true, false));
}
private static boolean atLeastTwoOutOfThree(boolean b, boolean c, boolean d) {
return countBooleans(b, c, d) >= 2;
}
private static int countBooleans(boolean... bs) {
int count = 0;
for (boolean b : bs)
if (b)
count++;
return count;
}
}
それを合計します。ブール代数と呼ばれる理由は次のとおりです。
0 x 0 = 0
1 x 0 = 0
1 x 1 = 1
0 + 0 = 0
1 + 0 = 1
1 + 1 = 0 (+ carry)
そこの真理値表を見ると、乗算はブール演算であり、単純に加算は xor であることがわかります。
あなたの質問に答えるには：
return (a + b + c) >= 2
boolean atLeastTwo(boolean a, boolean b, boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
それは、「改善」が何を意味するかによって大きく異なります。
より明確ですか？
boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
return (a && b) || (a && c) || (b && c);
}
ターサー？
boolean moreThanTwo(boolean a, boolean b, boolean c)
{
return a == b ? a : c;
}
もっと一般的な？
boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;
for(boolean b : bs)
{
count += b ? 1 : 0;
if(count > x) return true;
}
return false;
}
よりスケーラブルですか？
boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;
for(int i < 0; i < bs.length; i++)
{
count += bs[i] ? 1 : 0;
if(count > x) return true;
int needed = x - count;
int remaining = bs.length - i;
if(needed >= remaining) return false;
}
return false;
}
もっと早く？
// Only profiling can answer this.
どちらが「改善」されるかは、状況によって大きく異なります。
map/reduce を使用した別の実装を次に示します。これは、分散環境で数十億のブール値©にうまくスケーリングします。MongoDB の使用:
valuesブール値のデータベースの作成:
db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});
マップの作成、関数の削減:
編集:マップ/リデュースをジェネリックリストに適用することに関するCurtainDogの 回答が好きなので、値をカウントするかどうかを決定するコールバックを受け取るマップ関数を次に示します。
var mapper = function(shouldInclude) {
return function() {
emit(null, shouldInclude(this) ? 1 : 0);
};
}
var reducer = function(key, values) {
var sum = 0;
for(var i = 0; i < values.length; i++) {
sum += values[i];
}
return sum;
}
マップ/リデュースの実行:
var result = db.values.mapReduce(mapper(isTrue), reducer).result;
containsMinimum(2, result); // true
containsMinimum(1, result); // false
function isTrue(object) {
return object.value == true;
}
function containsMinimum(count, resultDoc) {
var record = db[resultDoc].find().next();
return record.value >= count;
}
ここで答えを（これまでのところ）取ってください：
public class X
{
static boolean a(final boolean a, final boolean b, final boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
static boolean b(final boolean a, final boolean b, final boolean c)
{
return a ? (b || c) : (b && c);
}
static boolean c(final boolean a, final boolean b, final boolean c)
{
return ((a & b) | (b & c) | (c & a));
}
static boolean d(final boolean a, final boolean b, final boolean c)
{
return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
}
}
逆コンパイラを介してそれらを実行します (javap -c X > results.txt):
Compiled from "X.java"
public class X extends java.lang.Object{
public X();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."<init>":()V
4: return
static boolean a(boolean, boolean, boolean);
Code:
0: iload_0
1: ifeq 8
4: iload_1
5: ifne 24
8: iload_1
9: ifeq 16
12: iload_2
13: ifne 24
16: iload_0
17: ifeq 28
20: iload_2
21: ifeq 28
24: iconst_1
25: goto 29
28: iconst_0
29: ireturn
static boolean b(boolean, boolean, boolean);
Code:
0: iload_0
1: ifeq 20
4: iload_1
5: ifne 12
8: iload_2
9: ifeq 16
12: iconst_1
13: goto 33
16: iconst_0
17: goto 33
20: iload_1
21: ifeq 32
24: iload_2
25: ifeq 32
28: iconst_1
29: goto 33
32: iconst_0
33: ireturn
static boolean c(boolean, boolean, boolean);
Code:
0: iload_0
1: iload_1
2: iand
3: iload_1
4: iload_2
5: iand
6: ior
7: iload_2
8: iload_0
9: iand
10: ior
11: ireturn
static boolean d(boolean, boolean, boolean);
Code:
0: iload_0
1: ifeq 8
4: iconst_1
5: goto 9
8: iconst_0
9: iload_1
10: ifeq 17
13: iconst_1
14: goto 18
17: iconst_0
18: iadd
19: iload_2
20: ifeq 27
23: iconst_1
24: goto 28
27: iconst_0
28: iadd
29: iconst_2
30: if_icmplt 37
33: iconst_1
34: goto 38
37: iconst_0
38: ireturn
}
?: のものは、元の修正バージョンよりもわずかに優れていることがわかります。最良のものは、分岐を完全に回避するものです。これは、(ほとんどの場合) 命令が少ないという観点からは良いことであり、分岐予測で間違った推測を行うと CPU のストールが発生する可能性があるため、CPU の分岐予測部分にとってはより適切です。
最も効率的なのは、moonshadow 全体のものだと思います。平均して使用する命令が最も少なく、CPU でパイプラインが停止する可能性が低くなります。
100% 確実にするには、各命令のコスト (CPU サイクル単位) を調べる必要がありますが、残念ながらすぐには入手できません (ホットスポットのソースを調べてから、当時の CPU ベンダーの仕様を調べる必要があります)。生成された命令ごとに取得されます)。
コードのランタイム分析については、Rotsor による更新された回答を参照してください。
直接コードの別の例:
int n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);
明らかに、これは最も簡潔なコードではありません。
補遺
これの別の (わずかに最適化された) バージョン:
int n = -2;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 0);
これは、0 との比較が 2 との比較よりも高速な (またはおそらく少ない) コードを使用すると仮定すると、わずかに高速に実行される可能性があります。
最も明らかな改善点は次のとおりです。
// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
return false;
}
その後
// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
return ((a && b) || (b && c) || (a && c));
}
しかし、それらの改善はマイナーです。
これを行う別の方法ですが、あまり良い方法ではありません。
return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);
ハッシュコード値は、trueのBoolean場合は 1231、false の場合は 1237 に固定されているため、同様に使用できます。<= 3699
私は（return a ? (b || c) : (b && c);トップの回答から）三項が好きではありません。誰もそれについて言及しているとは思いません。次のように書かれています。
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if (a) {
return b||c;
}
else {
return b&&C;
}
Clojureの場合:
(defn at-least [n & bools]
(>= (count (filter true? bools)) n)
使用法：
(at-least 2 true false true)
この解決策はまだ見たことがないと思います：
boolean atLeast(int howMany, boolean[] boolValues) {
// check params for valid values
int counter = 0;
for (boolean b : boolValues) {
if (b) {
counter++;
if (counter == howMany) {
return true;
}
}
}
return false;
}
その利点は、探している数に達すると壊れることです。したがって、これが「この 1,000,000 個の値のうち少なくとも 2 つが true である」場合、最初の 2 つが実際に true である場合、より「通常の」ソリューションよりも高速になるはずです。
ブール値を整数に変換して、この簡単なチェックを実行できます。
(int(a) + int(b) + int(c)) >= 2
コードの改善方法が明記されていなかったので、コードをもっと面白くするように改善するよう努めます。これが私の解決策です：
boolean atLeastTwo(boolean t, boolean f, boolean True) {
boolean False = True;
if ((t || f) && (True || False))
return "answer" != "42";
if (t && f)
return !"France".contains("Paris");
if (False == True)
return true == false;
return Math.random() > 0.5;
}
このコードが機能するかどうか疑問に思っている人のために、同じロジックを使用して単純化したものを次に示します。
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a || b) && (c))
return true;
if (a && b)
return true;
if (true)
return false;
// The last line is a red herring, as it will never be reached:
return Math.random() > 0.5;
}
これはさらに次のように要約できます。
return ((a || b) && (c)) || (a && b);
でも今はもう面白くない。
Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
return (System.Convert.ToInt16(val1) +
System.Convert.ToInt16(val2) +
System.Convert.ToInt16(val3)) > 1;
}
やり方が多すぎる…
文字どおりの解釈は、すべての主要言語で機能します。
return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;
しかし、私はおそらく人々が読みやすくし、3つ以上に拡張できるようにするでしょう.これは多くのプログラマーが忘れているようです:
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;
}
AC ソリューション。
int two(int a, int b, int c) {
return !a + !b + !c < 2;
}
またはあなたが好むかもしれません：
int two(int a, int b, int c) {
return !!a + !!b + !!c >= 2;
}
Cの場合：
return !!a + !!b + !!c >= 2;
混乱せず、読みやすい最も簡単な方法（IMO）：
// Three booleans, check if two or more are true
return ( a && ( b || c ) ) || ( b && c );
真理値表を介して計算:
return (a & b) | (c & (a ^ b));
現在Java 8を使用していますが、私は次のようなものを本当に好みます:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
return Stream.of(a, b, c).filter(active -> active).count() >= 2;
}
return 1 << $a << $b << $c >= 1 << 2;
@TofuBeer TofuBeer の優れた投稿への追加として、@pdox pdox の回答を検討してください。
static boolean five(final boolean a, final boolean b, final boolean c)
{
return a == b ? a : c;
}
「javap -c」で指定された逆アセンブル バージョンも考慮してください。
static boolean five(boolean, boolean, boolean);
Code:
0: iload_0
1: iload_1
2: if_icmpne 9
5: iload_0
6: goto 10
9: iload_2
10: ireturn
pdox の回答は、以前のどの回答よりも少ないバイト コードにコンパイルされます。その実行時間は他のものと比べてどうですか?
one 5242 ms
two 6318 ms
three (moonshadow) 3806 ms
four 7192 ms
five (pdox) 3650 ms
少なくとも私のコンピューターでは、pdox の回答は @moonshadow moonshadow の回答よりもわずかに高速であり、pdox は全体的に最速です (私の HP/Intel ラップトップでは)。
参考までに、これは全加算器のキャリーアウトビットにすぎません。ハードウェアでは、論理的な努力を使用して、さまざまなブール式に基づいて最適な回路を決定できます。従来のXORソリューションは、ポスターが提示した簡潔でない表現よりも多くの労力を要すると思います。
質問を見て最初に思ったのは、
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;
より簡単に拡張できるからです。後でテストする必要がある 4 番目の変数を追加するとどうなるでしょうか? 変数の数が実行時に決定され、未知のサイズのブール値の配列が渡された場合はどうなるでしょうか? カウントに依存するソリューションは、考えられるすべての組み合わせをリストすることに依存するソリューションよりも拡張がはるかに簡単です。また、考えられるすべての組み合わせをリストすると、間違いを犯しやすいのではないかと思います。「any 3 of 4」のコードを書いてみて、見落としたり重複したりしないようにしてください。「any 5 of 7」で試してみてください。
この種の読み方はより良いです：
if (a) {
return b || c;
}
else {
return b && c;
}
彼はおそらく、ビットごとの比較演算子のような複雑なもの (通常は複雑ではありませんが、ブール値ではビットごとの演算子を使用するのは非常に奇妙です) や、int に変換してそれらを合計するような非常に回り道的なものを探しているわけではありません。
これを解決する最も直接的で自然な方法は、次のような式を使用することです。
a ? (b || c): (b && c)
必要に応じて関数に入れますが、それほど複雑ではありません。このソリューションは、論理的に簡潔で効率的です。
そのはず：
(a || b && c) && (b || c && a)
また、がおよびにtrue自動的に変換される場合:1false0
(a + b*c) * (b + c*a) > 0
ルビーの場合:
[a, b, c].count { |x| x } >= 2
これは、JavaVM 上の JRuby で実行できます。;-)
三項演算子はオタクジュースを流しますが、混乱する可能性があります（コードの保守性が低下するため、バグ注入の可能性が高くなります）。ジェフ・アットウッドはここでそれをうまく言いました：
これは、まったく意味のない1回の書き込み時間の節約と、数十の読み取り時間の理解のペナルティとのトレードオフの完璧な例です。
三項演算子を避けて、次の関数を作成しました。
function atLeastTwoTrue($a, $b, $c) {
$count = 0;
if ($a) { $count++; }
if ($b) { $count++; }
if ($c) { $count++; }
if ($count >= 2) {
return true;
} else {
return false;
}
}
これは他のいくつかのソリューションと同じくらいクールですか？いいえ、わかりやすいですか？はい。それは、より保守しやすく、バグの少ないコードにつながりますか？はい。
この問題に対する非還元の解決策は次のとおりです。
a'bc + abc' + abc + ab'c
K-Mapsを使用して削減すると、次のようになります。
bc + ab + ac
排他的論理和またはa'bcおよびabc'mintermsを使用し、abcおよびab'c mintermsを組み合わせることで、これをさらに減らすことができます。
b(a ^ c) + ac
確かに、実際のコーディング能力よりも、問題をどのように解決するか/考えるかについての質問です。
少し簡潔なバージョンは
return（（a ^ b）&&（b ^ c））^ b
しかし、前のポスターが言ったように、私が取り組んでいるコードでこれを見た場合、誰かが耳を傾けるでしょう。:)
他の人が指摘するのを見たことがありませんが、採用面接の「コードを書いてください」セクションで行う標準的なことは、「それを改善できますか?」ということです。または「それに完全に満足していますか」または「それは可能な限り最適化されていますか?」あなたが終わったと言うとき。「どうすればそれを改善できますか」という言葉が、「これは改善される可能性があります。どのように改善しますか?」と聞こえた可能性があります。この場合、if(x) return true; else return false;慣用句を just に変更するreturn xと改善されますが、質問に対してあなたがどのように反応するかを見たいだけの場合があることに注意してください。完全なコードには欠陥があると主張するインタビュアーもいると聞いたことがあります。
質問に対する最良の答えは、「従業員として、パフォーマンスに必要な効率を維持しながら、私の意味が明確になるように書くことが重要です。」これが私がそれを書く方法です：
function atLeastTwoAreTrue(a, b, c) {
return (a && b) || (b && c) || (a && c);
}
実際には、テストは非常に工夫されているため、単純なコメントで対応する場合、可能な限り最速で最も不可解なメソッドを作成しても完全に受け入れられます。しかし、一般的に、このワンライナーの世界では、この世界ではもっと読みやすいコードが必要です。:-)
どうですか-Java(a||b) && (a||c)は、OPの6つではなく3つの比較を使用します。
ダメだ、もっと早く調べるべきだった。
C#では、私の頭の上から:
public bool lol(int minTrue, params bool[] bools)
{
return bools.Count( ( b ) => b ) >= minTrue;
}
かなり速いはずです。
呼び出しは次のようになります。
lol( 2, true, true, false );
このように、ルール (2 つが true である必要があります) をメソッドに埋め込むのではなく、呼び出し元に任せます。
パフォーマンスのコンテキストではないが、優れたコード (再利用できる拡張可能で読み取り可能なコード)
static boolean trueBooleans (int howMany,boolean ... bools)
{
int total = 0;
for (boolean b:bools)
if (b && (++total == howMany)) return true;
return false;
}
Java を作成するときの私の謙虚な意見では、予期しない変更を簡単に処理し、コードの重複がないことが、簡潔 (スクリプト言語のドメイン) や高速なプログラムよりも重要です。
目標が 3 つのオペランドに対してビット単位の 2/3 の値を返すことである場合、算術および反復アプローチは比較的効果的ではありません。多くの CPU アーキテクチャでは、適切な形式は "return ((a | b) & c) | (a & b);" です。これには 4 つのブール演算が必要です。単一アキュムレータ マシン (小規模な組み込みシステムで一般的) では、1 バイトあたり合計 7 つの命令を使用する傾向があります。"return (a & b) | (a & c) | (b & c);" という形式 見栄えは良いかもしれませんが、単一のアキュムレータ マシンでは 5 つのブール演算、つまり 1 バイトあたり 9 つの命令が必要になります。
ちなみに、CMOS ロジックでは、「not two out of three」を計算するには 12 個のトランジスタが必要です (比較のために、インバータには 2 個、2 入力の NAND または NOR には 4 個、3 入力の NAND または NOR には 6 個必要です)。
int count=0;
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if (a)
count++;
if (b)
count++;
if (c)
count++;
if (count>1)
return true;
else
return false;
}
3 つのブール値を A、B、C とします。
k-MAP を使用してブール式を使用できます...
この場合、ブール式は A(B+C) + C になります
または if(((A && (B || C )) || C ) { true を返します。それ以外の場合は false を返します。
この解決策を見つけました。
boolean atLeastTwo(boolean a, boolean b, boolean c) {
bool result = !(a ^ b ^ c) && !(!a & !b & !c) || (a & b & c);
return result;
}
提起された質問の 2 と 3 は明らかに魔法の数字です。「正しい」答えは、インタビュアーがブール論理を理解しようとしていたか (この点で pdox の答えに勝るものはないと思います)、またはアーキテクチャの問題を理解しているかによって異なります。
任意の条件を持つあらゆる種類のリストを受け入れるマップ削減ソリューションを使用する傾向があります。
C：
if (!!a + !!b + !!c >= 2)
Java 8 のStream機能を使用して、これに別のアプローチを取り、任意の必要量を持つ任意の数のブール値を取得します。すべての要素を処理する前に制限に達すると、ストリームは短絡します。
public static boolean atLeastTrue(int amount, Boolean ... booleans) {
return Stream.of(booleans).filter(b -> b).limit(amount).count() == amount;
}
public static void main(String[] args){
System.out.println("1,2: " + atLeastTrue(1, true, false, true));
System.out.println("1,1: " + atLeastTrue(1, false, true));
System.out.println("1,0: " + atLeastTrue(1, false));
System.out.println("1,1: " + atLeastTrue(1, true, false));
System.out.println("2,3: " + atLeastTrue(2, true, false, true, true));
System.out.println("3,2: " + atLeastTrue(3, true, false, true, false));
System.out.println("3,3: " + atLeastTrue(3, true, true, true, false));
}
出力：
1,2: true
1,1: true
1,0: false
1,1: true
2,3: true
3,2: false
3,3: true
ブール値を数値に変換した場合、その数値が 2 の累乗でない場合、少なくとも 2 つの true があります。
a*4 + b*2 + c*1 = N
return( N != 0 && (N&(N-1)) != 0)
代替案を提示しているだけです。
X = OR(a+b,c)
abc X
1 1 0 1
0 0 1 1
0 1 1 1
これはどう：
(a - b) ? c : a
3つのうち3つはかなり任意の数であり、関数は任意の数で機能するはずです。したがって、質問に答えるために、配列内のxがtrueの場合に機能する関数を記述します。たとえば、
bool istrue ( int x, bool[] list)
y = count true in list
return y >= x
関数koは答えを返します：
static int ho(bool a)
{
return a ? 1 : 0;
}
static bool ko(bool a, bool b, bool c)
{
return ho(a) + ho(b) + ho(c) >= 2 ? true : false;
}
関数 atLeastTwoTrue($a, $b, $c) {
int カウント = 0;
カウント = (a ? カウント + 1 : カウント);
カウント = (b ? カウント + 1 : カウント);
カウント = (c ? カウント + 1 : カウント);
リターン (カウント >= 2);
}
public static boolean atLeast(int atLeastToBeTrue, boolean...bools){
int booleansTrue = 0;
for(boolean tmp : bools){
booleansTrue += tmp ? 1 : 0;
}
return booleansTrue >= atLeastToBeTrue;
}
あなたは別名からどれだけat least真実になりたいかを選ぶことができます:-)varargsboolean[]
三項演算子を使用して問題を解決する最も単純な形式は次のとおりです。
return a ? (b ? true : c) : (b ? c : false);
また、要件の二重否定を使用して解決策を見つけることに投資することもできます。つまり、少なくとも 2 つの真の値ではなく、多くても 1 つの偽の値で条件を満たす必要があります。
ブール値が多い場合は、演算子のオーバーロードが簡単です。
operator fun Boolean.unaryPlus() = if (this) 1 else 0
// ...
if(+bool1 + +bool2 + ... + +boolN > 2) {
// ...
}
単純なブール演算子 (a || b) && (b || c) を使用することは問題なく、より簡単だと思います。
3 つの文字のいずれかを他の 2 つの文字と入れ替えても、同じ表現のままです。
最も簡単な解決策は次のとおりだと思います。
リターン (a && b) || c;
私の最初の考えは
return (a||b)&&(b||c)
しかし、読みやすくするために、提案された a+b+c>=2 ソリューションが気に入りました。