spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Was heißt "die größte Zahl"?

Wenn ich dir jetzt einen Algorithmus gebe, was bringt er dir?
Du kannst ja nicht unendlich viele Zahlen damit durchprobieren.
Das müsstest du aber, um mit Sicherheit sagen zu können, dass es keine noch größere Zahl gibt, die zusammensetzbar ist.
Das Problem ist rein mathematisch. Programmieren hilft dir hier nichts, würde ich mal sagen.

http://en.wikipedia.org/wiki/Coin_problem
(mit Google gefunden)

Auch wenn du es vielleicht jetzt schon gelöst hast: Ich habe nochmal darüber nachgedacht. Ein Algorithmus kann sehr wohl helfen, um die Zahl zu bestimmen, denn man muss gar nicht "alle" Zahlen probieren. Wenn A, B, C meine drei "Einheiten" sind und ich eine Zahl N habe, die sich nicht als Summe (Linearkombination) darstellen lässt, dann muss ich nur die nächsten min(A, B, C) Zahlen testen. Wenn diese sich allesamt als Summe darstellen lassen, dann ist N die größte derartige Zahl. Siehe McNugget-Beispiel im Wikipedia-Artikel. Ein solcher Algorithmus, der mir sagt, ob eine Zahl als Summe von gegebenen Zahlen darstellbar ist, fällt mir allerdings momentan nicht ein. (außer Bruteforce)