Zahl bis n in bis zu k Summanden aufteilen
Hallo,
ich stehe vor einem Problem: ich programmiere aktuell das Spiel "Shut The Box" nach. Vielleicht kennen das welche von euch. Ist zwar nichts sehr bekannt, macht aber durchaus spaß. Probleme bereitet mir aktuell eher der Algorithmus, um die Möglichkeiten durchzurechnen. Natürlich könnte ich erstmalig alle Kombinationen ausrechnen und dann abfragen. Dies ist aber nicht Sinn der Sache. Möglich soll sein, die Würfelzahl und die Felderzahl anzugeben, um so ein bisschen Dynamik und schwierigkeit in das Spiel zu bringen. Aber es geht eben nicht um das Spiel, sondern eher darum, wie man es mathematisch oder programmtechnisch lösen könnte. Bisher habe ich es mit Permutation probiert, was aber eher nicht funktioniert hat oder ich es einfach falsch angewandt habe. Denn im Internet habe ich zu dem Thema auch nichts gefunden.
Um nochmal das Problem konkret zu beschreiben: es sollen alle Kombinationsmöglichkeiten der Summanden aus der Zahl n errechnet werden. Wichtig ist, dass der Summand in einer Liste definiert sein muss und auch nur einmalig ist.
Ich hoffe, jemand kann mir mit meinem mehr oder weniger komplexen Problem helfen :)
Grüße
5 Antworten
Ich weiß zwar nicht hundertprozentig, ob sich dein Problem damit lösen könnte, aber es ist ein in manchen Fällen korrekter Algorithmus, um die Anzahl von Möglichkeiten auszurechnen:
Hier könnte der Binomialkoeffizient helfen. Diese Funktion sagt an, wieviele Möglichkeiten es gibt, wenn man aus einer Menge n eine Menge k heraus nimmt.
Die Formel dafür ist:
(n__ k) = (n!)/((n-k)!*k!) [Hierbei ist n! Die Fakultät von n, das sollte mathematisches Grundwissen eines Informatikers sein, (n__ k) soll nur heißen, dass es in der Schreibweise untereinander geschrieben wird. Hier nochmal ein Bild aus Wikipedia, welche die Formel ordentlich zeigt:
http://upload.wikimedia.org/math/5/b/1/5b1910ee2c949bbe482062ba41ebbf44.png
Wie gesagt, das könnte oder könnte nicht dein Problem lösen, wäre aber ein Denkansatz, wenn du die verschiedenen Möglichkeiten berechnen willst.
Du willst das doch sicher so programmieren, daß der optimale Zug genommen wird, oder?
Also: Durch Herausnahme welcher Kombination von "offenen" Summanden werden die Chancen maximal gehalten, bei nachfolgenden Würfen die Möglichkeit zu behalten, weitere noch "offene" Summanden-Kombinationen entfernen zu können? ...So daß insgesamt die Chance maximiert wird, alle "offenen" Summanden abzubauen.
Liege ich da richtig?
Dann ist das aber doch recht trivial mit Durchprobieren der verfügbaren Summanden (mit backtracing) zu machen.
Ein Permutations-Effekt stellt sich beim Durchprobieren von ganz allein ein. Den muß man nicht irgendwie künstlich erzwingen. Einfach systematisch durchprobieren und fertig! Zumal Du ja nur eine Handvoll Summanden hast - das ist rux-fix über die Bühne!
Dankeschön nochmal im Nachhinein für die Anregung. War mal wieder was einerseits interessantes, andererseits hinreichend leichtes zur Entspannung. http://harryboeck.dyndns.org/Spiele/ShutTheBox/
Sorry, das versteh ich nicht. Ich kenne das Spiel nicht.
Also du hast eine Zahl n gegeben, angenommen 11. Du möchtest jetzt alle Kombinationsmöglichkeiten von Summanden, wobei jeder Summand nur einmal vorkommen darf? Also 2+2+7 ginge nicht, weil die 2 dann doppelt ist? 4 + 7 ginge,.
Was bedeutet der Summand muss in einer Liste definiert sein? Du hast eine Liste von Summanden und was da nicht drin steht, darf nicht vorkommen?
Ist die Reihenfolge wichtig? Also möchtest du sowohl 4+7 als auch 7 + 4 haben oder nur eins davon?
Was ist mit dem k auf der Überschrift, möchtest du n in genau 10 Summanden zerlegen?
Hört sich nach einem Pack- oder Zuschnittsproblem an. Kannste vielleicht zunächst ein heuristisches Verfahren drüber laufen lassen.
Wenn "alle Kombinationsmöglichkeiten der Summanden aus der Zahl n errechnet werden" sollen, wirst Du an Permutationen nicht vorbeikommen?
Nein, ww geht darum, dass der Benutzer entscheiden kann, welche summanden benutzen will