Wie kann ich feststellen, ob eine bestimmte Nummer aus einer Reihe von Zahlen zusammengesetzt werden kann?

9

Also habe ich eine ganze Zahl, z.B. 1234567890 und eine gegebene Menge von Zahlen, z.B. {4, 7, 18, 32, 57, 68}

Die Frage ist, ob 1234567890 aus den angegebenen Zahlen zusammengesetzt werden kann (Sie können eine Zahl mehr als einmal verwenden, und Sie müssen nicht alle verwenden). Im obigen Fall ist eine Lösung:
38580246 * 32 + 1 * 18

(Muss keine spezifische Lösung geben, nur wenn es möglich ist)

Meine Idee wäre, alle Lösungen auszuprobieren. Zum Beispiel würde ich versuchen, 1 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 4 und 2 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 8
3 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 12
.....
308 641 972 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 1234567888
308 641 973 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 1234567892 == & gt; übertrifft 0 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 7
1 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 11
2 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 15 usw. und so weiter ...

Hier ist mein Code in c #:

%Vor%

Der Code funktioniert gut (soweit ich weiß), ist aber viel zu langsam. Es dauert etwa 3 Sekunden, um das Beispiel zu lösen, und aus 100 Zahlen können 10000 Nummern entstehen.

    
Tamás F 22.12.2015, 21:42
quelle

3 Antworten

3

Ich habe eine rekursive Lösung. Es löst das ursprüngliche Problem des OP in etwa 0,005 Sekunden (auf meinem Rechner) und teilt Ihnen die Berechnungen mit.

%Vor%

Grundsätzlich geht es durch jede Zahl, um zu sehen, ob es eine mögliche Lösung "unter" gibt, die den aktuellen Quotienten und die aktuelle Nummer angibt. Wenn nicht, subtrahiert es 1 vom Quotienten und versucht es erneut. Dies geschieht so lange, bis alle Optionen für diese Nummer ausgeschöpft sind und dann zur nächsten Nummer weitergegangen ist, falls verfügbar. Wenn alle Zahlen erschöpft sind, gibt es keine Lösung.

    
Trent Sartain 22.12.2015, 23:54
quelle
0

Haben Sie nicht die Mittel, um die Lösung zu testen, aber Folgendes sollte genügen.

Gegeben eine Zielnummer target und eine Menge numbers gültiger Zahlen:

%Vor%

Das Erstellen von n von decomposition ist ziemlich einfach.

    
InBetween 22.12.2015 22:31
quelle
-1

Sie könnten immer versuchen, die Modulo-Funktion in Verbindung mit LINQ-Ausdrücken zu verwenden, um das Problem zu lösen.

Sie hätten eine Liste und eine laufende Modulo-Variable, um zu verfolgen, wo Sie sich in Ihrer Iteration befinden. Verwenden Sie dann einfach Rekursion, um zu bestimmen, ob Sie die Bedingungen erfüllen oder nicht.

Ein Beispiel wäre das folgende:

%Vor%     
JustTryingToHelp 22.12.2015 22:58
quelle

Tags und Links