Zahlenrätsel "Des chiffres et des lettres"

Tranx · Verfasst: Mi 09.01.13 00:55

Eine weitere Einsparung von Rechenzeit kommt m.E. nur noch durch logische Ausschlüsse zustande. Was meine ich damit?

nehmen wir die Zahlen 3 4 5 6 und das Ergebnis 7

Dann wird mit Sicherheit die Anzahl der * als Operatoren nicht allzu häufig sein, da ja schon 3*4 > 7 ist. Und wenn, dann nicht im Zusammenhang mit +, sondern nur mit / und - . Aber das umzusetzen, um Permutationen von vorneherein auszuschließen, sie also garnicht erst zu testen, ist sicher sehr aufwändig.

Denn 283 Millionen Möglichkeiten durchzuchecken, das dauert nun mal.

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Horst_H · Verfasst: Mi 09.01.13 10:13

Hallo,

die Angabe von user profile icon

Mathematiker brachte mich auf die Idee es mal als UPN umzustellen

Zitat:

(a • b)•(c • d)
(a •(b • c)) • d
a • ((b • c) • d)
((a • b) • c) • d
a • (b • (c • d))

Als Ergebnis:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

  (a op1 b) op2 (c op3 d)       a  b  op1 c  d  op3 op2 
  
  (a op1(b op2 c)) op3 d        d  a  b  c op2 op1 op3
  a op1 ((b op2 c) op3 d)       a  d  b  c op2 op3 op1
  ((a op1 b) op2 c) op3 d       d  c  a  b op1 op2 op3
  a op1 (b op2 (c op3  d))      a  b  c  d op3 op2 op1

Nur die Variante mit nicht überlappenden Klammern muss anders gerechnet werden, die folgenden werden alle mit einer Permutation von [a,b,c,d] erfasst.
Vielleicht muss man "nicht überlappenden Klammern" anders formulieren.
Aber sicher lässt sich für diese Fälle ein Algorithmus finden, in wieviele Gruppen zu 2,3 elemtentigen Klammern man einen Term aufspalten kann.

Gruß Horst

Ehemaliges Mitglied Erhaltene Danke: 1

www.mathisfunforum.com/index.php

Mathematiker · Verfasst: Mi 09.01.13 14:44

Hallo,
trotz der vielen Hinweise auf UPN (Danke dafür :flehan:

) habe ich erst einmal meinen Algorithmus weiterentwickelt.

Will ich a • b • c • d berechnen, so gehe ich im Moment so vor, dass ich zuerst für alle Operationen a • b und b • a mit jedem möglichen Paar a,b aus den Ausgangszahlen das Ergebnis ermittle.
Mit dem Ergebnis e verändere ich die Aufgabe zu e • c • d und verfahre erneut so.

Nun sind a • b und b • a für die Addition und die Multiplikation die gleichen Aufgaben. Aus diesem Grund betrachte ich bei + und * nur noch a • b, für alle Paare a,b. Das reduziert den Aufwand noch einmal deutlich.
Da ich zusätzlich bei der Ausgabe einer Lösung Summanden und Faktoren der Größe nach sortiere, erhalte ich jetzt nur noch Lösungen, die nicht nach dem Kommutativgesetz identisch sind. Für das Assoziativgesetz habe ich noch keine Idee.
Insgesamt wird aber die Rechenzeit nochmals geringer und als Lösungen erhält man nur derartige, die wirklich entsprechend dem Kommutativgesetz voneinander verschieden sind.

Die Berechnung der Darstellungen von 1 bis 1800 mit den Ausgangszahlen 2, 3, 5, 7, 11, 13, 17 dauert jetzt nur 204 Sekunden und nicht mehr 25 Minuten.
Ich bin erst einmal zufrieden. Es geht aber bestimmt noch mehr.

hathor hat folgendes geschrieben :

www.mathisfunforum.com/index.php

Verstehe ich leider nicht. Unter dieser Adresse sind sehr viele interessante Text zu finden. Welche meinst Du konkret?

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Mathematiker · Verfasst: Mi 09.01.13 20:30

Hallo,
ich habe jetzt einmal die maximale Anzahl der Tests bei meinem Algorithmus durchgerechnet.

Je Rekursionsstufe werden für n Zahlen genau i(i-1) Paare bei der Subtraktion und Division und i(i-1)/2 bei Addition und Multiplikation getestet; insgesamt also 3i (i-1).
Gesucht wird für n, n-1, ..., 2 Zahlen, d.h. die maximale Testzahl wird

markieren

Quelltext

1:	Produkt 3·i·(i-1) (für i = 2,...,n) = 3^(n-1) n!² / n

Für n = 6, 7, 8 Zahlen sind das 20,9 Millionen, 2,6 Milliarden bzw. 444 Milliarden. Dies sind etwa die Werte bei vollständigem Test aller Permutationen.
Bei einem Testlauf wird dies aber deutlich weniger sein, da jede nicht aufgehende Division die Berechnung beschleunigt. Im günstigsten Fall sind es bei n = 6, 7, 8 Zahlen "nur" 2,7 Millionen, 232 Millionen bzw. 26 Milliarden Tests.

Bisher habe ich im Programm unnötigerweise die rekursiven Rufe bis einschließlich n = 2 durchgeführt. Die Änderung (Revision 7) auf n > 2 ergibt die gleichen Ergebnisse bei Einsparung einer Unmenge bedeutungsloser Aufrufe der Prozeduren.
Im Ergebnis brauche ich jetzt für die Zerlegungen von 1 bis 1800 mit den Zahlen 2, 3, 5, 7, 11, 13, 17 nur noch 60 Sekunden. Das sind gerade einmal 4 % der am Anfang benötigten Zeit. :dance2:

Beste Grüße
Mathematiker

Wichtiger Nachtrag:
Das Programm (8.Revision) enthält jetzt eine 3.Berechnungsmethode, das "Ziele suchen".
Dazu habe ich Martoks hervorragende Idee umgesetzt.

Mit den Ausgangszahlen werden alle möglichen Ergebnisse ermittelt. Liegen sie im Bereich "von" - "bis", erscheinen sie in der Liste.
Für diesen Bereich "von" - "bis" habe ich als untere Grenze 0 festgelegt. Außerdem darf "bis" nur maximal 100000 größer sein als "von"; sonst bekommt die Listbox akute Probleme.

Für mein Standardproblem der 1800 Zerlegungen, s.o., brauche ich jetzt noch 3 Sekunden; 0,2 % der Anfangszeit. Dabei benötigt die Vorbereitung und direkte Ausgabe in die Listbox allein 2 Sekunden.
Aus den 70 Stunden für 1 bis 18920 mit den Ausgangszahlen 2, 3, 5, 7, 11, 13, 17 und 19 sind noch 475 s geworden.
So etwas finde ich toll. :dance2:

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Do 10.01.13 19:13

Hallo,

Wie wäre es statt in 475 Sekunden in 5 ;-)

.
OK ist in integer, aber das ist ja nicht die Bremse.
Ich habe mein Verfahren, bei dem einfach nur die nächste Zahl mit dem vorherigen Ergebnis verknüpft wird, leider noch nicht komplett richtig, denn bei einer Division als letzter Operation kommt 647 div 2 = 323 durch, obwohl der Rest 1 ist. :-(

Aber es ja meist zig Lösungen ( 18619 hat bei mir "nur" 14 Varianten )
Als Beispiel mal eine Ausgabe für 4711 als Zielzahl:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Ergebnis 4711
Auf dem Ausgangsstack stehen
 '7'   5 '6'  19 '5'  11 '4'   7 '3'  17 '2'  13 '1'   3 '0'   2 
Operatoren: * + * - * - /
Dort steht umgeschrieben:
((((((5*19)+11)*7)-17)*13)-3)div 2
Auf dem Stack stehen dann die Zwischenergebnisse und ganz oben das Endergebnis.
 '7'   5 '6'  95 '5' 106 '4' 742 '3' 725 '2'9425 '1'9422 '0'4711

Permutationen 40320
Berechnungen 171.263.844 statt 40320 * 4^7 = 660.602.880 
00:00:05.075
 94.824 Cpu-Takte pro Berechnung

Ich schaue mal, ob ich nicht überlappende Klammern überhaupt einbauen kann.

Gruß Horst
P.S
Ich habe mal spasseshalber die Berechung abgebrochen wenn jedes Ergebnis von 0 bis 18720 mindestens einmal vorkam. Das war in 2,5 Sekunden der Fall, aber die Divisionen muss nochmals genauer untersuchen.

EDIT:
Programm siehe unten

Mathematiker · Verfasst: Do 10.01.13 20:07

Hallo Horst_H,

Horst_H hat folgendes geschrieben :

Ich habe mal spasseshalber die Berechung abgebrochen wenn jedes Ergebnis von 0 bis 18720 mindestens einmal vorkam. Das war in 2,5 Sekunden der Fall, ...

Das klingt wirklich sehr gut und vor allem interessant.
Leider kann ich Deinen Quelltext nicht compilieren. Den Befehl PtrUint kennt mein Delphi 5 nicht.
Mein Hauptproblem ist aber, dass ich die vielen Pointer-Operationen noch nicht verstehe. Wird wohl wieder eine lange Nacht.

In der Revision 9 habe ich "Folge berechnen" entfernt, da die Routine "Ziele suchen" die gleiche Aufgabe wesentlich schneller absolviert. Weitere Änderungen verkürzen die Rechenzeiten noch einmal.
Statt den oben erwähnten 475 s sind es noch 325 s; allerdings nicht mit dem Ergebnis von Horst_H zu vergleichen. Da müsste ich noch viel optimieren. Aber wie? :nixweiss:

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Do 10.01.13 21:47

Hallo,

PtrUint wurde bei fpc eingeführt damit man bei 64 und 32 bit Anwendungen den gleichen Namen einmal Qword das andere Mal Dword nutzen kann.
EDIT, ich habe eine neue Version hochgeladen

Gruß Horst

Mathematiker · Verfasst: Fr 11.01.13 00:14

Horst_H hat folgendes geschrieben :

markieren

Delphi-Quelltext

1:
2:

type
  ptruint = Dword;// 32-Bit

Danke für den Hinweis. Leider kann ich es immer noch nicht compilieren. Bei

markieren

Delphi-Quelltext

1:	while (k >=Low(Perm) ) AND (pDat^[0]> pDat^[1])do

kommt die Meldung "Konstantenausdruck verletzt untere Grenze".
Ich habe versucht, den Text zu verstehen. Kein Chance. Das ist für mich geradezu kryptisch. Dennoch hast Du meine Hochachtung dafür, dass Du solche Programm schreiben kannst.

In der Revision 10 habe ich noch ein paar Änderungen eingefügt. Durch Umlagern der Tests wird es noch etwas schneller.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Fr 11.01.13 00:51

Hallo,

ich hatte diese merkwürdige Handhabung wegen 64-Bit FPC für Linux als schnellste Variante gefunden.
Ich habe jetzt eine Variante die unter 32-Bit genauso schnell ist, ohne das der Compiler rummoppert :-)

Nun im Anhang Programmtext und EXE.
Ja es ist sehr kryptisch ;-)

Wieso dauert eine komplette Berechnung nur 90 CPU-Takte.
Ich benutze immer die vorhergehenden Berechnungen, deren Ergebnisse ja auf dem Stack noch stehen.
So muss nach jeder Berechnung nur die oberste Zahl korrigieren und den neuen Operator darauf anwenden.
tiefe
2,1,0
Zahlen Operatoren
3,2,1 * +
3,(3*2) 6,7
->Ergebnis in Tiefe 0 , dort die 1 aus dem UrStack( Permutation der Zahlen) wieder einsetzen und den nächsten Operator - auf 6 und 1
anwenden.
3, 6, 1 -
3, 6, (6-1) 5

Wie oben schon geschrieben, kann ich nicht alle Rechenmöglichkeiten damit ausführen.

Gruß Horst
EDIT:
Ich möchte eigentlich doch verstanden werden ;-)

....
Die Operatoren auf dem OpStack sind direkt die Adressen auf die entsprechende procedure ADD/SUB/MUL/DIVI

In test(i) wird die eigentliche Berechnung durchgeführt, wobei i die Positon des Operators ist, in anderen Worten die Stacktiefe.

markieren

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:

procedure DoIt(p:tproc); inline;// ohne inline extreme 40 CPU-Takte länger, wer hätte das gedacht
begin
  p; 
// in assembler
//   call  *%eax
//  ret
end;

(* Alternative Version von MUL aber langsamer
procedure MUL;
//Ein Aufruf dauert etwa 6..7 CPU-Takte
var
  i: integer;
begin
  i := TOS-1;
  TOS:= i;
  Stack[i] := Stack[i]*Stack[i+1];
end;;*)

procedure MUL;
//Ein Aufruf dauert etwa 4 CPU-Takte in enger Schleife
var
  i: integer;
  p : tpStackArr;// ^array[0..1] of integer;
begin
  i := TOS;
  dec(i);
  TOS := i;
  p := @Stack[i];
  p^[0] := p^[1]*p^[0];
end;
....
procedure Test(i:integer);

begin
  TOS := i+1;
  // Alle Operatoren von i .. 0 aufrufen
  For I:= i downto 0 do 
    Doit(OpStack[i]);
  // Das Ergbenis der Bechnung  steht dann in Stack[0]
  i := Stack[0];
  //Und entsprechend eintragen und zaehlen
  IF ( i >= Low(Erg)) AND (i <= High(Erg)) then
    begin
    IF Erg[i] = 0  then
      begin
      inc( AnzahlLoesung);//write(AnzahlLoesung:8,#8#8#8#8#8#8#8#8);
      end;
    inc(Erg[i]);
    end;
end;

In TOS= Top Of Stack steht die Position der ersten Zahl, die verarbeitet werden soll, diese ist global.
Und in diesem Spezialfall hier, dass immer 2 Zahlen verarbeitet werden, gibt es n-1 Operatoren, deshalb ist TOS immer i+1.
In der Schleife

markieren

Delphi-Quelltext

1:	For I:= i downto 0 do Doit(OpStack[i]);

ruft das Programm nacheinander die Proceduren direkt auf.Das ist das schöne an stackbasierten Rechnungen, das alle Parameter dort sind und man keine übergeben muss.
Wenn beispielsweise auf OpStack[i] die Adresse der Prozedur MUL ist, dann springt DoIt sofort in die Prozedur MUL.

Berechnete ich immer alles komplett neu, müsste ich, wie bei Testlauf als ersten Aufruf,die Zahlen vom UrStack auf den Stack schreiben ( cop )und dann test(MaxStack-1) aufrufen.
Wenn sich aber nur der Operator der Ebene/Tiefe 0 geändert hat brauche ich nur Zahl 0 neu beschreiben da in Ebene1 noch das Ergebnis der Berechnung bis dort hin steht.

Mit OpRek bestimme ich den aktuellen Operator in der jeweiligen Tiefe.
Ich erhöghe also oprek[0].Wenn die Zahl größer als die Anzahl der Operatoren ist, setzte ich diesen zurück auf 0 und erhöhe bei Tiefe = 0+1.
Dabei werden parallel die richtigen Zahlen auf den Stack geschrieben und der OperandenStack mit den Adressen der Operatoren beschrieben.

Das simuliert eben MAXSTACK-1 verschachtelte For-Schleifen.
Was vielleicht befremdlich wirkt, ist die Namensgebung Stack, denn ich benutze diesen außer beim rechnen selbst nicht immer so. Ich schreibe die Zahlen direkt hinein ohne Push und Pop, das hält mich nur auf ;-)

Ich werde mal testen, wieviele Lösungen ich nicht finde.
18619 gibt es bei mir nur 14 mal aus 2,3,5,7,11,13,17,19

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Fr 11.01.13 15:17

Hallo,

ich habe mal einen Test gemacht, wieviele Lösungen user profile icon

Mathematiker bei seinen Standardzahlen für 18619 findet, wo ich nur 14 Ergebnisse habe.
Seins findet über 200 bei 3,2 Milliarden Rechnungen in 342 Sekunden als abgebrochen habe.
ZiffernUndZahlen

Meine jetztige Überlegung ist nun zusätzlich zu meinem simplen Ansatz, nach Klammern aufzuteilen in 2er Gruppen in denen innnerhalb nur '+','-' gerechnet wird und ausserhalb der Klammer nur '*','/'.
Und dann die Klammern peu a peu zu verbreitern damit ich auch mal mit Catalan Freude bekomme.
Bei acht Zahlen

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

2-2-2-2
3-1-2-2 
1-3-2-2 braucht es wegen der '/'
2-1-3-2
2-3-1-2
2-2-3-1
2-2-1-3
4-2-2
2-4-2
2-2-4
4-1-3
1-4-3
1-3-4
...

Oder gibt es da merkwürdige Hindernisse?

Gruß Horst

Einloggen, um Attachments anzusehen!

Mathematiker · Verfasst: Fr 11.01.13 17:51

Hallo Horst_H,
vielen Dank für den veränderten Quelltext und die Exe.
Ich werde versuchen, Schritt für Schritt, Dein Programm zu verstehen.

Beste Grüße
Mathematiker

Nachtrag, 12.1.:
Ich habe das Programm so verändert, dass beim Aufruf der rekursiven Methoden das Feld nicht mehr kopiert wird. Dadurch wird es erneut etwas schneller, nur leider nicht so viel, wie ich gehofft hatte.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme