Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Rätsel Implementieren


Bergmann89 - Fr 03.07.09 14:08
Titel: Rätsel Implementieren
HI,

ich habe folgendes Rätsel:

Quelltext
1:
2:
3:
4:
5:
 ab +  ac =  de
 +     +     +
feg + fda = hij
 =     =     =
fhh + fhb = hdd

dabei sollen die Buchstaben a-j so durch Zahlen ersetzt werden das die 6 Rechnungen aufgehen. Und das wollt ich jetzt aus Spaß am Programmieren mal programmiertechnisch umsetzen. Mein Anstatz war 10 verschachtelte Schleifen, die jeweils einen Buchstaben durchzählen, aber das wären dann 10^10 Durchläufe und das dauert zu lange. Was anderes is mir aber bis jetzt net eingefallen, hat jmd von euch ne Idee?

Mfg & Thx Bergmann.


Moderiert von user profile iconNarses: Topic aus VCL (Visual Component Library) verschoben am Fr 03.07.2009 um 14:22


Nersgatt - Fr 03.07.09 14:17

Ich würde die Aufgaben Step-by-Step lösen.
Mache für jeden Buchstaben eine Liste, mit in Frage kommenden Zahlen:
Zu Beginn steht in jeder Liste die Zahlen 0 bis 9.
Jetzt probierst Du mit der ersten Formel (ab + ac = de) alle Möglichkeiten durch. Alle Lösungen, die korrekt sind bleiben stehen. Alle Zahlen, die aufgrund der ersten Formel nicht mehr in Frage kommen können, streichst Du aus den Listen.
Jetzt lässt Du das ganze auf die 2. Formel los, usw.
Wenn Du alle Formeln abgearbeitet hast, hast Du auch alle möglichen Lösungen.


Bergmann89 - Fr 03.07.09 14:29

Hey,

dann hätte ich ja bei der 1. Formel wieder 10^10 Durchläufe und das wären dann auch 100min!
Ich muss irgendwie ausschließen das die Zahlen doppelt vorkommen, also wenn a = 1 dann ist b <> 1!

MfG Bergmann.


Nersgatt - Fr 03.07.09 14:31

user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:

dann hätte ich ja bei der 1. Formel wieder 10^10 Durchläufe

Ne, eben nicht. Du hast nur 10^5 Durchläufe, weil Du nur a-e auswertest. Und für die folgenden Formeln hast Du dann die Möglichkeiten von a-e schon eingeschränkt, dass Du nicht mehr so viele Durchläufe hast.


Oliver Marx - Fr 03.07.09 14:32

Hi,

weitere Lösungsansätze wären Backtracking [http://de.wikipedia.org/wiki/Backtracking] und ILP.


Flamefire - Fr 03.07.09 14:33

nein!
du hast nur abcde-->10^5 durchläufe mit viel weniger rechnungen und abfragen-->viel schneller
und das mit den doppelt vorkommenden kannst du ja auch durch einfache if abfragen ausschließen


Bergmann89 - Fr 03.07.09 15:42

Hey,

habs gelöst. wer sichs ma angucken will ich habs im Anhang...

MfG & Thx Bergmann.


Fiete - Di 07.07.09 10:30

Moin Bergmann89,
Dein Problem habe ich über Permutationen gelöst.
Es werden maximal 3628800(10!) Möglichkeiten einer Liste 0 bis 9 durchprobiert.

Beispiel für die ZifferListe: GCDJ@IEF@@HBBIAJIJAA@HDIAGJEBDCEFEHB, das Symbolrätsel
Beispiel für den OPZustand: /++*-+


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
procedure TKZRL.LoesenClick(Sender: TObject);
  const Alfa='ABCDEFGHIJ';Leer='              ';
  var Nr,Anzahl,Tausch,K,L:Integer;
      Fertig,Fehler:Boolean;
      Index,I:Char;
      Zahl:String;
  begin
   K:=0;
   for Index:='A' to 'J' do
    begin Perm[Index]:=K;inc(K) end;
   for K:=1 to 9 do // Ziffernliste --> Buchstabencode, 9 Zahlen der Länge 4
    begin
     Zahl:='';
     for L:=(K-1)*4+1 to 4*K do
      Zahl:=Zahl+char(ZiffernListe[L]+65);
     Zahlen[K]:=Zahl;
    end;
   ZahlenTest(Fehler,Nr);
   if not Fehler then
    begin
     MessageDlg('die '+IntToStr(Nr)+'-te Zahl enthält einen Fehler!',mtError,[mbOk],0);
     exit;
    end;
   Screen.Cursor:=crHourGlass;
   Anzahl:=1;Index:='J';Fertig:=False;LAnzeige.Clear;
   Rechnung(Fertig);
   while (Index>'A'and not Fertig do
    begin
     Tausch:=Perm['A'];
     for I:='B' to Index do Perm[Pred(I)]:=Perm[I]; // nächste Permutation
     Perm[Index]:=Tausch;
     if Tausch=pos(Index,Alfa)-1 then dec(Index)
     else begin Index:='J';inc(Anzahl);Rechnung(Fertig);end
    end;
   Screen.Cursor:=crDefault;
   LAnzeige.Items.Add(IntToStr(Anzahl)+' Permutationen wurden berechnet!');
   LAnzeige.Items.Add(''); // Leerzeile
   if not Fertig then LAnzeige.Items.Add('PC hat leider keine Lösung gefunden')
   else
    begin
     LAnzeige.Items.Add(Leer+'das Symbolrätsel');
     LAnzeige.Items.Add(''); // Leerzeile
     for K:=1 to 9 do
      for L:=1 to 4 do
       if Zahlen[K,L]='@' then Zahlen[K,L]:=' '// bereinigen der Aufgabe
     LoesungsAusgabe;
     LAnzeige.Items.Add(Leer+'   die Lösung');
     LAnzeige.Items.Add(''); // Leerzeile
     for K:=1 to 9 do
      for L:=1 to 4 do
       if Zahlen[K,L]<>' ' then
        Zahlen[K,L]:=IntToStr(Perm[Zahlen[K,L]])[1]; // Buchstabe --> Ziffer
     LoesungsAusgabe;
    end
  end;

 procedure TKZRL.Rechnung(var Fertig:Boolean);
  var MusterZahl:Array[1..9]of Integer;
      K:Integer;
  begin
   // waagerechte Rechnungen
   for K:=1 to 3 do MusterZahl[K]:=Wert(Zahlen[K]);
   Test(MusterZahl[1],MusterZahl[2],MusterZahl[3],OPZustand[1],Fertig);
   if not Fertig then exit;
   for K:=4 to 6 do MusterZahl[K]:=Wert(Zahlen[K]);
   Test(MusterZahl[4],MusterZahl[5],MusterZahl[6],OPZustand[5],Fertig);
   if not Fertig then exit;
   for K:=7 to 9 do MusterZahl[K]:=Wert(Zahlen[K]);
   Test(MusterZahl[7],MusterZahl[8],MusterZahl[9],OPZustand[6],Fertig);
   if not Fertig then exit;
   for K:=1 to 3 do // senkrechte Rechnungen
    begin
     Test(MusterZahl[K],MusterZahl[K+3],MusterZahl[K+6],OPZustand[K+1],Fertig);
     if not Fertig then exit;
    end;
   Fertig:=True;
  end;

 function TKZRL.Wert(Zahl:String):Integer;
  var K,Faktor,Summe:Integer;
  begin
   Summe:=0;Faktor:=1;
   for K:=4 downto 1 do
    if Zahl[K]<>'@' then
     begin
      Summe:=Summe+Perm[Zahl[K]]*Faktor;
      Faktor:=10*Faktor;
     end;
   Wert:=Summe;
  end;

 procedure TKZRL.Test(L,M,R,Rechenart:Integer;var Erfolg:Boolean);
  begin
   Erfolg:=False;
   case Rechenart of
     1if L+M=R then Erfolg:=True; // +
     2if M+R=L then Erfolg:=True; // -
     3if L*M=R then Erfolg:=True; // *
     4if M*R=L then Erfolg:=True; // /
   end
  end;

Gruß
Fiete


Krischa - Di 07.07.09 10:57

Achtung!! Öffnet nicht das Bild. Es verursacht Augenkrebs.

Aber sonst ist das nicht schlecht gemacht ;)