Решите, удовлетворяет ли число недоопределенному уравнению

Question

Возможно ли теоретически решить, с O (1) пространственно-временной сложностью, является ли известное положительное целое число K решением уравнения

, где a и b - фиксированные положительные целые числа (не кратные другому) и & mu; _i s unknown неотрицательные целые числа, все, кроме конечного числа которых (но не все) равны нулю? Если это невозможно в O (1) пространстве и времени, каковы требования к пространству и времени для наиболее известного алгоритма?

Единственный подход к этой проблеме, который я обнаружил, состоит в том, чтобы заранее перечислить подмножество всех возможных K & zwnj; s, но, конечно, для этого необходимо выбрать верхние значения отсечки M. и N , так что i & le; N и & forall; & mu; _i & le; M . Хуже того, его пространство требует O ( M ^N ), которое, вероятно, настолько велико, что ни один алгоритм поиска не достигает производительности поиска O (1) на реальном оборудовании. У меня плохое предчувствие, что это на самом деле проблема с рюкзаком в скрытом виде, но я еще не уверен в этом, чтобы сдаться.

Я пытаюсь пройти весь путь до O (1) как в пространстве, так и во времени, потому что мне нужно знать, можно ли это сделать в режиме реального времени, во встроенной среде, где практически нет места ни в ЦП, ни в ОЗУ. 1042 *

Мне не нужно знать удовлетворяющий набор & mu; _i значений.

РЕДАКТИРОВАТЬ: Эта функция Python вычисляет установленный объект S таким образом, что K in S истинно, если и только если K является одним из решений вышеприведенного уравнения, учитывая a , b и отсечки M и N , как описано выше.

def compute_set(a, b, M, N):
    ss = [a*i + b for i in xrange(1,N+1)]
    aa = itertools.product(xrange(0,M+1), repeat=N)
    rv = set(map(lambda a: sum(a[i]*ss[i] for i in xrange(N)), aa))
    rv.remove(0)
    return rv

Answer 1

Решить в два этапа.

На этапе 1 вычислить описание набора {(x, y): x, y в Z и ax + by = K}, используя стандартные методы обработки Диофантовы уравнения .Пусть g = gcd (a, b);если g не делит K, нет решений.Вычислите g с помощью расширенного евклидового алгоритма , чтобы решить ax '+ by' = g, а также вычислите g;первое решение (х ', у') * К / г.Другие решения аддитивно связаны целыми числами, кратными (-b / g, a / g).

На этапе 2 вычисляют описание решений (x, y), которые могут быть достигнуты с помощью различных вариантов выбораμ _я .Поскольку K ≥ 0, мы знаем, что y ≥ 1 является необходимым условием.Если n - переменная, то x ≥ 0 и y ≥ 1 - необходимое и достаточное условие (установите µ ₀ = y - 1 и µ _x = 1 и все другие µs для0).

Если n является параметром, то все немного сложнее.Используя результаты этапа 1, найдите решение (x, y) с x ≥ 0 и максимумом y (если такого решения нет, то K не выполнимо).Для этого решения проверьте, x / y ≤ n.

def egcd(A, B):
    """Returns a triple (gcd(A, B), s, t) such that s * A + t * B == gcd(A, B)."""
    a, b, s, t, u, v = A, B, 1, 0, 0, 1
    while True:
        assert s * A + t * B == a
        assert u * A + v * B == b
        if not b:
            break
        q, r = divmod(a, b)
        a, b, s, t, u, v = b, r, u, v, s - q * u, t - q * v
    return a, s, t

def solvable(K, a, b):
    g, s, t = egcd(a, b)
    q, r = divmod(K, g)
    if r:
        return False
    x, y = s * q, t * q
    assert a * x + b * y == K
    d = a // g
    q, r = divmod(y, d)
    if r <= 0:
        q -= 1
        r += d
    assert 0 < r <= d
    x, y = x + q * (b // g), r
    assert a * x + b * y == K
    return x >= y