Autor Beitrag
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 06.01.13 11:31 
Hallo,
ich habe wieder einmal ein Problem, dass ich zum einen sehr interessant finde, zum anderen mir aber auch schlaflose Nächte bereitet hat.
Bekannt wurde es unter dem Namen "Des chiffres et des lettres" aus einer Spielshow des französischen Fernsehens. Mittlerweile ist es auch in anderen Ländern populär geworden. In den USA gibt es z.B. T-Shirts mit der Aufschrift
chiffre

Die Aufgabe ist, aus einer Menge gegebener Zahlen durch schrittweise Addition, Subtraktion, Multiplikation und Division eine Zielzahl zu ermitteln. Dabei darf und muss jede gegebene Zahl und jedes Zwischenergebnis genau einmal verwendet werden!
Beispiel: Aus den Zahlen 1 bis 6 ist die 278 zu konstruieren
4 · 5 = 20
3 + 20 = 23
23 · 6 = 138
1 + 138 = 139
139 · 2 = 278
Als einzelne Gleichung ergibt sich damit ((3 + 4 · 5) · 6 + 1) · 2 = 278.
Im Allgemeinen existieren entweder mehrere Lösungen oder aber gar keine. Aus den Zahlen n = 4, 5, 6, 7, 8 kann z = 29 zum Beispiel nicht konstruiert werden.

Meine Umsetzung als Programm nutzt vier Routinen, die sich gegenseitig rekursiv aufrufen. Elegant ist das nicht und vor allem für mehrere Ausgangszahlen wird es ziemlich langsam.
Schön wäre es, wenn jemand von Euch eine bessere Idee hätte.

Im Programm werden 4 bis 8 Ausgangszahlen betrachtet. Die möglichen Operationen Addition, ... können ausgewählt werden.
Mit dem Schalter "Problem lösen" werden alle möglichen Lösungen gesucht. Über den Schalter "Folge berechnen" wird beginnend bei der eingegebenen Zielzahl jeweils 1 Lösung ermittelt, die Zielzahl erhöht, erneut gesucht usw. bis eine Zielzahl ohne Lösung gefunden wird.

Beste Grüße
Mathematiker

Rev 1: Algorithmus korrigiert und Folgenberechnung vorerst entfernt.
Rev 2: Ein weiterer Fehler ist korrigiert. Es wurden nicht alle gefundenen Lösungen ausgegeben. Jetzt müsste es korrekt sein.
Rev 3: Die Folgenberechnung ist wieder möglich.
Rev 4: Die berechneten Ergebnisse können in einer Textdatei gespeichert werden.
Rev 5: Die Tests und damit auch die Rechenzeit sind deutlich auf etwa 25% gekürzt.
Rev 6: Es werden nur noch Ergebnisse angezeigt, die nach dem Kommutativgesetz voneinander verschieden sind.
Rev 7: Weitere deutliche Beschleunigung der Berechnung durch Reduktion der Rekursionsaufrufe.
Rev 8: Mit einer 3.Berechnung können nun alle möglichen Zielzahlen in einem festgelegten Bereich ermittelt werden. Besonders schnell!
Rev 9: "Folge berechnen" ist entfernt, da die Routine "Ziele suchen" die gleiche Aufgabe wesentlich schneller absolviert. Weitere Änderungen verkürzen die Rechenzeiten noch einmal.
Rev 10: Weitere Änderungen, vor allem der Tests.
Rev 11: Fehlerhafte Version 10 korrigiert.
Rev 12: Beim Aufruf der rekursiven Methoden wird kein Feld mehr direkt übergeben, d.h. wieder etwas schneller.
Einloggen, um Attachments anzusehen!
_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein


Zuletzt bearbeitet von Mathematiker am Sa 12.01.13 09:51, insgesamt 14-mal bearbeitet

Für diesen Beitrag haben gedankt: kaufmax
Mr_Emre_D
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 114
Erhaltene Danke: 14



BeitragVerfasst: So 06.01.13 20:36 
Ich würds auch per Bruteforce lösen:

Die Zahlen permutieren und bei jedem Perumationsschritt alle Kombinationen für die Rechenopeartionen ermitteln - den Wert evaluieren und zwischenspeichern.
Letzendlich würde ich dann diejenigen ausgeben, die gleich "Zielzahl" sind.

Hmm... es ist aber ein interessantes Problem.
Gibts eig. schon (ordentlich) mathematische Ansätze zu diesem Problem?
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 06.01.13 20:48 
Hallo,
im Endeffekt läuft es bei mir ja auch mit Bruteforce. Und das dauert eben, gerade wenn es dann 7 oder 8 Ausgangszahlen sind.
Als Beispiel: Die Berechnung der Zerlegungen von 1 bis 18920 mit den Ausgangszahlen 2, 3, 5, 7, 11, 13, 17 und 19 benötigte auf meinem 2,6 GHz-PC über 70 Stunden.
In englischsprachigen Ländern wurde das Problem unter dem Namen "Letters and Numbers" (oder umgedreht) bekannt, zuerst in Australien, später in den USA.
user profile iconMr_Emre_D hat folgendes geschrieben Zum zitierten Posting springen:
Gibts eig. schon (ordentlich) mathematische Ansätze zu diesem Problem?

Trotz ausführlicher Netzsuche habe ich noch nichts gefunden. Leider.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Moderator
Beiträge: 3657
Erhaltene Danke: 600

Win XP x86, Win 8.1 x64
Lazarus Snapshot; Delphi 7,2007,XE; PHP (PHPEdit,PhpStorm); JS; Java(Eclipse)
BeitragVerfasst: So 06.01.13 22:04 
Kurze Regelfrage... was ist mit Nicht-Ganzen und negativen Zwischenergebnissen? Und Zwischenergebnissen, die gleich Zahlen sind die schon im Pool sind (ist [2,3,6]->12 als 2*3,6+6,12 möglich)?
Und dann wäre da ja noch das Problem der vielfachen äquivalenten Lösungen. Da waren wir ja schonmal beim Gleichungen vereinfachen ;)

Ansonsten: würde das stimmen? Die Rechnungen sind jeweils von rechts nach links zu lesen, das war grad einfacher programmiert :roll: Ist ein dummes Bruteforce, also auch keine neue Idee.
ausblenden volle Höhe 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:
pool is   1,2,3,4
target   9
found  3--6,-3*2,1-4
found  3--6,2*-3,1-4
found  6--3,2*3,1-4
found  6--3,3*2,1-4
found  5+4,6-1,2*3
found  4+5,6-1,2*3
found  10-1,6+4,2*3
found  4--5,1-6,2*3
found  6--3,1-4,2*3
found  10-1,4+6,2*3
found  3+6,4-1,2*3
found  6+3,4-1,2*3
found  5+4,6-1,3*2
found  4+5,6-1,3*2
found  10-1,6+4,3*2
found  4--5,1-6,3*2
found  6--3,1-4,3*2
found  10-1,4+6,3*2
found  3+6,4-1,3*2
found  6+3,4-1,3*2
found  11-2,12-1,3*4
found  10-1,12-2,3*4
found  12-3,1+2,3*4
found  12-3,2+1,3*4
found  11-2,12-1,4*3
found  10-1,12-2,4*3
found  12-3,1+2,4*3
found  12-3,2+1,4*3
done


PS: mit Abbruch nach erstem Fund:
ausblenden Quelltext
1:
2:
3:
4:
5:
pool is  1,2,3,4,5,6
target  278
found  139*2,138+1,23*6,20+3,4*5
done
took  78631  ms

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 06.01.13 22:32 
Hallo Martok,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Kurze Regelfrage... was ist mit Nicht-Ganzen und negativen Zwischenergebnissen? Und Zwischenergebnissen, die gleich Zahlen sind die schon im Pool sind (ist [2,3,6]->12 als 2*3,6+6,12 möglich)?

Negative Zwischenergebnisse sind zugelassen, gebrochene aber nicht, d.h. die Division muss "aufgehen". Tritt ein Zwischenergebnis auf, dass evtl. einer der Zahlen entspricht, so wird trotzdem mit diesem einfach weitergerechnet.

user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Und dann wäre da ja noch das Problem der vielfachen äquivalenten Lösungen. Da waren wir ja schonmal beim Gleichungen vereinfachen ;)

Äquivalente Lösungen habe ich im Moment als weitere gezählt. Das Problem mit der Vereinfachung verfolgt uns scheinbar immer wieder.
Ich hatte schon einmal die Idee aus dem Term einen UPN-Term zu machen. Vielleicht könnte man dann einfacher äquivalente ausfiltern. Allerdings schrecke ich davor noch zurück. Ich mag UPN einfach nicht.

Für Dein Beispel pool is 1,2,3,4 / target 9 hat Du (ohne Division) 28 Lösungen, ich nur 20, also sind mir wohl ein paar abhanden gekommen.
Für 1,2,3,4,5,6 und target 278 braucht mein Programm nur rund 1 Sekunde für das Testen aller Möglichkeiten.

Beste Grüße
Mathematiker

Nachtrag: Ich habe gerade gesehen, dass mir alle Lösungen fehlen, die mit einer Subtraktion mit einem negativen Ergebnis beginnen.
Nachtrag 2: Ich habe die Lösungen doch, nur in der Form (4-1)+(2*3). Einige bei Dir verschiedene, sind bei mir ausgeblendet.
Nachtrag 3: Mein Algorithmus hat einen entscheidenden Fehler. Es werden nicht alle Möglichkeiten getestet. Sehr ärgerlich.
Nachtrag 4: Ich habe (hoffe ich) den Fehler im Algorithmus entfernt. Vorerst gibt's auch keine Folgenberechnung mehr. Die machte den Quelltext unübersichtlich.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Marc.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1876
Erhaltene Danke: 129

Win 8.1, Xubuntu 15.10

BeitragVerfasst: Mo 07.01.13 13:20 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Negative Zwischenergebnisse sind zugelassen, gebrochene aber nicht, d.h. die Division muss "aufgehen".

Damit kann man die Frage in dem Bild in Deinem ersten Post ganz klar mit nein beantworten. Jedenfalls in dem von Dir erlaubten Zahlenraum.
(Ansonsten ginge 8/(3-5/2)=16)

Für einen Algorithmus müsste man wohl erst einmal die Existenz einer Lösung nachweisen bzw. voraussetzen können. Allein das ist wohl schon schwierig genug. :nixweiss:

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 07.01.13 13:27 
Hallo Marc.,
user profile iconMarc. hat folgendes geschrieben Zum zitierten Posting springen:
Damit kann man die Frage in dem Bild in Deinem ersten Post ganz klar mit nein beantworten.

Wow, ich habe bisher noch nicht geprüft, ob dass auf dem T-Shirt möglich ist. :autsch:
Du hast vollkommen recht. In der Original-Spielshow musste die Division aber aufgehen. Obwohl es mit meinen Kenntnissen der französischen Sprache nicht so gut aussieht, habe ich mir auf "TV 5" die Sendung ab und an mal angesehen.

Lässt man gebrochene Zwischenergebnisse zu, heißt das für das Programm, dass der Algorithmus deutlich schwerer wird.

In der Revision 2 habe ich einen blöden Fehler beseitigt. Es wurden nicht alle gefundenen Lösungen ausgegeben. Jetzt müsste es korrekt sein.

Beste Grüße
Mathematiker

Nachtrag: Das T-Shirt ist wohl für richtige Nerds. :mrgreen: Ein "normaler" US-Amerikaner wird die Aufgabenstellung gar nicht verstehen, geschweige denn eine Lösung finden.
Lässt man sogar Kommas zu, geht auch: 8 * (3 - (,5 * 2)) = 16.
Interessant ist Nerds-Gifts.

Nachtrag 2: In der Revision 3 ist die Folgenberechnung wieder möglich.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: Mo 07.01.13 16:35 
Also, bei 6 Zahlen gibt es oft schon 3000 - mehr als 6000 Lösungen. Das ist schon gewaltig. Obwohl wahrscheinlich die rel. Lösungshäufigkeit nicht ansteigt. Aber mit Permutationen hab ich das nicht so.

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 07.01.13 17:01 
Hallo Tranx,
user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Also, bei 6 Zahlen gibt es oft schon 3000 - mehr als 6000 Lösungen. Das ist schon gewaltig.

Das finde ich auch überraschend.
Interessanter finde ich aber die Berechnung von mindestens einer Lösung für aufsteigende Zielwerte (Folge berechnen). Ich habe gerade für die Ausgangszahlen 2, 3, 5, 7, 11, 13, 17 für alle Zahlen von 1 bis 1800 wenigstens eine Darstellung ermitteln lassen. Knapp 25 Minuten Rechenzeit sind ziemlich viel.

Beste Grüße
Mathematiker

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


Zuletzt bearbeitet von Mathematiker am Sa 09.02.13 22:06, insgesamt 1-mal bearbeitet
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Moderator
Beiträge: 3657
Erhaltene Danke: 600

Win XP x86, Win 8.1 x64
Lazarus Snapshot; Delphi 7,2007,XE; PHP (PHPEdit,PhpStorm); JS; Java(Eclipse)
BeitragVerfasst: Mo 07.01.13 17:24 
Das ist natürlich der Vorteil von meiner Lösung. Da werden alle möglichen Ergebnisse berechnet, die sich mit dem Pool erreichen lassen, das wird dann nur nach dem target gesiebt. Kann man natürlich dann andersrum rangehen und von dieser Liste wiederum min/max nehmen, dann weißt du, dass du alle erzeugbaren Werte dazwischen kennst ;)

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 07.01.13 18:46 
Hallo Martok,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Das ist natürlich der Vorteil von meiner Lösung. Da werden alle möglichen Ergebnisse berechnet, die sich mit dem Pool erreichen lassen, das wird dann nur nach dem target gesiebt.

Klingt sehr gut. Die Lösung würde mich sehr interessieren. :D

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1586
Erhaltene Danke: 231


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Mo 07.01.13 22:18 
Wenn "Brute Force" und Permutierung Grundlagen der Lösung sind, ist dann ein möglichst schneller Permutationsalgorithmus vorteilhaft? M.E. ja!
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 07.01.13 22:57 
Hallo Delphi-Laie,
user profile iconDelphi-Laie hat folgendes geschrieben Zum zitierten Posting springen:
... ist dann ein möglichst schneller Permutationsalgorithmus vorteilhaft?

Du hast schon recht und wenn ich es richtig verstanden habe, nutzt Martok auch alle Permutationen der Zahlen, Operationen und Klammermöglichkeiten.

Dies sind bei n Zahlen und alle Operationen ziemlich viele Möglichkeiten. Nach meiner Abschätzung gleich n! (n-1)^4 C(n), wobei C(n) = (2n)! / ((n+1)! n!) die n.te Catalansche Zahl ist, welche die Anzahl der Klammermöglichkeiten eines Berechnungsterms mit n Zahlen angibt.
n! sind die Permutationen der n Zahlen und (n-1)^4 die Anzahl der Operationsmöglichkeiten zwischen den Zahlen.
Für 6 Zahlen sind das 59,4 Millionen, für 7 Zahlen schon 2,8 Milliarden und für 8 Zahlen 138 Milliarden Möglichkeiten; bei einer einzigen Suche!

Den größten Zeitbedarf hat in meinem Programm die Überprüfung, ob das gewünschte Resultat erzeugt wird. Und das braucht seine Zeit. Deshalb hoffe ich ja, dass jemand eine vielleicht bessere Idee hat.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1643
Erhaltene Danke: 236

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Di 08.01.13 06:13 
Hallo,

Warum nicht einen UPN- Parser.
Ein Stack mit den vorhandenen n Zahlen und einen mit den n-1 möglichen operatoren , die immer auf zwei Elemente wirken.
Den Zahlen Stack mit allen Permutationen der n Zahlen füttern und die Operatoren mit den Zahlen 1..4 symbolisch für +,-,*,/
Wenn man einen Operator ändert, hat man ja immer noch das Ergbebnis der Berechnung der vorherigen Zahlen auf dem Stack.
Zu früh am Tag, später mehr

Gruß Horst

Für diesen Beitrag haben gedankt: Martok
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: Di 08.01.13 14:24 
Ein Problem ist noch zu bedenken:

Neben der Kombinatorik der Operatoren gibt es ja noch die der Klammern:

(5 * 4) + 6 ist nicht gleich 5 *(4 + 6). Die Operatoren jedoch sind in der gleichen Reihenfolge.

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Di 08.01.13 14:37 
Hallo Tranx,
user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Neben der Kombinatorik der Operatoren gibt es ja noch die der Klammern: ...

Aus diesem Grund werden die zu untersuchenden Möglichkeiten so schnell groß.
user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
(5 * 4) + 6 ist nicht gleich 5 *(4 + 6).

Bei UPN wird der erste Term zu 5 4 * 6 +, der zweite zu 5 4 6 + *, d.h. sie sind unterscheidbar.

Vor Jahren habe ich mir einmal die Mühe gemacht, eine Routine zu schreiben die AOS-Terme in UPN transformiert. Die Umkehrung habe ich leider nicht. Kennt jemand von Euch für die Transformation von UPN nach AOS eine Quelle? Hier in der EE bin ich noch nicht fündig geworden.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1643
Erhaltene Danke: 236

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Di 08.01.13 15:55 
Hallo,

ich habe die Vorstellung das ich alle z.B 6 Zahlen auf den Stack schiebe und anschließend die 5 Operatoren.
Ich hoffe, alle Berechnungsmöglichkeiten durch die Permutation der Zahlen zu erfassen.
(5 * 4) + 6 = UPN 5 4 * 6 + = UPN 6 5 4 * +

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
Zahl   OP_erator    Ber_echnung
 1
 
 2      +,-,*,/   Zahl1 OP1 Zahl2 
 
 3     +,-,*,/   (Zahl1 OP1 Zahl2) OP2 Zahl3
 
 4     ....

Bei 6 Zahlen und 4 Operatoren pro Berechnung habe ich folgende Kombinationen an Berechnungen
4( Berechung 1) +4*4( Berechung 2) +4*4*4 +4*4*4*4 +4*4*4*4*4 = 1364 bei einer Zahlenkombination.
Da 1+k+k²+k³+...k^n = ( k^(n+1)-1)/(k-1) ist ergibt sich hier auch so
(4^6-1)/(4-1) -1 = 1364
Jetzt gibt es 720 Permutationen der Zahl1..Zahl6 so sind es dann 982080 Berechungen an der Zahl.
Zitat:
Für 6 Zahlen sind das 59,4 Millionen

:?!?:

Welche Berechnung wird denn nicht erfasst?

Gruß Horst
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Moderator
Beiträge: 3657
Erhaltene Danke: 600

Win XP x86, Win 8.1 x64
Lazarus Snapshot; Delphi 7,2007,XE; PHP (PHPEdit,PhpStorm); JS; Java(Eclipse)
BeitragVerfasst: Di 08.01.13 16:07 
Die Sache ist sogar noch einfacher, da du Operatoren mehrfach verwenden darfst. Da brauchst du nur die Zahlen auf einen Stack schieben, und diesen in einer Art Tiefensuche für jede Operation einmal verwürfeln. Ich bin mir relativ sicher, dass mein Code dazu mindestens doppelt so viel tut wie er muss (das könnte auch quadratisch sein), aber dafür ist er dank JS-Array Comprehensions sehr einfach ;)

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Di 08.01.13 16:56 
Hallo Horst_H,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Jetzt gibt es 720 Permutationen der Zahl1..Zahl6 so sind es dann 982080 Berechungen an der Zahl.
Zitat:
Für 6 Zahlen sind das 59,4 Millionen
:?!?:
Welche Berechnung wird denn nicht erfasst?

Nach Deiner Idee werden, wenn ich es richtig verstehe, für vier Operanden alle Möglichkeiten
ausblenden Quelltext
1:
  ((a • b) • c) • d					

berechnet. Dabei fehlt aber u.a. die Variante (a • b)•(c • d).
Wie ich schon weiter oben geschrieben habe, beschreibt die Catalansche Zahl C(n) (de.wikipedia.org/wiki/Catalan-Zahl) die Anzahl der Klammermöglichkeiten/Paarbildungen. Für n = 4 Elemente werden es C(n-1) = C(3) = 5. Diese sind:
ausblenden Quelltext
1:
2:
3:
4:
5:
  (a • b)•(c • d) 
  (a •(b • c)) • d
  a • ((b • c) • d) 
  ((a • b) • c) • d
  a • (b • (c • d))

Oben hatte ich den Fehler C(n) gemacht; es sind aber "nur" C(n-1).
Bei 4 Operationen kann jede auch mehrfach auftreten, d.h. die Operationen permutieren nicht nur, sondern bilden eine Variation mit Wiederholung von 4 (Operationen) zu n-1 Verknüpfungen, d.h. = 4^(n-1). Mein 2.Fehler oben.
Mit den Permutationen der n gegebenen Zahlen wird damit insgesamt
n! 4^(n-1) C(n-1) = n! 4^(n-1) (2(n-1))! / (n! (n-1)!) = 4^(n-1) (2n-2)! / (n-1)!
Für n = 6, 7, 8 werden es insgesamt 30,9 Millionen , 2,7 Milliarden und 283 Mlliarden Möglichkeiten. Für zunehmende n wachsen die Möglichkeiten also noch stärker an.
Bei meiner ersten Berechnung hatte ich leider 2 Fehler. :autsch: Entschuldigung. :oops:

Hallo Martok,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Die Sache ist sogar noch einfacher, da du Operatoren mehrfach verwenden darfst. Da brauchst du nur die Zahlen auf einen Stack schieben, und diesen in einer Art Tiefensuche für jede Operation einmal verwürfeln.

Diese Idee klingt wirklich gut.

Nebenbei: Bei meinem eigenen Versuch rufe ich die oben berechnete Zahl die Methoden für Addition, Subtraktion, usw. rekursiv auf und übergebe ein Feld von Zahlen.
Dies erschien mir sehr aufwendig. Deshalb habe ich es mit genau einem zweidimensionalen Feld versucht, bei dem im 2.Index die Rekursionstiefe gespeichert wird. Leider dauert das noch länger.

Beste Grüße
Mathematiker

Nachtrag: Ich habe in meiner Lösung die Aufrufe der Routinen gezählt. Für 6 Zahlen waren es einmal 112 Millionen, ein zweites Mal 152 Millionen. Hoffentlich habe ich mich schon wieder verrechnet. Ob am Programm etwas nicht stimmt :shock: , muss ich testen. Die unterschiedlichen Werte können aber dadurch entstehen, dass die Aufrufe fehlen, die wegen nicht "aufgehenden" Divisionen entfallen.

Nachtrag 2: Die überzähligen Tests haben mich beschäftigt. Und siehe da, im Programm waren zwei unnötige Tests je Routine. Damit konnte ich die Anzahl der Tests und somit auch die Rechenzeit deutlich auf etwa 25% kürzen. :D

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1586
Erhaltene Danke: 231


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Di 08.01.13 22:34 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Den größten Zeitbedarf hat in meinem Programm die Überprüfung, ob das gewünschte Resultat erzeugt wird. Und das braucht seine Zeit. Deshalb hoffe ich ja, dass jemand eine vielleicht bessere Idee hat.


Warum nicht einfach vom Probeergebnis das gewünschte subtrahieren (oder umgekehrt) und auf 0 vergleichen?