L'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 nombres entiers positifs.

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

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

.

Modifier

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-3-octets, des éléments zéro ou plus 4 octets et zéro ou plus-5 octets éléments. J'ai reçu un message de 456 octets, et je veux en déterminer la 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 veux faire une première inspection du niveau bibliothèque 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) *

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

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

Supposons que vos chiffres sont 6,7,15. Je vais appeler un numéro 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 sûrement vous serez en mesure d'obtenir n + 6, n + 12, n + 18 - en général, n + 6K pour tout k> = 0. autre côté, si vous ne parvenez pas à obtenir un certain nombre n, alors n-6 est sûrement pas disponible aussi (si vous pouvez obtenir (n-6), puis (n-6) + 6 = n serait disponible), cela signifie n -12, n-18, n-6k ne sont pas disponibles non plus.

Supposons que vous avez déterminé que 15 est disponible, mais 9 n'est pas. Dans notre cas, 15 = 6 * 0 + 7 * 0 + 15 * 1 mais ne sera pas en mesure d'obtenir 9 en aucune façon. Ainsi, par notre raisonnement précédent, 15 + 6K est disponible pour tout k> = 0 et 9-6k pour tout k> = 0 est pas. Si vous avez un nombre qui a divisé par 6 donne 3 en reste (3, 9, 15, 21, ...), vous pouvez répondre rapidement: chiffres <= 9 ne sont pas disponibles, les numéros> = 15 sont

Il suffit de déterminer tous les possibles de la division des restes de 6 (qui est 0,1,2,3,4,5) ce qui est le plus petit nombre qui est disponible. (I venons de montrer que ce numéro pour le reste 3 est 15).

Comment faire: Créer un graphe dont les sommets sont 0,1,2,3,4,5. Pour tous les nombres k que vous êtes donné (7,15 - on fait abstraction 6) ajoute un bord de x à (x + k) 6. mod Give it poids (x + k) div 6. Utilisez l'algorithme de Dijkstra en utilisant 0 comme le noeud initial. Les distances trouvées par l'algorithme seront exactement ces chiffres que nous cherchons.

Dans notre cas (6,7,15) le numéro 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 plus court chemin de 0 à 3 a un bord - son poids est égal à 2. Ainsi, 6 * 2 + 3 = 15 est le plus petit nombre qui donne 3 en tant que reste. 6 * 1 + 3 = 9 ne sont pas disponibles (bien, nous avons vérifié que précédemment à la main).

Et quelle est la connexion à des expressions régulières? Eh bien, chaque expression régulière a un automate fini équivalent, et je construit un d'entre eux.

Ce problème, avec plusieurs requêtes autorisées, est apparu sur la Olympiade polonaise et je traduit la solution. Maintenant, si vous entendez maintenant une personne disant la science informatique n'est pas utile pour les programmeurs réels, le coup de poing dans le visage.

Answer 2

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

Donc, une partie de votre algorithme trouverait le GCF ({n1, n2, ...}) voir alors si elle est un facteur de m. Dans le cas contraire, aucune solution existe. Cela ne montre pas pleinement qu'une solution existe, mais il peut rapidement vous montrer qu'il n'y en a, ce qui est toujours utile.

Answer 3

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 programmation linéaire problème. Malheureusement pour vous, le cas général de résoudre un tel système avec est NP-complet . Cependant, il existe de nombreux algorithmes qui le résoudre pour vous.

Answer 4

Ceci est lié à la Frobenius problème de pièce , qui n'a pas été résolu pour n > 3.

Answer 5

Une approche par la 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 cela n'a pas de sens, car il a besoin de travailler immédiatement. Dans la demande de OPi probablement utiliser une sorte de hachage, mais son approche semble intéressant.

Answer 6

Voici quelque chose sur le 2 numéro de dossier. Je ne l'ai pas encore compris comment elle échelle:

Compte tenu de 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)

En gros, cela fonctionne parce que, si vous assumez 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 nombres entiers compris entre [(x-1) (y-1), (x-1) y], que tous les nombres entiers compris entre (x-1) (y- 1) et (x-1) y-1 avaient été exprimées précédemment.

1. GCD (x, y). Si c est pas un multiple, return false.
2. si GCD (x, y)> 1, diviser x, y, c par GCD
3. Si c> (x-1) (y-1), le retour true
4. la force brute Else

Et pour la force brute:

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

Answer 7

Peut-être l'information suivante est hors de propos, car 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 3*n1 + 4*n2 + 5*n3 somme, pour les entiers non négatifs n1, n2, n3, alors la réponse est « oui », K> = 3.

de Rosen manuel bien connu Mathématiques discrètes et ses applications , p. 287 de la sixième édition, prouve que « tout montant d'affranchissement de 12 cents ou plus peut être formé en utilisant seulement 4 cents et 5 cents timbres, » par induction.

L'étape de base est que l'affranchissement de 12 cents peut être formé avec 3 timbres quatre cents.

L'étape d'induction considère que si P (k) est vrai à l'aide de quatre timbres cent, alors simplement remplacer un timbre de quatre cent avec un timbre de cinq cents pour montrer que P (k + 1) est vrai. Si P (k) est vrai en utilisant pas de timbres à quatre cent, alors, parce que k> = 12, nous avons besoin d'au moins 3 timbres cinq cents pour former notre somme, et 3 timbres cinq cent peuvent être remplacés par des 4 quatre cent timbres pour obtenir k + 1.

Pour étendre la solution ci-dessus pour ce problème, il faut juste considérer que quelques cas.