Summe der Zahlen eine Sequenz machen

Question

Während gerade die Rugby letzte Nacht Ich habe mich gefragt, ob irgendwelche Noten unmöglich gegeben waren, können Sie nur Punkte in vielen 3, 5 punkten oder 7. Es dauerte nicht lange, um herauszufinden, dass eine beliebige Anzahl von mehr als 4 erreichbar ist. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5, und so weiter.

Die Ausweitung auf dieser Idee für 5, 7 und 9 ergibt sich folgende mögliche Werte:

5,7,9,10,12,14 // and now all numbers are possible.  

Für 7, 9 und 11:

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

Ich habe diese in meinem Kopf, kann jemand empfehlen, einen guten Algorithmus, der die niedrigsten Werte oberhalb derer bestimmen würden alle Werte erreichbar sind eine Reihe von Noten gegeben.

Ich modellierte es wie folgt aus:

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

Dann schauen Sie sich die Liste für eine Folge von mehr als 3 (die kleinstmögliche Punktzahl). Scheint ziemlich unpraktisch und zu langsam für etwas über den trivialen Fall.

Answer 1

Es gibt nur eine unerreichbare Zahl oberhalb der alle Werte erreichbar sind.

Dies ist die Frobenius-Zahl genannt. Siehe: http://en.wikipedia.org/wiki/Frobenius_number

Die Wiki-Seite sollte Links haben für Algorithmen, es zu lösen, zum Beispiel: http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Für 2 Zahlen a, b eine exakte Formel (ab-ab) bekannt ist (die Sie Ihren Suchraum zu reduzieren verwenden könnten) und für 3 Zahlen a, b, ca scharfe untere Grenze (sqrt (3ABC) - abc) und sehr schnelle Algorithmen sind bekannt.

Wenn die Zahlen in arithmetischer Progression sind, dann eine exakte Formel bekannt ist (siehe Wiki). Ich erwähne dies, weil in Ihren Beispielen beziehen sich alle Zahlen in arithmetischen Progression sind.

So Ihre Frage zu beantworten, findet die Frobenius-Zahl und fügen Sie 1 bis es.

Ich hoffe, das hilft.