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 :stupid:

[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:

Zitat von x000x (Beitrag 1150467)

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.

[patti]

Zitat:

Zitat von QuickAndDirty (Beitrag 1150459)

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) :wink:

[x000x]

Zitat:

Zitat von BUG (Beitrag 1150476)

• welche Zahlen sind erlaubt

• Ganzzahlen

[EDIT]Wobei Zahlen ja gar nicht eingesetzt werden sollen[/EDIT]

Zitat:

Zitat von BUG (Beitrag 1150476)

• welche Operatoren sind erlaubt

• Die vier Grundrechenarten: + - * /

Zitat:

Zitat von BUG (Beitrag 1150476)

• was ist die Operatorenrangfolge

• Punkt vor Strich
• Klammersetzung ist nicht erlaubt

[sx2008]

Zitat:

Zitat von x000x (Beitrag 1150467)

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.

[Popov]

Einfach geht nicht, trotz Brute Force, denn das kleine Beispiel ist zwar ok, beachtet aber kein Punkt vor Strich. Deshalb führt es nicht zum Erfolg. Letztendlich kommt man um einem Mathparser der die Komplettformel richtig berechnet nicht herum.

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
  function r(x, y: Double; z: Char): Double;
  begin
    case z of
    '+': Result := x + y;
    '-': Result := x - y;
    '*': Result := x * y;
    '/': Result := x / y;
    else
      Result := x;
    end;
  end;

const
  o = '+-*/';
var
  a, b, c, d: Char;
begin
  repeat
    a := o[Random(4) + 1];
    b := o[Random(4) + 1];
    c := o[Random(4) + 1];
    d := o[Random(4) + 1];
  until r(r(r(r(7, 5, a), 3, b), 8, c), 4, d) = 31;

  ShowMessage(a+b+c+d);
end; //7   5   3   8   4 = 31

[ConnorMcLeod]

Mir würde da eine Systematik anstatt des <Random> besser gefallen ;-)

[Popov]

a.) ist letztendlich egal, denn irgendwann kommt alles dran
b.) wäre mehr Schreibarbeit im Quellcode gewesen ;)

[Valle]

Zitat:

Zitat von Popov (Beitrag 1150499)

Einfach geht nicht, trotz Brute Force, denn das kleine Beispiel ist zwar ok, beachtet aber kein Punkt vor Strich. Deshalb führt es nicht zum Erfolg. Letztendlich kommt man um einem Mathparser der die Komplettformel richtig berechnet nicht herum.

Delphi ist dafür auch wirklich nicht geeignet.

Prolog auch nicht, mMn. Lösung in Python, hat ca. 2 Minuten gedauert.

Code:

e = 31
s = ["7.0",  "5.0",  "3.0",  "8.0",  "4.0"]
o = [" + ", " - ", " * ", " / "]

for a in o:
    for b in o:
        for c in o:
            for d in o:
                t = s[0] + a + s[1] + b + s[2] + c + s[3] + d + s[4]
                if eval(t) == e:
                    print t.replace(".0", "") + " = " + str(e)

Liebe Grüße,
Valentin

[himitsu]

Zitat:

Zitat von BUG (Beitrag 1150476)

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) :wink:

Wobei da ja alles implizit erwähnt wurde. :angle2:

Zitat:

welche Zahlen sind erlaubt

Die sind doch vorgegeben, samt ihrer Reihenfolge

Zitat:

welche Operatoren sind erlaubt

+ - * / wäre ja normal
Wenn du hart drauf bist, dann kannst'e es auch gerne mit Potenzen und Wurzeln rumspielen und noch ein zusätzliches - (negieren) der Werte

Zitat:

was ist die Operatorenrangfolge

Normale Matheregeln, wenn nix anderes erwähnt ist?
Und da nur die Operatoren fehlen, sind alle Klammern vorhanden, bzw. es gibt keine.



Theoretisch müßte man doch den Formelparser der neuen XE2-LiveBindings nutzen können?

[Amateurprofi]

Ich hab mal was zusammengefrickelt.
Etwas umständlich das Ganze, weil ich den größten Teil aus einem Parserprogramm übernommen habe.
Es scheint aber zu funktionieren und auch mit angemessener Laufzeit.

Wie gehts?
1) In das Editfeld die Aufgabe eingeben, wie in #1 gezeigt, also z.B. 7 5 3 8 4 = 31
2) Start klicken.