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

Question

Один для математиков. Это произошло в офисе, и мы хотим посмотреть, кто может предложить более оптимизированную версию.

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

Редактировать : все данные являются положительными целыми числами

Редактировать : лучше == рефакторинг для простоты

Answer 1

// 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);

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

Поскольку целые числа без знака, (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.

Answer 5

Проверено с a, b, p от 0 до 10000:

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

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

Answer 6

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

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

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

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

Например, если вы используете C и 32-битные беззнаковые целые для типов a, b и p, рассмотрите случай, когда a = 2 ^ 31 + 7, p = 2 ^ 31 + 5, b = 13. У нас a> 0, (a + p) = 12 Возможно, ваши значения не будут приближаться к диапазонам, в которых возникает переполнение такого рода, но вы должны проверить это предположение. И если это оказывается возможным, добавьте комментарий с этим выражением, объясняющим это, чтобы какой-то ревностный будущий оптимизатор небрежно не удалил тест (b> = p).

Answer 7

((((a + p) <= b) && (a == 0 || a> 1) && (b> = p)) && ((b - (a + p) == 0) || (б - (а + р)> 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 - р> 1 + а).

Следовательно, все состояние будет уменьшено до

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

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

Answer 8

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

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

Answer 9

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

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

Answer 10

Если 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) </strong> && ((b- (a + p))! = 1)

Позвольте мне продемонстрировать это: В первой части выражения есть условие ((a + p) <= b) </strong>, что если значение 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- (a + p))! = 1)

Если 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) </strong> && ((b- (a + p))! = 1)