algorithme pour déterminer une solution non-négatives des valeurs existance pour l'équation diophantienne linéaire

Question

Je cherche une méthode pour déterminer s'il y a une solution aux équations telles que: 3n1 + 4n2 + 5n3 = 456, où n1, n2, n3 sont des entiers positifs.

Ou plus général: sont là zéro ou entiers positifs n1, n2, n3 ... qui permet de résoudre l'équation k1n1 + k2n2 + k3n3 ... = m où k1, k2, k3 ... et m sont des entiers positifs connus.

Je n'ai pas besoin de trouver une solution - juste pour déterminer si une solution existe.

Edit:

En ce qui concerne l'utilisation pratique de cet algorithme:

Dans une bibliothèque de communication, je veux décider si un message donné est valide en fonction de sa taille, avant de manipuler le message. Par exemple: Je sais qu'un message contient zéro ou plusieurs éléments de 3 octets, zéro ou plusieurs éléments de 4 octets et zéro ou plusieurs éléments de 5 octets. J'ai reçu un message de 456 octets, et je veux déterminer sa validité avant d'inspecter davantage son contenu. Bien sûr, l'en-tête du message contient le nombre d'éléments de chaque type, mais je souhaite effectuer une première inspection au niveau de la bibliothèque de communication en passant quelque chose comme pair<MsgType,vector<3,4,5>>.

Answer 1

Vous vous demandez si l'expression régulière

(xxx | xxxx | xxxxx) *

matchs xx ... x, où x se produit 456 fois.

Voici une solution dans O (n + a^2), où a est le plus petit des nombres sur le côté gauche (dans ce cas 3).

Supposons que vos numéros soient 6,7,15. Je vais appeler un nombre exprimable sous la forme 6x + 7y + 15z "disponible". Vous devez vérifier si un nombre donné est disponible.

Si vous êtes en mesure d'obtenir un certain nombre n, alors vous serez sûrement capable d'obtenir n + 6, n + 12, n + 18 - en général, n + 6k pour tout k> = 0. Sur le de l'autre côté, si vous ne parvenez pas à obtenir un certain nombre n, alors n-6 n'est certainement pas disponible aussi (si vous pouviez obtenir (n-6), alors (n-6) + 6 = n serait disponible), cela signifie n-12, n-18, n-6k ne sont pas disponibles non plus. Supposons que vous ayez déterminé que 15 est disponible mais que 9 ne l'est pas. Dans notre cas, 15 = 6 * 0 + 7 * 0 + 15 * 1 mais ne pourra en aucun cas en obtenir 9. Donc, par notre raisonnement précédent, 15 + 6k est disponible pour tout k> = 0 et 9-6k pour tout k> = 0 ne l'est pas. Si vous avez un nombre divisé par 6 donne 3 comme reste (3, 9, 15, 21, ...), vous pouvez répondre rapidement: les nombres < = 9 ne sont pas disponibles, les nombres> = 15 sont.

Il suffit de déterminer pour tous les restes de division possibles de 6 (c'est-à-dire 0,1,2,3,4,5) quel est le plus petit nombre disponible. (J'ai juste montré que ce nombre pour le reste 3 est 15). Comment faire: Créez un graphe avec les sommets 0,1,2,3,4,5. Pour tous les nombres k qui vous sont donnés (7,15 - nous ne tenons pas compte de 6) ajoutez une arête de x à (x + k) mod 6. Donnez-lui du poids (x + k) div 6. Utilisez Dijkstra's algorithm en utilisant 0 comme noeud initial . Les distances trouvées par l'algorithme seront exactement les nombres que nous recherchons.

Dans notre cas (6,7,15) le nombre 7 donne lieu à 0 -> 1 (poids 1), 1 -> 2 (poids 1), 2 -> 3 (poids 1), ... , 5 -> 0 (poids 1) et le nombre 15 donne 0 -> 3 (poids 2), 1 -> 4 (poids 2), ..., 5 -> 1 (poids 2). Le chemin le plus court de 0 à 3 a un bord - son poids est 2.Donc 6 * 2 + 3 = 15 est le plus petit nombre qui donne 3 comme reste. 6 * 1 + 3 = 9 n'est pas disponible (eh bien, nous avons vérifié cela précédemment à la main).

Et quelle est la connexion aux expressions régulières? Eh bien, chaque expression régulière a un automate fini équivalent, et j'en ai construit un.

Ce problème, avec plusieurs requêtes autorisées, est apparu sur le Polish Olympiad et j'ai traduit la solution. Maintenant, si vous entendez maintenant une personne dire que l'informatique n'est pas utile pour de vrais programmeurs, frappez-le en face.

Answer 2

On dirait que vous parlez d'un système d'inégalités avec des contraintes entières. La réalité est que vous résolvez pour ce système:

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

Et la contrainte supplémentaire que n1, n2, n3 sont des nombres entiers. C'est un problème linear programming. Malheureusement pour vous, le cas général de la résolution d'un tel système avec integer constraints is NP-complete. Cependant, il existe de nombreux algorithmes qui le résoudront pour vous.

Answer 3

Une approche force brute (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 

Voir aussi http://mail.python.org/pipermail/python-list/2000-April/031714.html

EDIT: Dans une bibliothèque de communication ce serait pas de sens, car il a besoin de travailler immédiatement. Dans l'application OP, j'utiliserais probablement une sorte de hash, mais son approche semble intéressante.

Answer 4

Selon this, si le plus grand facteur commun de {n1, n2, n3, ...} n'est pas un diviseur de m alors vous n'avez pas de solution. Cette page montre un exemple de juste {n1, n2} mais elle s'étend aux plus grands systèmes. Le nouveau problème consiste à écrire un algorithme pour trouver le plus grand facteur commun, mais c'est trivial à la lumière du problème original.

Donc, une partie de votre algorithme trouverait le gcf ({n1, n2, ...}) alors voir si c'est un facteur de m. Si ce n'est pas le cas, aucune solution n'existe. Cela ne montre pas complètement qu'une solution existe, mais elle peut rapidement vous montrer qu'il n'en existe aucune, ce qui est toujours utile.

Answer 5

Voici quelque chose sur le cas des 2 chiffres.Je ne l'ai pas encore compris comment l'échelle il:

Vu 2 entiers premiers x et y, il existe des nombres entiers positifs a et b tels que ax+by=c pour tous c>=(x-1)(y-1)

Fondamentalement, cela fonctionne parce que, si vous supposons x<y, vous pouvez exprimer tous les entiers mod x avec (0, y, 2y, 3y, ..., (x-1) y). Maintenant, en ajoutant un multiple positif de x, vous pouvez atteindre tous les entiers entre [(x-1) (y-1), (x-1) y], comme tous les entiers entre (x-1) (y- 1) et (x-1) y-1 avaient été exprimés précédemment.

1. GCD (x, y). Si c n'est pas un multiple, renvoyez false.
2. si GCD (x, y)> 1, diviser x, y, c par GCD
3. Si c> (x-1) (y-1), le rendement vrai
4. vigueur Autres brute

Et pour la force brute:

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

Answer 6

Ceci est lié à la Frobenius coin problem, qui n'a pas été résolu pour n> 3.

Answer 7

Peut-être l'information suivante est hors de propos, parce qu'il ne gère pas la situation générale, mais ...

Si le problème est de déterminer si un nombre entier positif donné K peut être formé comme une somme 3*n1 + 4*n2 + 5*n3, pour entiers positifs n1, n2, n3, alors la réponse est "oui", K> = 3.

Rosen bien connu de manuel mathématiques discrètes et ses applications, p. 287 de la sixième édition, prouve que "chaque montant d'affranchissement de 12 cents ou plus peut être formé en utilisant seulement des timbres de 4 et 5 cents", en utilisant l'induction. L'étape de base est que l'affranchissement de 12 cents peut être formé avec 3 timbres de quatre cents. L'étape d'induction considère que si P (k) est vrai en utilisant des timbres de quatre cents, il suffit de substituer un timbre de quatre cents par un timbre de cinq cents pour montrer que P (k + 1) est vrai. Si P (k) est vrai sans timbres de quatre cents, alors, parce que k> = 12, nous avons besoin d'au moins 3 timbres de cinq cents pour former notre somme, et 3 timbres de cinq cents peuvent être remplacés par 4 cent timbres pour atteindre k + 1.

Pour étendre la solution ci-dessus à ce problème, il suffit de ne prendre en compte que quelques cas supplémentaires.