Lösungsweg für Denkaufgabe

[x000x]

Moin moin,

bei folgender Aufgabe sind die Operatoren zwischen den Zahlen so zu setzen, dass sich eine mathematisch korrekte Lösung ergibt:

Code:

7   5   3   8   4 = 31

Die Lösung ist mir bekannt. Ich habe sie durch durchprobieren rausgefunden.
Meine Frage ist nun, gibt es hier oder besser allgemein für diese Art von Aufgaben einen Algorithmus um auf die Lösung zu kommen?

[Furtbichler]

"brute force" wäre ein Ansatz. aka "alles durchprobieren"

[Popov]

Mit der Aufgabe hat mich mal mein Kollege eines morgens überrascht. Er hat nur 3,5 Minuten dafür gebraucht, hielt sich deshalb für klug. Ich habe 30 Sekunden gebraucht. Und was habe ich davon? Er hat heute meinen Job

[QuickAndDirty]

Ja Bruteforce! Und ich würde es NICHT mit Delphi machen sondern mit Prolog.

[x000x]

Hm schade, ich war der Meinung, dass es hierbei einen mathemetischen "Trick" gibt.

[Gustav.R]

[OT]

Ist 9live nicht Pleite gegangen?

[/OT]

[Popov]

Zitat von x000x:

Hm schade, ich war der Meinung, dass es hierbei einen mathemetischen "Trick" gibt.

Theoretisch gibt es bei dieser Aufgabe 256 Möglichkeiten. Praktisch läuft es auf weniger hinaus, da man hier irgendwie die Richtung erahnen kann. Wenn man die 8 und die 4 sieht und dann die Lösung 31 und denkt, dass 8 x 4 = 32 sind, und das im Kopf so erst stehen läßt (kann natürlich auch ein falsche Weg sein), dann reduzieren sich die Möglichkeiten. Dann kommen zuerst die Strichrechnungen 7 + 5 + 3 und 7 + 5 - 3 und dann 7 - 5 - 3. Und plötzlich sieht man die -1 und die 32 und die 31 vor dem geistigen Auge, so dass der Rest sich geradezu aufdrängt.

Ist natürlich auch etwas Glück dabei gleich am Anfang schon mal richtig gelegen zu haben.

[sx2008]

Zitat von x000x:

ich war der Meinung, dass es hierbei einen mathemetischen "Trick" gibt.

Es geht nur Brute Force; man könnte aber darauf achten dass zuerst wahrscheinliche Kombinationen von Operatoren getestet werden um möglichst schnell eine Lösung zu finden.
Zwei oder mehr gleiche Operatoren hintereinander würde ich als unwahrscheinlich bezeichnen.
Die Reihenfolge wie ein Operator getestet wird hängt also vom Vorgängeroperator ab.

Delphi-Quellcode:

function CalcNextOperators(previousOp:char):string;
begin
  case preOp of
    '+': Result := '-*/+';
    '-': Result := '+*/-';
    '*': Result := '+-/*';
    '/': Result := '+-*/;
  else
    Result := '+-*/';
  end;
end;

Ausserdem kann man Divisionen ausschliesen bei denen ein ganzzahliger Rest übrigbleiben würde.
Jede Division, die man ausschliesen kann, reduziert die Anzahl der Tests um den Faktor 3/4.
Bei deinem Beispiel wäre nur 8 /4 möglich; also kann man 3 Divisionen ausschliesen.

[patti]

Zitat von QuickAndDirty:

Ja Bruteforce! Und ich würde es NICHT mit Delphi machen sondern mit Prolog.

Die Lösung in Prolog würde mich aus gegebenem Anlass (schreibe Ende März Klausur in "Grundlagen der Logik und Logikprogrammierung" und bin bisher leider alles andere als fit in Prolog...) tatsächlich interessieren. Wie würdest du das implementieren?

[BUG]

Um sich das Problem genauer anzuschauen, fehlen einige Informationen:

• welche Zahlen sind erlaubt
• welche Operatoren sind erlaubt
• was ist die Operatorenrangfolge

Das Problem sieht imho (<- hab aber keine Ahnung) schwer aus, vielleicht schafft es ja jemand zu zeigen, das es NP-vollständig ist (oder eben nicht)