Algorithmus gesucht!

Sonstiges Theoretisches
1

Hallo!

Es ist eine Hausaufgabe von mir.

Gegeben sind diese Zahlen: 1 2 3 4 5 6 7 8 9

aus diesen Zahlen sollte man 100 ergeben können. Zum Beispiel: 1+2+34-5+67-8+9 = 100.

Schön und gut. Alles lösbar.

Aber ich muss auch ein Programm (in Prolog) schreiben das mir beliebige Sequenzen löst. Nun habe ich aber nicht mal eine Vorstellung, wie das anzugehen wäre. Ich muss ja irgendeine Art Algorithmus im Programm implementieren, wenn ich nicht Brute-Force arbeiten will (was ich unbedingt vermeiden möchte).

Habt ihr irgendwelche Ideen? Es können auch mehrere Algorithmen sein, die per Fallunterscheidung ausgeführt werden. Einzig Brute Force will ich vermeiden.

Grüße

2

Hm. Eine etwas genauere Beschreibung der Bedingungen wäre vielleicht hilfreich. Sind die Eingaben immer einzelne, aufsteigend sortierte Ziffern? Darf man die Reihenfolge der Ziffern beliebig verändern? Kann man nur Zahlen aus den Ziffern bilden oder +/- einfügen? Oder darf man auch andere Rechenoperationen verwenden?

Selbst im einfachsten Fall (aufsteigend sortierte Ziffern, die nur zu Zahlen verbunden und mit +/- verrechnet werden dürfen) würde mir spontan kaum eine Lösung einfallen, die nicht im schlechtesten Fall „degeneriert“: Spätestens, wenn man feststellen muss, DASS es für eine bestimmte Konfiguration keine Lösung gibt (inwieweit auch immer das eintreten kann :confused: müßte man sich überlegen) muss man, um eine Lösungsmöglichkeit definitiv ausschließen zu können, ALLE Kombinationsmöglichkeiten durchprobieren.

Die Frage ist (nicht nur dann, sondern allgemein) ob man Heuristiken verwenden könnte, die ggf. schnell zu Lösungen führen… aber auch da würde mir spontan nichts wirklich „trickreiches“ einfallen…

3

Hallo!

Ja, ich leide auch etwas an Informationsmangel, da aus dem Angabeblatt nicht viel mehr hervorgeht, als ich gepostet habe.
Aber zusammengefasst: Es sei eine beliebige, aufsteigend sortiete Abfolge von Ziffern gegeben. Ich vermute, dass man die Reihenfolge nicht ändern kann. Die Ziffern kann man mit +/- verbinden, oder einfach zu einer Zahl zusammenfassen.

Auch wird im Dunkeln gelassen, wie diese “beliebige Sequenz” aussehen soll. Denn die Zahl, auf die man kommt (z.B. 100) sollte auch beliebig sein, so wie ich das verstehe. Ok. Wie sieht die Folge aus bei 60? 1 2 3 4 5 oder 1 2 3 4 5 6? Und bei 45?

Hier habe die ganze Angabe kopiert. Mich interssiert v.a. Punkt b.

Consider the digits 1 to 9 written in ascending order:
1 2 3 4 5 6 7 8 9
We want to insert the arithmetical operations + and ? between some of the digits such that the
resulting expression evaluates to 100. A possible solution is shown below:
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
(a) Find a solution with only three operations.
(b) Write a Prolog predicate solve sequence/3 that can be used to solve arbitrary sequence
problems. The sequence is given as first argument and the number that must be reached as
second argument.

4

Bei konkreter Prolog-Hilfe wird’s bei mir dünn - meine Prolog-Kenntnisse waren immer nur rudimentär, und sind inzwischen mehr als eingerostet :o
Aber die Aufgabenstellung klingt für mich jetzt so, als ob immer die Folge der Ziffern von 1 bis 9 gegeben ist. Ich würde erstmal versuchen, das mit Brute-Force zu lösen, um überhaupt eine Lösung zu haben. Dann erkennt man vielleicht schon, an welchen Stellen man vielleicht irgendwelche Heuristiken einsetzen kann - ich denke, man könnte vielleicht über die Größe der Zahlen einige Vereinfachungen finden - wenn man die Zahl 100 erreichen muss, und schon 12345 zusammengefasst hat, braucht man sich keine Gedanken mehr darum zu machen, ob man nun +6 oder -6 rechnet - selbst wenn man -6789 rechnen würde, wäre das Ergebnis zu groß. Aber erstens ist sowas in Prolog nicht sooo einfach einzubauen, und zweitens wird dadurch der (gigantische) Suchraum nur unwesentlich verkleinert :confused:

5

Klar, konkret werd ichs dann schon selber implemetieren. Aber ich muss sagen, die Aufgabe entmutig mich immer mehr. Vielleicht werd ich doch mit ner brute-force ähnlichen Methode probieren. Das könnte sich vielleicht ausgehen, trotz des gigantischen Suchraumes.
Wenn man mal Zeuge wurde wie Prolog die 10000 (ja, zehntausendste) Fibonacci-Zahl in 1-2 Zehntel berechnet, würde man meinen, es geht alles.

Bei runden Zahlen ist mir aufgefallen: N - (N-1N-2) - N-3 +/- N-4 +/- N-5

z.B. 60 - 54 - 3 - 2 - 1 = 0. Hier gehts sogar ohne +
oder eben 50 - 54 + 3 + 2 - 1 = 0. Das Problem ist aber, das ich da zwei verschiedene Definitionen von Sequenzen verwende. Und ich sollte mich für eine entscheiden.

6

Das mit den Fibonacci-Zahlen ist wohl weniger ein Problem, wenn man es nicht rekursiv macht - sofern man erstmal die passenden „Datenstrukturen“ für so große Zahlen hat :confused:

Was meinst du mit „verschiedene Definitionen von Sequenzen“? Wie gesagt, es klingt als wäre es immer 1 bis 9. Und die Reihenfolge meinst du wohl nicht, oder?

7

Erstelle zwei Listen: noch nicht verwendete Zahlen und bereits verwendete Zahlen. Speichere in einer Variablen immer die noch fehlende Summe. Lass den Algorithmus dann aus der Menge der noch nicht verwendeten Zahlen die Zahl auswählen, die der fehlenden Summe am nächsten kommt. Verschiebe diese Zahl in die Menge der bereits verwendeten Zahlen und aktualisiere die fehlende Summe. Sollte der Algorithmus irgendwann nur mehr eine Zahl finden, so dass die Wahl dieser Zahl die fehlende Summe übersteigen würde, dann verschiebe die zuletzt verwendete Zahl zurück in die Menge der noch nicht verwendeten Zahlen und suche statt dieser Zahl diejenige Zahl, die der fehlenden Summe am zweitnächsten ist. So hast du eine Systematik in deinem Algorithmus, ohne dass er lediglich primitives Backtracking darstellt. Du musst natürlich auch eine Liste führen, die für jede verwendete Zahl angibt, ob sie erste, zweite, dritte,… Wahl war.

8

Java ist nicht Prolog, und es ist nur der einfache Fall 1…9, aber trotzdem:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class OneToNine {
    public static void main(String[] args) {
        solve(100);
    }

    enum Op {PLUS, MINUS, NOP;
        public String toString() {
            switch (this) {
                case PLUS: return "+";
                case MINUS: return "-";
                case NOP: return "";
                default: throw new AssertionError();
            }
        }
    }

    public static void solve(long total) {
        for(List<Op> list : permutations(8)) {
            Stack<Long> numberStack = new Stack<>();
            long i = 1;
            numberStack.push(i);
            Stack<Op> opStack = new Stack<>();
            String s = "1";
            for(Op op : list) {
                i++;
                switch (op) {
                    case PLUS : case MINUS :
                        numberStack.push(i);
                        s += op.toString() + i;
                        opStack.push(op);
                        break;
                    case NOP :
                        numberStack.push(numberStack.pop() * 10 + i);
                        s += i;
                        break;
                }
            }
            Collections.reverse(numberStack);
            Collections.reverse(opStack);
            long result = numberStack.pop();
            while(! opStack.isEmpty()) {
                if (opStack.pop() == Op.PLUS) {
                    result += numberStack.pop();
                } else {
                    result -= numberStack.pop();
                }
            }
            if (result == total) {
                System.out.println(s);
            }
        }
    }

    private static List<List<Op>> permutations(int n) {
        List<List<Op>> result = new ArrayList<>();
        if (n == 0) {
            result.add(new ArrayList<>());
        } else {
            List<List<Op>> list = permutations(n - 1);
            for(Op op : Op.values()) {
                for(List<Op> subList : list) {
                    List<Op> extendedList = new ArrayList<>(subList);
                    extendedList.add(op);
                    result.add(extendedList);
                }
            }
        }
        return result;
    }
}

Ich bekomme folgende Lösungen:


1+23-4+56+7+8+9
12+3-4+5+67+8+9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
123-4-5-6-7+8-9
123+45-67+8-9
1+23-4+5+6+78-9
12-3-4+5-6+7+89
12+3+4+5-6-7+89
123-45-67+89
123+4-5+67-89
9

kann auch nach 5 Jahren durchaus noch helfen :wink:

10

Ups… Aber ich bin bekennender Zombie-Fan…

11

Pi mal Daumen ist 3^9 nicht viel (2^9 + 2^81^3 + 2^72^3 usw.) Aufgehört werden kann, wenn sum ± (a** concat a[i+1] concat … a[n]) < 100 bzw. > 100 wäre.
Der „Suchraum“ ist einfach winzig.
Ich grabe übrigens auch gerne Leichen aus. :wink: