Algorithme pour déterminer l'existence en solution de valeurs non négatives pour l'équation linéaire diophantienne

Selon ce , si le plus grand facteur commun de {n1, n2, n3, ...} n'est pas un diviseur de m, puis vous n'avez pas de solution. Cette page montre un exemple de just {n1, n2} mais il s'étend à de plus grands systèmes. Le nouveau problème est d'é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 trouve le gcf({n1,n2,...}), puis voir si il est un facteur de m. Si c' n'est-ce pas, alors aucune solution n'existe. Cela ne montre pas pleinement qu'une solution existe, mais cela peut rapidement vous montrer qu'il n'y en a pas, ce qui est encore utile.

on dirait que vous parlez d'un système d'inégalités entier contraintes. 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 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 des contraintes entières est NP-complète . Cependant, il existe de nombreux algorithmes qui le résoudront pour vous.

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

Une force brute approche (pseudo-code):

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'aurait aucun sens, car cela doit fonctionner immédiatement. Dans L'application de L'OP j'utiliserais probablement une sorte de hachage, mais son approche semble intéressante.

voici quelque chose sur l'affaire des 2 nombres. Je n'ai pas encore trouvé comment le dimensionner:

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

fondamentalement, 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 certain multiple positif de x, vous pouvez atteindre tous les entiers entre [(x-1)(y-1) (x-1)y], comme tous les nombres entiers compris entre (x-1)(y-1) et (x-1)y-1 a été exprimé précédemment.

1. PGCD(x,y). Si c n'est pas un multiple, retournez false.
2. si GCD(x,y) > 1, diviser x, y, c par GCD
3. If c > (x-1) (y-1), return true
4. d'Autre force brute

et pour la force brute:

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

peut-être que l'information suivante n'est pas pertinente, parce qu'elle ne gère pas la situation générale, mais...

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

Rosen bien connu des manuels scolaires Mathématiques Discrètes et de 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 cents 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 à quatre cents, il suffit de remplacer un timbre à quatre cents par un timbre à cinq cents pour montrer que P(k+1) est vrai. SI P (k) est vrai en n'utilisant pas de timbres de quatre cents, alors, parce que k>=12, nous avons besoin d'au moins 3,5 cents les timbres pour former notre Somme, et 3 timbres de cinq cents peuvent être remplacés par 4 timbres de quatre cents pour atteindre k+1.

pour étendre la solution ci-dessus pour ce problème nécessite juste de considérer quelques cas supplémentaires.