Алгоритм поиска 2 самых больших чисел, меньших 2 целых чисел a и b, которые делятся друг на друга

Question

Итак, вот проблема. Даны 2 целых числа с именами a и b:

// Находим 2 самых больших числа, меньше чем a и b, которые делятся друг на друга.

// ввод: а: 102, б: 53 // вывод: (102,51)

// ввод: а: 7, б: 4 // вывод: (6,3)

// ввод: a: 3, b: 2 // вывод: (2,2)

Загвоздка в том, что я не хочу ее перебирать. Я думаю, что это выходит за O (n²).

Вот подпись для метода:

static Tuple<int, int> Analyze(int a, int b)
{
    if (a % b == 0)
        return new Tuple<int, int>(a, b);
    else
        // Here’s where the algorithm kicks in
}

Вот пример реализации:

static Tuple<int, int> Analyze(int left, int right)
{
    if (left % right == 0)
        return new Tuple<int, int>(left, right);
    else
    {
        for (int i = left; i >= right; i--)
        {
            for (int j = right; j >= 0; j--)
                if (i % j == 0)
                    return new Tuple<int, int>(i, j);
                else
                    i--;
        }
    }

    return null;
}

Вот тестовый клиент:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Analyze(102, 53));
        Console.WriteLine(Analyze(6, 4));
        Console.WriteLine(Analyze(3, 2));
    }
}

Очевидно, есть проблемы с моей реализацией, но это неплохо для начинающих. Например, когда я использую 106 и 54 для своих аргументов, если бы я не уменьшил переменную внешнего цикла (я - в блоке else), я бы нашел совпадение со 106 и 53. Вместо этого я нахожу совпадение с 52, что не совсем верно, но относительно близко к желаемому результату. Тем не менее, мой пример реализации намного быстрее, чем грубый принудительный подход, потому что я никогда не буду зацикливаться больше, чем b раз, делая его O (b). Мысли, входы?

Answer 1

Я думаю, что это сработало бы, и было бы довольно просто, если я не запутался, он должен найти самое большое sum(a,b):

static Tuple Analyze(int a, int b)
{
    if (a % b == 0)
        return new Tuple(a, b);
    else {
        // The algorithm starts here.
        // This is fairly easy to implement with tail recursion, but not optimal:
        // There are two cases to worry about:
        //   1) 'b' will never divide into 'a' evenly, but 'b-1' might.
        //   2) 'a' doesn't divide evenly by 'b', but 'a-1' might.
        if (a < b*2) return Analyze(a, b-1);
        else return Analyze(a-1, b);
    }
}

Найти самый большой лексикографически тривиально. Просто цикл от b до 1.

Вы сможете добиться большего успеха, если прыгнете больше чем на один, очевидно. Вот пример в Python (при условии a>b, если это не так, поменять их местами):

>>> def analyze(a, b):
...   if 0 == a%b: return (a,b)          # If b is a factor, return them.
...   if a < b*2: return analyze(a,a/2)  # If b can't factor, adjust 'b' to next.
...   return analyze(a-(a%b),b)          # Otherwise, adjust 'a' to next.
... 
>>> map(lambda p: analyze(*p), [(102, 53), (6, 4), (3,2)])
[(102, 51), (6, 3), (3, 1)]

Answer 2

Посмотрели ли вы статью Wolfram о величайшем общем делителе, и с небольшим гуглом я нашла для вас хороший код Java, который реализует хороший алгоритм GCD, который вы можете изменить для своих целей здесь