Оптимальный способ определить, возможно ли достичь пары (c, d), начиная с (a, b)

Question

Каждая пара (a, b) может быть преобразована в (a + b, b) или (a, a + b).

Для данной функции bool isPossible (int a, int b, intc, int d), реализовать логику, которая возвращает истину или ложь в зависимости от того, может ли быть достигнута целевая пара (c, d) через (a, b)

// (a,b) -> (a, a+b)
// (a,b) -> (a+b,b)
// 2,3 -> 2,5 | 5,3 -> 7,5 | 2, 7 | 5, 8 | 8, 3 -> 12, 5 | 7, 12 | 9, 7 | 2, 9 |5, 13|13,8 | 11, 3 | 8, 11
// a,b -> a,a+b | a+b, b -> a, 2a+b | 2a +b , a+b | a+b, a+2b | a+2b, b -> a, 3a + b | 3a + b , 2a +b |

Обновление: добавление моегоРешение здесь. Было бы интересно поискать другие элегантные решения для этого.

bool isPossible(int a,int b,int c,int d) {

    while(c>=a && d>=b) {
        if(a == c && b==d ) {
            return true;
        }
        int temp = c;
        c= c>d?c-d:c;
        d= d>=temp?d-temp:d;
    }
    return false;
}

Обновление: Это решение работает только для положительных значений a и b.

Answer 1

У меня пока нет (математических) доказательств, но эта функция:

static boolean myPossible(int a, int b, int c, int d) {
  // parenthesis not needed, but for better human readability...
  return (c % a == b && d % b == a) || (c % b == a && d % a == b);
}

... возвращает (всегда) те же результаты, что и ваши!

"числовой / грубый тест силы":

public class Test {

    private static final Random RAND = new Random();

    public static void main(String[] args) {

        for (int i = 0; i < 1000000; i++) {
            // temporarily set to 0..1 (corner case)
            int a = RAND.nextInt(1);
            // temporarily set to 0..1 (corner case)
            int b = RAND.nextInt(1);
            int c = RAND.nextInt(10000);
            int d = RAND.nextInt(10000);
            assert (isPossible(a, b, c, d) == myPossible(a, b, c, d));
        }
    }

    static boolean isPossible(int a, int b, int c, int d) {
        while (c >= a && d >= b) {
            c = c > d ? c - d : c;
            d = d >= c ? d - c : d;
            if (a == c && b == d) {
                return true;
            }
        }
        return false;
    }

    static boolean myPossible(int a, int b, int c, int d) {
        return c % a == b && d % b == a || c % b == a && d % a == b;
    }
}

Answer 2

Ваше решение основано на идее, что лучше идти назад, то есть от (c, d) к (a, b).Это потому, что когда вы начинаете с (a, b) и идете вперед, у вас есть две возможности для следующей пары, в то время как когда вы начинаете с (c, d) и идете назад, у вас, очевидно, есть только одна возможность - вам необходимо вычестьнаименьшее значение из наибольшего.

Это действительно верно для случая, когда оба значения a и b являются положительными.В этом случае, a+b>a и a+b>b, и, следовательно, по паре (c,d) легко определить, какой шаг в цепочке преобразований был последним (это зависит от того, c>d или d>c).Однако это рассуждение нарушается, если a или b может быть отрицательным, так как в этом случае вы не знаете, следует ли вычитать c из d или наоборот.Это фундаментальная проблема в вашем подходе, и я не вижу простых способов ее преодоления.

Если мы рассмотрим только случай положительных a и b, то мы можем изменить ваше решение наболее эффективный.

Рассмотрим случай, когда c намного больше, чем d.В этом случае вы будете вычитать d из c много раз, вплоть до того момента, когда новый c станет меньше d.К чему вы прибудете в конце?Очевидно, что (c%d, d).Таким образом, вы можете сделать это за один шаг, придя к коду, очень похожему на евклидов алгоритм для наибольшего общего делителя.

Однако при таком переходе от вычитания к делению по модулю вы, возможно, фактически пропустили необходимую пару (т. Е. (A, b)).Однако это легко исправить, поскольку одно из чисел не изменяется, поэтому мы легко можем определить такую ​​ситуацию.

Код будет выглядеть примерно так (не проверено)

while (c > 0 && d > 0) {  // similar to how Eucledian algorithm is written
    if (c > d) {
        int new_c = c % d;
        if (b == d) {  // we should have seen (a,b) here
            return (a % d == new_c && a >= new_c && a <= c);
        }
        c = new_c;
    } else {
        //  a symmetrical case follows
        ...
    }
} 

Этот код имеет временную сложность O(log(c + d)), в то время как ваш код с вычитаниями работает в O(c+d).

---

Что касается случая, когда a и / или b могут быть отрицательными, этокажется, гораздо более сложная проблема.