Проверьте, верно ли хотя бы два из трех логических значений - PullRequest
Новая
       105

Проверьте, верно ли хотя бы два из трех логических значений

568 голосов
/ 19 июня 2010

Один из интервьюеров недавно задал мне этот вопрос: при наличии трех логических переменных a, b и c верните true, если хотя бы две из трех верны.

Мое решение следующее: 

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    else{
        return false;
    }
}

Он сказал, что это можно еще улучшить, но как?

Ответы [ 63 ]

813 голосов
/ 19 июня 2010

Вместо записи: 

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 и b ровно один раз и c самое большее один раз.

Ссылки

484 голосов
/ 21 июня 2010

Просто ради использования XOR для решения относительно простой задачи ... 

return a ^ b ? c : a
213 голосов
/ 19 июня 2010

Почему бы не реализовать это буквально?:) 

(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);
        }
    }
}

Это печатает следующее на моей машине (работает Ubuntu на Intel Core 2 + Sun Java Java 1.6.0_15-b03 с виртуальной машиной сервера HotSpot (14.1-b02), смешанный режим)):

Первая и вторая итерации: 

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

Интересно, что может сделать Java Java VM ухудшает производительность с течением времени для случая (a + b + c> = 2).

И вот что происходит, если я запускаю Java с -client виртуальным коммутатором: 

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

Mystery ...

И если я запускаю его в GNU Java Interpreter , он работает почти в 100 раз медленнее, но тогда выигрывает версия a&&b || b&&c || a&&c.

Результаты Tofubeer с последним кодом, работающим под управлением OS X: 

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

Результаты Paul Wagland с Mac Java 1.6.0_26-b03-383-11A511 

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
142 голосов
/ 19 июня 2010

Подобные вопросы можно решить с помощью Карты Карно : 

      | C | !C
------|---|----
 A  B | 1 | 1 
 A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

, из которой вы можете сделать вывод, что вам нужна группа для первого ряда и две группы для первого столбца, получаяоптимальное решение полигенных смазок: 

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case
139 голосов
/ 19 июня 2010

Читабельность должна быть целью.Кто-то, кто читает код, должен немедленно понять ваше намерение.Итак, вот мое решение. 

int howManyBooleansAreTrue =
      (a ? 1 : 0)
    + (b ? 1 : 0)
    + (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;
133 голосов
/ 22 июня 2010 
return (a==b) ? a : c;

Объяснение:

Если a==b, то оба являются истинными или оба ложными.Если оба они истинны, мы нашли два наших истинных логических значения и можем вернуть истину (вернув a).Если оба являются ложными, не может быть двух истинных логических значений, даже если c истинно, поэтому мы возвращаем ложное значение (возвращая a).Это часть (a==b) ? a.Как насчет : c?Хорошо, если a==b является ложным, тогда точно один из a или b должен быть истинным, поэтому мы нашли первое истинное логическое значение, и единственное, что остается важным, это если c также верно, поэтомуверните c в качестве ответа.

34 голосов
/ 19 июня 2010

Вам не нужно использовать формы короткого замыкания операторов.

return (a & b) | (b & c) | (c & a);

Выполняет то же количество логических операций, что и ваша версия, но полностью без ветвей.

27 голосов
/ 19 июня 2010

Вот общий подход, основанный на тестировании.Не настолько «эффективный», как большинство предлагаемых решений, но понятный, проверенный, работающий и обобщенный. 

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;
    }
}
24 голосов
/ 22 июня 2010

Подведите итог.Она называется булевой алгеброй по причине: 

  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
15 голосов
/ 19 июня 2010 
boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}
Страница:
...