Die Suche nach dem kürzesten Term bzw. dem kürzesten Algorithmus in einer gegebenen Sprache (in dem Fall sind die Grundrechenarten diese "Sprache") nennt sich Bestimmung der
Kolmogorov-Komplexität - und die ist nicht berechenbar...
Gut, dann vielleicht etwas anders. Gegeben sind k (nicht notwendigerweise verschiedene) natürliche Zahlen sowie eine zu erreichende Zahl n. Die Aufgabe besteht darin, aus genau diesen k Zahlen die Zahl n zu erzeugen, durch Grundrechenarten und Klammern. Soll heißen, wenn unter den k Zahlen manche mehrfach vorkommen, müssen sie auch genau so oft benutzt werden, wie sie in der Aufgabenstellung vorkommen.
Ich denke, das kommt der Aufgabenstellung von pah am nächsten, wo ja 3, 3, 8, 8 gegeben waren.
Man kann die Aufgabe auch folgendermaßen formulieren. Anfangs ist die Liste der Zahlen, z.B. [3, 3, 8, 8] gegeben. Diese Liste ist nun schrittweise zu verkürzen, wobei jeder Schritt darin besteht, zwei beliebige Zahlen auszuwählen und mit einer der Grundrechenarten zu verknüpfen, und dann beide Zahlen durch das Ergebnis zu ersetzen. Beispiel, wie man damit auf 24 kommt:
- Wähle (/ 8 3): [8/3, 3, 8]
- Wähle (- 3 8/3): [1/3 8]
- Wähle (/ 8 1/3): [24]
Damit hat man die Aufgabe auf endlich viele Möglichkeiten in jedem Schritt reduziert, und man kann nun alle möglichen Schrittfolgen untersuchen. Diese Art der Aufgabe ist eine
Baumsuche, und dafür gibt es verschiedene Algorithmen. Auf die Art und Weise spielen Computer auch Strategiespiele und können eben auch solche Puzzle lösen.
Übrigens braucht es keine beliebige Genauigkeit, weil nur rationale Zahlen vorkommen - mit Zähler und Nenner reichen da zwei Ganzzahlen, um die exakt zu beschreiben. Ich würde mich wundern, wenn es sowas nicht für Perl schon gäbe. Für Python würde ich
SymPy nehmen. Man könnte die Aufgabenstellung auch in
Ludii übersetzen und schauen, wie die dort mitgelieferten AIs sich schlagen.
