Проверьте, верно ли хотя бы два из трех логических значений - 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 ]

3 голосов
/ 22 июня 2010

Рассчитано с помощью таблицы истинности: 

return (a & b) | (c & (a ^ b));
3 голосов
/ 23 июня 2010

Моя первая мысль, когда я увидел вопрос, была: 

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;

разнообразие, потому что его легче расширять. Что если позже мы добавим четвертую переменную, которая должна быть проверена? Что если число переменных определяется во время выполнения, и нам передается массив логических значений неизвестного размера? Решение, которое зависит от подсчета, гораздо проще расширить, чем решение, которое зависит от перечисления всех возможных комбинаций. Кроме того, при перечислении всех возможных комбинаций, я подозреваю, что намного легче ошибиться. Например, попробуйте написать код для «любых 3 из 4» и убедитесь, что вы не пропустите ни один, ни один из них. Теперь попробуйте это с "любой 5 из 7".

3 голосов
/ 05 сентября 2010

Должно быть: 

(a || b && c) && (b || c && a)

Кроме того, если true автоматически преобразуется в 1 и false в 0: 

(a + b*c) * (b + c*a) > 0
3 голосов
/ 23 июня 2010

в рубине:

[a, b, c].count { |x| x } >= 2

Который может быть запущен в JRuby на JavaVM. ; -)

2 голосов
/ 22 июня 2010

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

2 голосов
/ 23 июня 2010

Я нашел это решение. 

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    bool result = !(a ^ b ^ c) && !(!a & !b & !c) || (a & b & c);
    return result;
}
2 голосов
/ 23 июня 2010

2 и 3 в поставленном вопросе решительно волшебны. «Правильный» ответ будет зависеть от того, пытался ли интервьюер понять вашу логическую логику (и я не думаю, что ответ pdox в этом отношении может быть лучше), или от вашего понимания архитектурных проблем.

Я был бы склонен пойти с решением сокращения карты, которое примет любой вид списка с любым произвольным условием.

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

Если целью является возвращение побитового значения «два из трех» для трех операндов, арифметический и итерационный подходы могут быть относительно неэффективными.На многих архитектурах ЦП хорошей формой будет «return ((a | b) & c) | (a & b);».Это занимает четыре логических операции.На машинах с одним аккумулятором (обычно в небольших встраиваемых системах) обычно требуется семь инструкций на байт.Форма «возврат (a & b) | (a & c) | (b & c);»возможно, выглядит лучше, но на машине с одним аккумулятором потребуется пять логических операций или девять инструкций на байт.

Кстати, в логике CMOS для вычисления «не два из трех» требуется двенадцать транзисторовДля сравнения: для инвертора требуется два, для двух входов NAND или NOR требуется четыре, а для трех входов NAND или NOR требуется шесть).

2 голосов
/ 22 июня 2010

Одна вещь, которую я не видел, на что указывают другие, это то, что стандартная вещь в разделе «пожалуйста напиши мне код» собеседования - это сказать: «Не могли бы вы улучшить это?» или "Вы полностью довольны этим?" или "это максимально оптимизировано?" когда вы говорите, что вы сделали. Возможно, вы слышали «как бы вы улучшили это», как «это можно улучшить; как?». В этом случае изменение идиомы if(x) return true; else return false; на return x является улучшением, но имейте в виду, что иногда они просто хотят увидеть, как вы реагируете на вопрос. Я слышал, что некоторые интервьюеры будут настаивать на недостатке в совершенном коде, просто чтобы посмотреть, как вы с ним справляетесь.

Страница:
...