Algoritmo para determinar a existência de solução não negativa para a equação linear da diofantina

Question

Estou procurando um método para determinar se há uma solução para equações como:3n1+4n2+5n3 = 456, Onde n1, n2, n3 são inteiros positivos.

Ou mais geral: existem zero ou positivo Inteiros n1, n2, n3... que resolve a equação K1N1+K2N2+K3N3 ... = M Onde K1, K2, K3... e m são conhecidos inteiros positivos.

Não preciso encontrar uma solução - apenas para determinar se existe uma solução.

Editar:

Com relação ao uso prático deste algoritmo:

Em uma biblioteca de comunicação, quero decidir se uma determinada mensagem é válida de acordo com seu tamanho, antes de lidar com a mensagem. Por exemplo: eu sei que uma mensagem contém elementos zero ou mais de 3 bytes, elementos zero ou mais 4-bytes e elementos zero ou mais 5-bytes. Recebi uma mensagem de 456 bytes e quero determinar sua validade antes de inspecionar ainda mais seu conteúdo. É claro que o cabeçalho da mensagem contém o número de elementos de cada tipo, mas eu quero fazer uma primeira inspeção no nível da biblioteca de comunicação, passando algo como pair<MsgType,vector<3,4,5>>.

Answer 1

Você está perguntando se a expressão regular

(xxx | xxxx | xxxxx)*

Combina xx ... x, onde x ocorre 456 vezes.

Aqui está uma solução em O (n+a^2), onde A é o menor dos números no lado esquerdo (neste caso 3).

Suponha que seus números sejam 6,7,15. Chamarei um número expresso no formulário 6x+7y+15z "disponível". Você deve verificar se um determinado número está disponível.

Se você puder obter algum número n, certamente poderá obter n+6, n+12, n+18 - em geral, n+6k para todos k> = 0. do outro lado, se Você não pode obter algum número n, então o N-6 certamente não está disponível também (se você pudesse obter (n-6), então (n-6)+6 = n estaria disponível), isso significa N-12, N-18, N-6K também não estão disponíveis.

Suponha que você tenha determinado que 15 está disponível, mas 9 não é. No nosso caso, 15 = 6*0+7*0+15*1, mas não será capaz de obter 9 de forma alguma. Portanto, pelo nosso raciocínio anterior, 15+6k está disponível para todos os k> = 0 e 9-6k para todos k> = 0 não. Se você tem algum número dividido por 6, fornece 3 como restante (3, 9, 15, 21, ...), você pode responder rapidamente: os números <= 9 não estão disponíveis, números> = 15 são.

É suficiente determinar para todos os restos possíveis da divisão em 6 (ou seja, 0,1,2,3,4,5) qual é o menor número disponível. (Acabei de mostrar que esse número para o restante 3 é 15).

Como fazer: Crie um gráfico com vértices 0,1,2,3,4,5. Para todos os números k que você recebe (7,15 - desconsideramos 6) Adicione uma borda de x a (x + k) mod 6. Dê peso (x + k) div 6. Use Algoritmo de Dijkstra usando 0 como o nó inicial. As distâncias encontradas pelo algoritmo serão exatamente os números que estamos procurando.

No nosso caso (6,7,15), o número 7 dá origem a 0 -> 1 (Peso 1), 1 -> 2 (Peso 1), 2 -> 3 (Peso 1), ..., 5 -> 0 (peso 1) e o número 15 dá 0 -> 3 (peso 2), 1 -> 4 (peso 2), ..., 5 -> 1 (peso 2). O caminho mais curto de 0 a 3 tem uma borda - seu peso é 2. Então 6*2 + 3 = 15 é o menor número que dá 3 como restante. 6*1 + 3 = 9 não está disponível (bem, verificamos isso anteriormente manualmente).

E qual é a conexão com expressões regulares? Bem, toda expressão regular tem um autômato finito equivalente, e eu construí um deles.

Esse problema, com várias consultas permitidas, apareceu no Olimpíada polonesa e eu traduzi a solução. Agora, se você ouvir agora uma pessoa dizendo que a ciência da computação não é útil para programadores reais, soce -o na cara.

Answer 2

De acordo com isto, se o maior fator comum de {n1, n2, n3, ...} não for um divisor de m, então você não terá solução. Esta página mostra um exemplo de apenas {n1, n2}, mas se estende a sistemas maiores. O novo problema é escrever um algoritmo para encontrar o maior fator comum, mas isso é trivial à luz do problema original.

Portanto, parte do seu algoritmo encontraria o GCF ({n1, n2, ...}), então veja se é um fator de m. Se não for, não existe solução. Isso não mostra completamente que existe uma solução, mas pode mostrar rapidamente que não existe, o que ainda é útil.

Answer 3

Parece que você está falando de um sistema de desigualdades com restrições inteiras. A realidade é que você está resolvendo para este sistema:

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

E a restrição adicional de que N1, N2, N3 são inteiros. Aquilo é um programação linear problema. Infelizmente para você, o caso geral de resolver esse sistema com Restrições inteiras são NP-Preparado. No entanto, existem muitos algoritmos que o resolverão para você.

Answer 4

Isso está relacionado ao Problema da moeda de Frobenius, que não foi resolvido para n> 3.

Answer 5

Uma abordagem de força bruta (pseudocode):

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

Veja também http://mail.python.org/pipermail/python-list/2000-april/031714.html

EDITAR: Em uma biblioteca de comunicações, isso não faria sentido, pois precisa funcionar imediatamente. No aplicativo do OP, eu provavelmente usaria algum tipo de hash, mas sua abordagem parece interessante.

Answer 6

Aqui está algo no caso de 2 números. Ainda não descobri como escalá -lo:

Dados 2 números inteiros relativamente primos x e y, existem números inteiros positivos a e b tais que ax+by=c para todos c>=(x-1)(y-1)

Basicamente, isso funciona porque, se você assumir x<y, você pode expressar todos os números inteiros mod x com (0, y, 2y, 3y, ..., (x-1) y). Agora, adicionando um múltiplo positivo de x, você pode alcançar todos os números inteiros entre [(x-1) (y-1), (x-1) y], como todos os números inteiros entre (x-1) (y- 1) e (X-1) Y-1 foi expresso anteriormente.

1. GCD (x, y). Se C não for um múltiplo, retorne falsa.
2. Se GCD (x, y)> 1, divida x, y, c por gcd
3. Se c> (x-1) (y-1), retorne verdadeiro
4. Outra força bruta

E para a força bruta:

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Answer 7

Talvez a informação a seguir seja irrelevante, porque não lida com a situação geral, mas ...

Se o problema é determinar se um determinado número inteiro positivo K pode ser formado como uma soma 3*n1 + 4*n2 + 5*n3, para números inteiros não negativos n1, n2, n3, então a resposta é "sim", para k> = 3.

Livro conhecido de Rosen Matemática discreta e suas aplicações, p. 287 da sexta edição, prova que "toda quantidade de postagem de 12 centavos ou mais pode ser formada usando carimbos de apenas 4 e 5 centavos", usando a indução.

A etapa base é que a postagem de 12 centavos pode ser formada com 3 carimbos de quatro centavos.

A etapa de indução considera que, se p (k) for verdadeiro usando carimbos de quatro centavos, basta substituir um carimbo de quatro centavos por um carimbo de cinco centavos para mostrar que P (K+1) é verdadeiro. Se p (k) for verdadeiro usando carimbos de quatro centavos, então, porque k> = 12, precisamos de pelo menos 3 carimbos de cinco centavos para formar nossa soma e 3 carimbos de cinco centavos podem ser substituídos por 4 quatro centavos Carimbos para alcançar K+1.

Estender a solução acima para esse problema requer apenas considerar apenas mais alguns casos.