Algoritmo per determinare i non-valori negativi-soluzione esistenza lineare equazione diofantea

Question

Sto cercando un metodo per determinare se c'è una soluzione per le equazioni come:3n1+4n2+5n3=456, dove n1,n2,n3 sono interi positivi.

O, più in generale:ci sono zero o positivo interi n1,n2,n3...che risolve l'equazione k1n1+k2n2+k3n3...=m dove k1,k2,k3...e m sono noti i numeri interi positivi.

Non ho bisogno di trovare una soluzione solo per determinare se una soluzione esiste.

Edit:

Riguardo l'uso pratico di questo algoritmo:

In una libreria di comunicazione, voglio decidere se un determinato messaggio è valido in base alla sua dimensione, prima di maneggiare il messaggio.Per esempio:So che un messaggio contiene zero o più di 3 byte elementi, zero o più di 4 byte elementi, e zero o più di 5 byte elementi.Ho ricevuto un messaggio di 456 byte, e voglio determinare la validità prima di continuare a ispezionare il suo contenuto.Naturalmente l'intestazione del messaggio contiene il numero di elementi di ogni tipo, ma voglio fare una prima ispezione nella comunicazione-biblioteca di livello, passando qualcosa di simile pair<MsgType,vector<3,4,5>>.

Answer 1

Si sta chiedendo se l'espressione regolare

(xxx | xxxx | xxxxx) *

partite xx ... x, dove x verifica 456 volte.

Ecco una soluzione in O (n + a ^ 2), dove a è il più piccolo dei numeri sul lato sinistro (in questo caso 3).

Supponiamo che i numeri sono 6,7,15. Chiamerò un numero esprimibili in forma 6x + 7y + 15z "disponibile". Tu sei per controllare se un dato numero è disponibile.

Se siete in grado di ottenere un certo numero n, allora sicuramente si sarà in grado di ottenere n + 6, n + 12, n + 18 - in generale, n + 6K per ogni k> = 0. D'altra lato, se non si riesce a ottenere un certo numero n, allora n-6 non è sicuramente disponibile anche (se si potrebbe ottenere (n-6), poi (n-6) + 6 = n sarebbe disponibile), questo significa che n -12, n-18, n-6K non sono disponibili né.

Si supponga di aver determinato che il 15 è disponibile, ma non è 9. Nel nostro caso, 15 = 6 * 0 + 7 * 0 + 15 * 1 ma non sarà in grado di ottenere 9 in alcun modo. Quindi, dal nostro ragionamento precedente, 15 + 6K è disponibile per ogni k> = 0 e 9-6k per ogni k> = 0 non è. Se hai qualche numero che diviso per 6 dà 3 come resto (3, 9, 15, 21, ...) è possibile rispondere rapidamente: i numeri <= 9 non sono disponibili, i numeri> = 15 sono

E 'sufficiente per determinare tutte le possibili resti della divisione per 6 (che è 0,1,2,3,4,5) qual è il numero più piccolo che è disponibile. (Ho appena mostrato che questo numero per il resto 3 è 15).

Come fare: creare un grafico con vertici 0,1,2,3,4,5. Per tutti i numeri k che si è data (7,15 - si prescinde 6) Aggiungi un vantaggio da x a (x + k) 6. mod Dategli peso (x + k) div 6. Utilizzare di Dijkstra utilizzando 0 come nodo iniziale. Le distanze trovati dall'algoritmo sarà esattamente quei numeri che stiamo cercando.

Nel nostro caso (6,7,15) il numero 7 dà luogo a 0 -> 1 (peso 1), 1 -> 2 (peso 1), 2 -> 3 (peso 1), ..., 5 -> 0 (peso 1) e il numero 15 dà 0 -> 3 (peso 2), 1 -> 4 (peso 2), ..., 5 -> 1 (peso 2). Il percorso più breve da 0 a 3 ha un bordo - il suo peso è 2. Quindi 6 * 2 + 3 = 15 è il numero più piccolo che dà 3 come resto. 6 * 1 + 3 = 9 non è disponibile (bene, abbiamo verificato che in precedenza a mano).

E qual è il collegamento con le espressioni regolari? Bene, ogni espressione regolare ha un automa a stati finiti equivalente, e ho costruito uno di loro.

Il problema, con più query autorizzati, apparso sul polacco Olimpiade e ho tradotto la soluzione. Ora, se si sente ora una persona dicendo informatica non è utile per i programmatori reali, lui un pugno in faccia.

Answer 2

questo , se il più grande fattore comune {n1, n2, n3, ...} non è un divisore di m allora non hai soluzione. Questa pagina mostra un esempio di {n1, n2} ma si estende a sistemi più grandi. Il nuovo problema sta scrivendo un algoritmo per trovare il più grande fattore comune, ma che è banale alla luce del problema originale.

Quindi, parte del vostro algoritmo avrebbe trovato il GCF ({n1, n2, ...}) poi vedere se si tratta di un fattore pari a m. Se non lo è, allora non esistono soluzioni. Questo non dimostra pienamente che esiste una soluzione, ma può rapidamente dimostrare che non esiste, che è ancora utile.

Answer 3

Sembra che si sta parlando di un sistema di disequazioni con vincoli interi. La realtà è che stai risolvendo per questo sistema:

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

E il vincolo aggiuntivo che n1, n2, n3 sono interi. Questo è un lineare programmazione problema. Purtroppo per voi, il caso generale di risolvere un tale sistema con è NP-completo . Tuttavia, ci sono molti algoritmi che risolverà per voi.

Answer 4

Questo è legato alla Frobenius problema della moneta , che non è stato risolto per n > 3.

Answer 5

Un approccio a forza bruta (pseudocodice):

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

Si veda anche http://mail.python.org /pipermail/python-list/2000-April/031714.html

Modifica In una libreria di comunicazione questo non avrebbe alcun senso, dal momento che ha bisogno di lavorare immediatamente. In applicazione del PO avrei probabilmente utilizzare una sorta di hash, ma il suo approccio sembra interessante.

Answer 6

Ecco qualcosa sul 2 numero di caso.Non ho capito ancora come scala:

2 relativamente primi numeri interi x e y, esistono interi positivi a e b tali che ax+by=c per tutti c>=(x-1)(y-1)

Fondamentalmente, questo funziona perché, se si assume x<y, puoi esprimere tutti i numeri interi mod x (0, y, 2y, 3y, ..., (x-1)y).Ora, con l'aggiunta di alcune positive più di x, è possibile raggiungere tutti i numeri interi compresi tra [(x-1)(y-1),(x-1)y], come tutti i numeri interi compresi tra (x-1)(y-1) (x-1)y-1 era stato espresso in precedenza.

1. GCD(x,y).Se c non è un di più, restituisce false.
2. se GCD(x,y) > 1, dividere x,y,c da GCD
3. Se c > (x-1)(y-1), restituisce true
4. Il resto della forza bruta

E per la forza bruta:

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

Answer 7

Forse le seguenti informazioni è irrilevante, in quanto non gestisce la situazione generale, ma ...

Se il problema è quello di determinare se un determinato numero intero positivo K può essere formato come un 3*n1 + 4*n2 + 5*n3 somma, per i numeri interi non negativi n1, n2, n3, allora la risposta è "sì", per K> = 3.

ben noto libro di testo di Rosen Matematica Discreta e le sue applicazioni , p. 287 della sesta edizione, dimostra che "ogni importo delle spese di spedizione di 12 centesimi o più può essere formato utilizzando appena 4 centesimi e 5 cent francobolli," utilizzando l'induzione.

Il passo base è che l'affrancatura di 12 centesimi può essere formato con 3 francobolli quattro cent.

Il passo di induzione ritiene che se P (k) è vero utilizzando Stamp quattro centesimi, poi semplicemente sostituire un francobollo quattro centesimi con un bollo cinque centesimi per mostrare che P (k + 1) è vera. Se P (k) è vero non usando Stamp quattro centesimi, allora, poiché k> = 12, che necessita di almeno 3 Stamp cinque centesimi per formare nostra somma, e 3 francobolli cinque centesimi possono essere sostituiti con 4 quattro cent Stamp per ottenere k + 1.

Per estendere la soluzione di cui sopra per questo problema richiede solo considerando solo un paio di casi.