Lösungsweg für Denkaufgabe

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

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

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