Можете ли вы упростить этот алгоритм?

Ответ 1

(a + p <= b) && (a != 1) && (b - a - p != 1);

Ответ 2

Если формула работает и исходит из ваших бизнес-правил, нет реальной необходимости ее упростить. Возможно, компилятор лучше знает, как оптимизировать формулу.

Единственное, что вам нужно сделать, это использовать имена переменных переменных, которые отражают бизнес-логику.

Остерегайтесь применения какого-либо предлагаемого решения до его тестирования.

Ответ 3

Рефактор для простоты, введя более локальные переменные, которые указывают значение каждого выражения. Это трудно для нас сделать, не имея представления о том, что означает a, b и p.

Ответ 4

b >= p && b != p+1

EDIT: Хорошо, это не сработало, но это делает:

a != 1 && b >= a+p && b-a-p != 1

Ответ 5

(a!=1) && ((b==a+p) || (b>1+a+p))

Он может быть не самым простым, но должен быть одним из самых читаемых.

Ответ 6

Я бы не сделал всю математику в этом выражении. Например, b - (a + p) оценивается дважды. Если возможно, разделите их на переменные.

Кроме того, при написании дерева изящного извещения можно оптимизировать его, все, что вы видите дважды, можно повторно использовать.

Ответ 7

Поскольку все они являются положительными, много повторений можно удалить:

Итак, как первый шаг,

(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

становится

((a+p) <= b) && (a != 1) && (b >= p)) && ((b - (a + p) != 1) 

Для ясности это просто заменяет шаблон (foo == 0 || foo > 1) на foo != 1

Этот шаблон появляется дважды выше, один раз с foo = a и один раз с foo = (b - (a+p))

Ответ 8

Так как ints без знака, (a == 0 || a > 1) можно заменить (a!= 1).

С первого прохода вы можете уменьшить его до этого:

uint sum = a + p;
return ((sum <= b) && (a != 1) && (b >= p)) && (b - sum != 1);

Кроме того, было бы гораздо более читаемым, если бы вы смогли дать более значимые имена переменным. Например, если a и p были давлениями, то a + p может быть заменено как PressureSum.

Ответ 9

bap = b - (a + p)
bap >= 0 && bap != 1 && a != 1

EDIT: теперь у меня есть -2 для честной попытки помочь, а также для того, что мне кажется правильным. Для вас, кто может использовать Python, вот две функции: одна с вопросом и одна с моим ответом:

def question(a, b, p):
    return (((a+p) <= b) and (a == 0 or a > 1) and (b >= p)) or ((b - (a + p) == 0) or (b - (a + p) > 1))

def answer(a, b, p):
    bap = b - (a + p)
    return bap >= 0 and bap != 1 and a != 1

Ответ 10

s = a + p
b >= s && a != 1 && b - s - 1 > 0

Проверено, возвращает то же логическое значение, что и вопрос.

Программа, которую я использовал для проверки: (получал удовольствие писать ее)

#include <iostream>
using namespace std;

typedef unsigned int uint;

bool condition(uint a, uint b, uint p)
{
        uint s = a + p;
        return uint(    b >= s && a != 1 && b - s - 1 > 0    )
        == uint(    (((a+p) <= b) && (a == 0 || a > 1) && (b >= p))
                 && ((b - (a + p) == 0) || (b - (a + p) > 1))    );
}

void main()
{
    uint i = 0;
    uint j = 0;
    uint k = 0;

    const uint max = 50;

    for (uint i = 0; i <= max; ++i)
        for (uint j = 0; j <= max; ++j)
            for (uint k = 0; k <= max; ++k)
                if (condition(i, j, k) == false)
                {
                    cout << "Fails on a = " << i << ", b = " << j;
                    cout << ", p = " << k << endl;

                    int wait = 0;
                    cin >> wait;
                }
}

Ответ 11

Это так просто, как я мог его получить.

def calc(a, b, p):
    if (a != 1):
        temp = a - b + p
        if temp == 0 or temp < -1:
            return True
    return False

Он также может быть записан как:

def calc(a, b, p):
    temp = a - b + p
    return a != 1 and (temp == 0 or temp < -1)

Или как:

def calc(a, b, p):
    temp = a - b + p
    return a != 1 and temp <= 0 and temp != -1

Ответ 12

Протестировано с помощью a, b, p от 0 до 10000:

a != 1 && a != (b-p-1) && a <= (b-p);

Я думаю, что его можно упростить еще больше.

Ответ 13

мои извинения за ошибку в исходном деривации. Это происходит, когда вы не беспокоитесь о unit test после рефакторинга!

исправленный вывод следует в виде тестовой программы.

Короткий ответ:

((a > 1) && (skeet == 0)) || ((a > 1) && (jon > 0) && (skeet < -1));

где

jon = (b - p)
skeet = (a - jon);

class Program
{
    static void Main(string[] args)
    {
        bool ok = true;
        for (int a = 1; a < 100; a++)
        {
            Console.Write(a.ToString());
            Console.Write("...");

            for (int b = 1; b < 100; b++)
            {
                for (int p = 1; p < 100; p++)
                {
                    bool[] results = testFunctions(a, b, p);
                    if (!allSame(results))
                    {
                        Console.WriteLine(string.Format(
                            "Fails for {0},{1},{2}", a, b, p));
                        for (int i = 1; i <= results.Length; i++)
                        {
                            Console.WriteLine(i.ToString() + ": " + 
                                results[i-1].ToString());
                        }

                        ok = false;
                        break;
                    }
                }
                if (!ok) { break; }
            }
            if (!ok) { break; }
        }
        if (ok) { Console.WriteLine("Success"); }
        else { Console.WriteLine("Failed!"); }
        Console.ReadKey();
    }

    public static bool allSame(bool[] vals)
    {
        bool firstValue = vals[0];
        for (int i = 1; i < vals.Length; i++)
        {
            if (vals[i] != firstValue)
            {
                return false;
            }
        }
        return true;
    }

    public static bool[] testFunctions(int a, int b, int p)
    {
        bool [] results = new bool[16];

        //given: all values are positive integers
        if (a<=0 || b<=0 || p<=0)
        {
            throw new Exception("All inputs must be positive integers!");
        }

        //[1] original expression
        results[0] = (((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[2] a==0 cannot be true since a is a positive integer
        results[1] = (((a+p) <= b) && (a > 1) && (b >= p)) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[3] rewrite (b >= p) && ((a+p) <= b) 
        results[2] = (b >= p) && (b >= (a+p)) && (a > 1) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[4] since a is positive, (b>=p) guarantees (b>=(p+a)) so we 
        //can drop the latter term
        results[3] = (b >= p) && (a > 1) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[5] separate the two cases b>=p and b=p
        results[4] = ((b==p) && (a > 1) && ((b - (a + p) == 0) || 
            (b - (a + p) > 1))) || ((b > p) && (a > 1) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1)));

        //[6] rewrite the first case to eliminate p (since b=p 
        //in that case)
        results[5] = ((b==p) && (a > 1) && ((-a == 0) || 
            (-a > 1))) || ((b > p) && (a > 1) && 
            (((b - a - p) == 0) || ((b - a - p) > 1)));

        //[7] since a>0, neither (-a=0) nor (-a>1) can be true, 
        //so the case when b=p is always false
        results[6] = (b > p) && (a > 1) && (((b - a - p) == 0) || 
            ((b - a - p) > 1));

        //[8] rewrite (b>p) as ((b-p)>0) and reorder the subtractions
        results[7] = ((b - p) > 0) && (a > 1) && (((b - p - a) == 0) || 
            ((b - p - a) > 1));

        //[9] define (b - p) as N temporarily
        int N = (b - p);
        results[8] = (N > 0) && (a > 1) && (((N - a) == 0) || ((N - a) > 1));

        //[10] rewrite the disjunction to isolate a
        results[9] = (N > 0) && (a > 1) && ((a == N) || (a < (N - 1)));

        //[11] expand the disjunction
        results[10] = ((N > 0) && (a > 1) && (a == N)) ||
            ((N > 0) && (a > 1) && (a < (N - 1)));

        //[12] since (a = N) in the first subexpression we can simplify to
        results[11] = ((a == N) && (a > 1)) || 
            ((N > 0) && (a > 1) && (a < (N - 1)));

        //[13] extract common term (a > 1) and replace N with (b - p)
        results[12] = (a > 1) && ((a == (b - p)) || 
            (((b - p) > 0) && (a < (b - p - 1))));

        //[14] extract common term (a > 1) and replace N with (b - p)
        results[13] = (a > 1) && (((a - b + p) == 0) || 
            (((b - p) > 0) && ((a - b + p) < -1)));

        //[15] replace redundant subterms with intermediate 
        //variables (to make Jon Skeet happy)
        int jon = (b - p);
        int skeet = (a - jon);   //(a - b + p) = (a - (b - p))
        results[14] = (a > 1) && ((skeet == 0) || 
            ((jon > 0) && (skeet < -1)));

        //[16] rewrite in disjunctive normal form
        results[15] = ((a > 1) && (skeet == 0)) || 
            ((a > 1) && (jon > 0) && (skeet < -1));

        return results;
    }
}

Ответ 14

// In one line:
return (a != 1) && ((b-a-p == 0) || (b-a-p > 1))

// Expanded for the compiler:
if(a == 1)
    return false;

int bap = b - a - p;

return (bap == 0) || (bap > 1);

Если вы публикуете процессор, который используете, я могу оптимизировать его для сборки. =]

Ответ 15

jjngy здесь имеет это право. Здесь доказательство того, что его упрощенная формула эквивалентна оригиналу с помощью Coq Proof Assistant.

Require Import Arith.
Require Import Omega.

Lemma eq : forall (a b p:nat),
(((a+p) <= b) /\ ((a = 0) \/ (a > 1)) /\ (b >= p)) /\ 
    ((b - (a + p) = 0) \/ (b - (a + p) > 1)) <-> 
((a + p <= b) /\ ~ (a= 1) /\ ~ (b - a - p = 1)).
Proof. intros; omega. Qed.

Ответ 16

Хорошо

((b - (a + p) == 0) || (b - (a + p) > 1))

Would be better writen as:
(b - (a + p) >= 0)  

Applying this to the whole string you get:

((a+p) <= b) && (a > 1) && (b >= p)) && (b - (a + p) >= 0) 


(a + p) <= b is the same thing as b - (a + p) >= 0

Итак, вы можете избавиться от этого:

((a+p) <= b) && (a > 1) && (b >= p)) 

Ответ 17

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

bool bool1 = ((a+p) <= b) && (a == 0 || a > 1) && (b >= p);
bool bool2 = (b - (a + p) == 0) || (b - (a + p) > 1);

return bool1 && bool2;

Вторая итерация:

int value1 = b - (a + p);
bool bool1 = (value1 >= 0) && (a == 0 || a > 1) && (b >= p);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

Третья итерация (все позитивы)

int value1 = b - (a + p);
bool bool1 = (value1 >= 0) && (a != 1) && (b >= p);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

4-я итерация (все позитивы)

int value2 = b - p;
int value1 = value2 - a;
bool bool1 = (value1 >= 0) && (a != 1) && (b - p >= 0);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

5-я итерация:

int value2 = b - p;
int value1 = value2 - a;
bool bool1 = (value1 >= 0) && (a != 1) && (value2 >= 0);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

Ответ 18

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

// Initial equation
(((a + p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

// ((a + p) <= b) iif a = 0 && p = b; therefore, b = p and a = 0 for this to work
(b == p) && ((b - (a + p) == 0) || (b - (a + p) > 1))

// Simplification, assuming that b = p and a = 0
(b == p) && (a == 0)

Однако, если мы работаем в предположении, что ноль не является положительным или отрицательным, то это означает, что любое значение a, предоставленное уравнение будет больше или равно единице. Это, в свою очередь, означает, что уравнение всегда будет оцениваться как ложное из-за того, что следующее:

(a == 0 || a > 1)

Оценил бы только true, когда a >= 2; однако, если верно и следующее:

(b >= p)

Тогда это означает, что p не меньше, чем b, таким образом:

((a + p) <= b)

Подстановкой становится:

((2 + b) <= b)

Который явно не может оценить true.

Ответ 19

Я добавил это как комментарий к ответу на nickf, но подумал, что предлагаю его в качестве ответа на него. Хорошие ответы кажутся вариацией его, в том числе и моей. Но поскольку мы не зависим от компилятора для оптимизации (если бы OP был, мы бы даже не делали этого), то кипячение этого вниз от 3 AND до следующего означает, что будут значения, где только 2 из 3 порций необходимо будет оценить. И если это выполняется в script, это будет иметь значение, в отличие от скомпилированного кода.

(a != 1) && ((b > (a + p + 1)) || (b == (a + p))))

Основываясь на комментарии, я добавлю, что это лучше, чем версия AND:

Я думаю, это зависит от того, превышает ли ваш набор данных истинных результатов более 50% наборов входных данных. Чем чаще ввод верен, тем лучше будет моя вариация. Итак, с этим уравнением, похоже, что стиль AND будет лучше (по крайней мере, для моего набора входных данных 0-500).

Ответ 20

Если a, b и p - целые положительные числа (при условии, что положительный диапазон включает значение 0), тогда выражение (((a + p) <= b) && (a == 0 || a > 1) && (b >= p)) && & ((b - (a + p) == 0) || (b - (a + p) > 1)) может быть сведена до ((a + p) <= b) && (a!= 1) && ((b- (а + р))!= 1)

Позвольте мне продемонстрировать это: В первой части выражения есть условие ((a + p) <= b), что если оцениваемая истина возвращает true, вторая часть: ((b - (a + p) == 0) || (b - (a + p) > 1)). Если верно, что (b >= (a + p)), то (b - (a + p)) должно быть больше или равно 0, нам нужно чтобы убедиться, что (b- (a + p))!= 1. Отложите этот термин на некоторое время и продолжайте.

Теперь мы можем сосредоточить наши усилия на первой части (((a + p) <= b) && (a == 0 || a > 1) && (b >= p)) && & ((B- (а + р))!= 1)

Если a положительно, то оно всегдa >= 0, поэтому мы можем отказаться от теста (a == 0 || a > 1), если пользу ( a!= 1) и уменьшите первую часть выражения до (((a + p) <= b) && (b >= p) && (a!= 1)).

Для следующего шага сокращения вы можете считать, что если b >= (a + p), то, очевидно, b >= p ( a положительна), и выражение можно свести к

((a + p) <= b) && (a!= 1) && ((b- (а + р))!= 1)

Ответ 21

b >= (a+p) && a>=1

even b >= p является избыточным, так как это всегда будет иметь место для a >= 1

Ответ 22

как насчет следующей логики, прокомментируйте это:

((a == 0 || a > 1) && ((b-p) > 1) )

Ответ 23

(((a + p) <= b) && (a == 0 || a > 1) && & (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

1) (a == 0 || a > 1) является (a!= 1)

2) (b >= p) есть (b - p >= 0)

(a + p <= b) есть (b - p >= a), что сильнее, чем (b - p >= 0).

Первое условие сводится к (a!= 1) && (b - p >= a).

3) (b - (a + p) == 0) - (b - a - p == 0) - (b - p == a).

(b - (a + p) > 1) есть (b - a - p > 1) - (b - p > 1 + a).

Так как мы имели (b - p >= a), и мы используем && мы можем сказать, что (b - p >= a) охватывает (b - p == a & b - p > 1 + a).

Следовательно, все условие будет сведено к

(a!= 1 && (b - p >= a))

Там есть темп, чтобы уменьшить его до (b >= p), но это сокращение не будет охватывать запрет b = p + 1, поэтому (a!= 1 && (b - p >= a )) является условием.

Ответ 24

Этот вопрос был довольно удовлетворительно дан уже на практике, но есть один момент, о котором я упоминаю ниже, который я еще не видел, когда кто-либо еще поднимает.

Так как нам сказали, что a >= 0, и первое условие гарантирует, что b - (a + p) >= 0, заключенный в квадрат || тесты могут быть превращены в тесты против неравенства с 1:

(a + p <= b) && (a!= 1) && (b >= p) && (b - a - p!= 1)

Заманчиво удалить проверку (b >= p), которая даст выражение nickf. И это почти наверняка правильное практическое решение. К сожалению, нам нужно больше узнать о проблемной области, прежде чем говорить, безопасно ли это сделать.

Например, если использовать C и 32-битные беззнаковые int для типов a, b и p, рассмотрим случай, когда a = 2 ^ 31 + 7, p = 2 ^ 31 + 5, b = 13. Мы имеем a > 0, (a + p) = 12 < b, но b < п. (Я использую '^' для указания экспоненциальности, а не побитового xor.)

Вероятно, ваши значения не будут приближаться к тем диапазонам, где этот тип переполнения является проблемой, но вы должны проверить это предположение. И если это окажется возможным, добавьте комментарий с этим выражением, объясняющим это, чтобы какой-то усердный оптимизатор будущего не беззаботно удалял тест (b >= p).

Ответ 25

Я чувствую (a!= 1) && & (a + p <= b) && (a + p!= b - 1) несколько яснее. Другой вариант:

int t = b-p; (a!= 1 & a <= t & a!= t-1)

В основном a является либо 0, t, либо находится между 2 и t-2 включительно.

Ответ 26

a!= 1 && ((b == a + p) || (b - p > a + 1))

Ответ 27

(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

так как a >= 0 (положительные целые числа), член (a == 0 || a > 1) всегда истинен

if ((a + p) <= b) тогда (b >= p) истинно, когда a, b, p являются >= 0

поэтому ((a + p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) сводится к

b>=(a+p)

(b - (a + p) == 0) || (b - (a + p) > 1) эквивалентно b >= (a + p)

поэтому все уравнение сводится к

**b>= (a+p)**