Lösungsweg für Denkaufgabe

[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

[himitsu]

Zitat von 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)

Wobei da ja alles implizit erwähnt wurde.

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.