Makro für Problem < Wettbewerbe < Informatik < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 17:59 Di 09.03.2010 | Autor: | Ferma |
Hallo Programmierer,
gesucht 16 Zahlen von 1 bis 100. Mit je 2 von diesen sollen mittels Addition alle Zahlen von 1 bis 100 gebildet werden können. Ich denke an ein Array mit 17 Zahlen(die 0 ist auch dabei) Dieses Array soll verändert werden, bis die richtigen Zahlen gefunden sind. Initialisiert wird das Array mit plausibeln Werten. Die ersten beiden Zahlen sind sicher:0 und 1; a(2)= 2 bis3,; a(3)=3 bis 5; a(4)=4 bis......a(16)=45 bis 80; a(17)=50 bis90. Das nächste Element ist stets größer. Ich habe es mit brute force versucht, leider...Vielleicht hat jemand Spaß daran...
Gruß, Ferma
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 23:22 Di 09.03.2010 | Autor: | Karl_Pech |
Hallo Ferma,
Ich denke nicht, daß es möglich ist, jede Zahl von 1 bis 100 alleine durch die Addition von jew. zwei aus insg. 16 Zahlen darzustellen. Betrachte z.B. folgendes Python-Programm:
1: | from math import floor
| 2: |
| 3: | f = open('out.txt','w')
| 4: |
| 5: | bfoundsmallestsolution = False
| 6: |
| 7: | for g in range(8):
| 8: | bfoundsmallestsolution = False
| 9: | for a in range(floor(g/2),g+1):
| 10: | if not bfoundsmallestsolution:
| 11: | for b in range(floor(g/2)+1):
| 12: | if a+b==g:
| 13: | #bfoundsmallestsolution = True
| 14: | print(g,a,b,file=f)
| 15: | break
| 16: | else:
| 17: | break
| 18: | print('\n',file=f)
| 19: |
| 20: | f.close() |
Kommentiert man 'bfoundsmallestsolution = True' aus, so daß das Programm alle Lösungstupel für eine Zahl ausgibt, erhält man:
0 0 0
1 1 0
2 1 1
2 2 0
3 2 1
3 3 0
4 2 2
4 3 1
4 4 0
5 3 2
5 4 1
5 5 0
6 3 3
6 4 2
6 5 1
6 6 0
7 4 3
7 5 2
7 6 1
7 7 0
8 4 4
8 5 3
8 6 2
8 7 1
8 8 0
Jetzt sieht man, daß man weniger Summanden braucht, wenn man kleinere Summanden nimmt. Z.B. könnte man 0 = 0+0, 1=1+0 und 2=2+0 schreiben und erhält eine Liste mit 3 Summanden {0,1,2}. Besser ist es jedoch 2=1+1 zu schreiben, so daß die Liste ein Element weniger enthält. Und man sieht, daß sich das für die anderen Zahlen fortsetzt. Läßt man das Programm deshalb nur nach den kleinsten Summanden suchen, indem man 'bfoundsmallestsolution = True' wieder in den Code einfügt, erhält man Folgendes:
0 0 0
1 1 0
2 1 1
3 2 1
4 2 2
5 3 2
6 3 3
7 4 3
8 4 4
Für die Zahlen 0 bis 8 braucht man also die Summanden 0 bis 4. Weniger geht nicht, denke ich. Für die Zahlen 1 bis 100 sind es dann min. 50 Summanden, wenn ich das Programm damit laufen lasse. Nur allgemein beweisen, daß man bei [mm]n\![/mm] Zahlen mindestens [mm]\approx\tfrac{n}{2}[/mm] Summanden zur Darstellung braucht, konnte ich nicht. Dabei müßte das doch eigentlich sehr einfach zu beweisen sein...
Viele Grüße
Karl
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 08:15 Mi 10.03.2010 | Autor: | Ferma |
Hallo Karl,
tatsächlich soll es heißen "mit maximal 2 Zahlen". Beispiel: 1=1; 2=1+1; 3=3; 4=2+2; 5=5;
Sieh Dir bitte das an: Eine harte Nuß zum Wochenende +Spotlight (in google eingeben)
Gruß, Ferma
|
|
|
|
|
Man könnte die Aufgabe ja auch allgemeiner formulieren...
Aufgabe | Gegeben: [mm]\mathcal{B}\subset\mathbb{N}_0[/mm] mit [mm]2\leqslant\left|\mathcal{B}\right|<\infty,\ 0\in\mathcal{B}[/mm] und [mm]\forall\gamma\in\mathcal{B}\setminus\{0\}\exists\delta\in\mathcal{B}:\gamma=\delta+1[/mm].
Gesucht: Ein Algorithmus, der so schnell wie möglich (zumindest besser als Brute-Force) ein [mm]A\subseteq\mathcal{B}[/mm] bestimmen kann, für das Bedingung [mm]\alpha[/mm] erfüllt ist: [mm]\forall x\in\mathcal{B}\,\exists a,b\in A:a+b=x[/mm].
Dabei soll es kein [mm]\widetilde{A}\subseteq\mathcal{B}[/mm] geben mit [mm]\left|\widetilde{A}\right|<\left|A\right|[/mm] für das Bedingung [mm]\alpha[/mm] gilt. |
Ich denke, ich verschiebe diese Diskussion nun ins Forum Informatik -> Wettbewerbe, da ich jetzt selber gespannt bin, wer diese Frage beantworten kann. Ich kann's jedenfalls ( (noch (?) ) nicht.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 04:02 Di 15.06.2010 | Autor: | felixf |
Moin!
> Man könnte die Aufgabe ja auch allgemeiner formulieren...
>
>
>
> Gegeben: [mm]\mathcal{B}\subset\mathbb{N}_0[/mm] mit
> [mm]2\leqslant\left|\mathcal{B}\right|<\infty,\ 0\in\mathcal{B}[/mm]
> und
> [mm]\forall\gamma\in\mathcal{B}\setminus\{0\}\exists\delta\in\mathcal{B}:\gamma=\delta+1[/mm].
Sprich: [mm] $\mathcal{B} [/mm] = [mm] \{ 0, 1, \dots, n \}$ [/mm] fuer $n [mm] \ge [/mm] 1$.
> Gesucht: Ein Algorithmus, der so schnell wie möglich
> (zumindest besser als Brute-Force) ein
Die Frage ist, was genau du unter Brute Force verstehst. Brute Force mit Pruning ist wesentlich schneller als "normales" Brute Force, aber immer noch "langsam" (superexponentiell in $n$).
Hier ein paar Beobachtungen, die beim prunen helfen. Sei [mm] $(a_1, \dots, a_m)$ [/mm] eine Loesung mit [mm] $a_1 [/mm] < [mm] \dots [/mm] < [mm] a_m$.
[/mm]
* Es gilt [mm] $a_0 [/mm] = 0$ und [mm] $a_1 [/mm] = 1$.
* Ist die Loesung minimal (also $m$ minimal), so gilt [mm] $a_i \le [/mm] n - (m - i)$.
* Wenn man sich [mm] $a_1, \dots, a_i$ [/mm] anschaut, und von diesen $k$ Zahlen aus [mm] $\{ 0, \dots, n \}$ [/mm] nicht abgedeckt werden, so muss $k [mm] \le \frac{m (m + 1)}{2} [/mm] - [mm] \frac{i (i + 1)}{2}$ [/mm] sein.
* Es muss [mm] $a_m [/mm] + [mm] a_m \ge [/mm] n$ sein, also [mm] $a_m \ge \bigl\lceil \frac{n}{2} \bigr\rceil$.
[/mm]
* Es muss [mm] $a_m [/mm] + [mm] a_{m-1} \ge [/mm] n - 1$ sein, also [mm] $a_m \ge [/mm] n - 1 - [mm] a_{m-1}$.
[/mm]
LG Felix
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 22:01 So 27.06.2010 | Autor: | felixf |
Moin!
> Man könnte die Aufgabe ja auch allgemeiner formulieren...
>
>
>
> Gegeben: [mm]\mathcal{B}\subset\mathbb{N}_0[/mm] mit
> [mm]2\leqslant\left|\mathcal{B}\right|<\infty,\ 0\in\mathcal{B}[/mm]
> und
> [mm]\forall\gamma\in\mathcal{B}\setminus\{0\}\exists\delta\in\mathcal{B}:\gamma=\delta+1[/mm].
>
> Gesucht: Ein Algorithmus, der so schnell wie möglich
> (zumindest besser als Brute-Force) ein
> [mm]A\subseteq\mathcal{B}[/mm] bestimmen kann, für das Bedingung
> [mm]\alpha[/mm] erfüllt ist: [mm]\forall x\in\mathcal{B}\,\exists a,b\in A:a+b=x[/mm].
>
> Dabei soll es kein [mm]\widetilde{A}\subseteq\mathcal{B}[/mm] geben
> mit [mm]\left|\widetilde{A}\right|<\left|A\right|[/mm] für das
> Bedingung [mm]\alpha[/mm] gilt.
>
> Ich denke, ich verschiebe diese Diskussion nun ins Forum
> Informatik -> Wettbewerbe, da ich jetzt selber gespannt
> bin, wer diese Frage beantworten kann. Ich kann's
> jedenfalls ( (noch (?) ) nicht.
Ich bin mal etwas genauer auf Suche gegangen, und hab mit meinem Programm geschaut, ab welchem $n$ man [mm] $|\mathcal{B}|$ [/mm] um eins erhoehen muss. Dabei kam der Anfang der Sequenz A001212 in Sloanes Integer Sequence Encyclopedia heraus.
Das Postage Stamp Problem ist aehnlich zu unserem Problem mit $h = 2$, mit dem Unterschied dass 0 kein Element der Menge sein muss (darf), da man auch null oder einen Summanden verwenden kann.
Es wurde uebrigens gezeigt, dass dieses Problem NP-hart ist, insofern wird es wohl keine Loesung mit sub-exponentieller oder gar polynomieller Laufzeitkomplexitaet geben. Damit ist diese Frage zumindest teilweise beantwortet.
LG Felix
|
|
|
|
|
Hallo!
ich habe jetzt tatsächlich mal ein Bruteforce-programm geschrieben.
Es gibt ein Array von 16 Elementen, die allesamt mit 1 initialisiert werden.
Es wird getestet, ob sich die Zahlen 1-100 aus ein bis zwei Zahlen des Arrays bilden lassen.
Dann wird die erste Zahl im Array um 1 vergrößert. Ist die Zahl 101, wird die zweite Zahl vergrößert, und die erste auf den gleichen Wert wie die zweite gesetzt, usw. Es wird also der Reihe nach durchgezählt.
Das Problem ist nur die Rechenzeit. Mein Rechner rechnet nun schon seit 1,5 Stunden und ist erst bei
95 94 87 86 71 53 3 1 1 1 1 1 1 1 1 1
angekommen. Braucht also noch ein paar tausend Stunden Rechenzeit, wenn nicht irgendwem noch eine geniale Optimierung einfällt.
Link zum 1. Dateianhang
Dateianhänge: Anhang Nr. 1 (Typ: cpp) [nicht öffentlich]
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 21:10 Do 25.03.2010 | Autor: | Ferma |
eine geniale Idee findest Du hier:" Eine harte Nuß zum Wochenende +Spotlight". So bei Google eingeben. Das Programm stammt von Marco und ist jn Java geschrieben. Wenn das jemand in VBA übersetzen könnte...Das funktioniert schneller. Ein paar Lösungen sind dort angegeben
Gruß, Ferma
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 22:46 So 06.06.2010 | Autor: | felixf |
Hallo!
> eine geniale Idee findest Du hier:" Eine harte Nuß zum
> Wochenende +Spotlight". So bei Google eingeben. Das
> Programm stammt von Marco und ist jn Java geschrieben. Wenn
> das jemand in VBA übersetzen könnte...Das funktioniert
> schneller.
Glaubst du ernsthaft, dass ein VBA-Programm schneller ist als ein entsprechendes Java-Programm?
LG Felix
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 04:02 Di 15.06.2010 | Autor: | felixf |
Hallo!
> gesucht 16 Zahlen von 1 bis 100. Mit je 2 von diesen
> sollen mittels Addition alle Zahlen von 1 bis 100 gebildet
> werden können. Ich denke an ein Array mit 17 Zahlen(die 0
> ist auch dabei) Dieses Array soll verändert werden, bis
> die richtigen Zahlen gefunden sind. Initialisiert wird das
> Array mit plausibeln Werten. Die ersten beiden Zahlen sind
> sicher:0 und 1; a(2)= 2 bis3,; a(3)=3 bis 5; a(4)=4
> bis......a(16)=45 bis 80; a(17)=50 bis90. Das nächste
> Element ist stets größer. Ich habe es mit brute force
> versucht, leider...Vielleicht hat jemand Spaß daran...
Ich hab da ein wenig rumprogrammiert, und mein aktuelles Programm braucht 8 Minuten 10 Sekunden, um festzustellen, dass es keine solchen 16 Zahlen gibt (mal angenommen das Programm ist korrekt).
Ich hab mir auch den anderen Thread angeschaut; die dortigen Loesungen von Marco13 haben alle 17 Zahlen, nicht 16!
Mein Programm sucht nun nach Loesungen mit 17 Zahlen, nach etwas mehr als 7 Minuten hat es schon Fast-Loesungen gefunden, bei denen nur noch eine Zahl fehlt.
LG Felix
PS: Es handelt sich um eine Intel(R) Xeon(TM) CPU mit 2.80GHz.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 05:54 Di 15.06.2010 | Autor: | felixf |
Moin!
> > gesucht 16 Zahlen von 1 bis 100. Mit je 2 von diesen
> > sollen mittels Addition alle Zahlen von 1 bis 100 gebildet
> > werden können. Ich denke an ein Array mit 17 Zahlen(die 0
> > ist auch dabei) Dieses Array soll verändert werden, bis
> > die richtigen Zahlen gefunden sind. Initialisiert wird das
> > Array mit plausibeln Werten. Die ersten beiden Zahlen sind
> > sicher:0 und 1; a(2)= 2 bis3,; a(3)=3 bis 5; a(4)=4
> > bis......a(16)=45 bis 80; a(17)=50 bis90. Das nächste
> > Element ist stets größer. Ich habe es mit brute force
> > versucht, leider...Vielleicht hat jemand Spaß daran...
>
> Ich hab da ein wenig rumprogrammiert, und mein aktuelles
> Programm braucht 8 Minuten 10 Sekunden, um festzustellen,
> dass es keine solchen 16 Zahlen gibt (mal angenommen das
> Programm ist korrekt).
Ich hatte mich ein wenig vertan und etwas zu wenig geprunt. Jetzt benoetigt das Programm 14 Sekunden, um zu zeigen, dass es keine Loesung mit 16 Zahlen gibt.
Weiterhin findet es alle Loesungen mit 17 Zahlen innerhalb 25 Minuten; diese sind:
(0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 28, 29, 30, 61, 64, 67, 70)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 45, 47, 48, 49, 52)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 47, 48, 49, 51)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 48, 49, 51, 53)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52)
(0, 1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90)
(0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)
Dies umfasst alle Loesungen, die Marco13 gepostet hat.
Ich habe mein C++-Programm mal angehaengt; es ist nicht wirklich gut dokumentiert. Es umfasst eine Bit-Vektor-Klasse, die das ganze etwas schneller machen sollte als std::vector<bool>. Der obere Wert $n$ fuer das Intervall ist im Programm einkodiert, dies macht es vermutlich auch noch einen Tacken schneller. Kompilieren laesst es sich mit g++ -O3 -o executable programm.cpp, momentan nur mit dem G++ da ein spezieller GCC-Befehl fuer's Bitzaehlen benutzt wird (das laesst sich wegoptimieren, aber dazu hab ich grad keine Lust).
LG Felix
Dateianhänge: Anhang Nr. 1 (Typ: cpp) [nicht öffentlich]
|
|
|
|
|
Hallo Zusammen,
Ich habe nun auch etwas Zeit gefunden mich mit diesem Problem zu beschäftigen. Da Felix das Problem bereits gelöst hat, habe ich zwei Näherungsverfahren ausprobiert, um festzustellen, ob es damit auch lösbar ist. Leider hat sich das Problem gegenüber den klassischen evolutionären Algorithmen als resistent herausgestellt. Ich habe dann ein wenig gesucht und bin auf die Wohlklang-Suche gestoßen. Ich habe daraufhin eine Variante der Version von 2001 von diesem Verfahren in Python implementiert.
Das Python-Programm besteht aus zwei Modulen: pereignisgen und wks.
pereignisgen kann ein Ereignis mit einer vorgegebenen Wahrscheinlichkeit $p$ eintreten lassen. (Dann wird 'True' zurückgegeben. D.h. mit W'keit $1-p$ tritt das Ereignis nicht ein und es wird 'False' zurückgegeben.) Die Funktion ereignisgeschieht() schneidet ein vorgegebenes $p$ zunächst auf 5 Stellen nach dem Komma ab und wandelt dieses dann in einen gekürzten Bruch um (Spezialfälle wie $p=1$ und $p=0$ werden berücksichtigt. Alternativ kann $p$ auch als Paar (zaehler, nenner) an die Funktion übergeben werden, wenn man z.B. mit W'keiten wie 1/7 arbeiten möchte. Ich benutze im Übrigen auch Hashing an zwei Stellen, um die Funktion zu beschleunigen.)
Nachdem wir $p$ als ein Paar (zaehler, nenner) vorliegen haben, werden 'zaehler' viele Zufallszahlen ausgewählt. Dazu fangen wir mit einer Liste [1, nenner] an und fügen die erste Zufallszahl ein: [1, z0, nenner]. Danach kommt der nächste Durchlauf [1, z2, z0, z1, nenner] u.s.w. . Dabei wird jede neue Zahl zwischen zwei "Nachbar"zahlen der Liste ausgewählt, wenn zwischen den Nachbarzahlen "genug Platz" ist. Wurde z.B. eine W'keit wie 2/3 übergeben, geschieht folgendes: [1, 3] --> [1, 2, 3]. Jetzt ist kein Platz mehr, um noch eine Zahl einzufügen. Deshalb muß dieser Spezialfall (zaehler == 1) behandelt werden, indem zufällig entweder 1 oder nenner in der Liste belassen werden, also z.B. [2,3]. War jedoch zaehler == 0, werden 1 und nenner aus der Liste gelöscht: [2] (z.B. für [mm] $p=\tfrac{1}{3}$).
[/mm]
Zum Schluss wird eine Zufallszahl zwischen 1 und nenner ausgewählt und es wird geprüft, ob diese Zahl in der zaehler-Zufallszahl-Liste vorhanden ist.
Kommen wir nun zu wks. Im 1ten Schritt des Verfahrens wird der sogenannte Wohlklang-Speicher WS initialisiert. Dabei wird entweder ein vorhandener Speicher von einem Speichermedium geladen. Oder aber es wird ein Speicher mit zufälliger Belegung erzeugt.
Der WS besteht aus WSG (WS-Größe) vielen Listen, die alle eine Länge [mm] $N+2\!$ [/mm] haben. In den ersten [mm] $N+1\!$ [/mm] Zellen, werden Zufallszahlen zwischen [mm] $0\!$ [/mm] und [mm] $\left\lfloor\tfrac{x}{2}\right\rfloor$ [/mm] gespeichert, [mm] $\forall x\in\left[0:N\right]$. [/mm] In der [mm] $N+1\texttt{-ten}$ [/mm] Zelle wird die Bewertung der aktuellen [mm] ($y\texttt{-ten}$) [/mm] Liste gespeichert. (Hierbei wird jede Liste im WS als Wohlklang bezeichnet und die Bewertung einer Liste ist demnach eine Hörprobe dieses Wohlklangs. Ein Element der Liste heißt "Note".)
Im 2ten Schritt wird mit der Wohlklang-Speicher-Betrachtungswahrscheinlichkeit (WSBW) ein neuer Wohlklang gänzlich aus den im WS vorhandenen Wohlklängen erzeugt. Dazu wird in der [mm] $x\texttt{-ten}$ [/mm] WS-Spalte zufällig eine Note eines entsprechenden Wohlklangs ausgewählt. Mit der W'keit 1-WSBW wird der neue Wohlklang ganz zufällig erzeugt. Im Nachhinein ist mir jedoch aufgefallen, daß ich diesen Teil des Verfahrens mißverstanden habe. Und zwar sollte eigentlich für jede Note eines neuen Wohlklangs individuell entschieden werden, ob diese mit W'keit WSBW aus dem WS oder ganz zufällig erzeugt wird. Allerdings hat dieses Mißverständnis in meinem Falle dazu geführt, daß das Verfahren sogar besser funktioniert hat. Denn wenn man sich umgekehrt die Frage stellt, wie ein individuelles WSBW gewählt sein sollte, damit alle Noten mit W'keit 0.95 aus dem WS gewählt werden, so müßte [mm] $\operatorname{WSBW}^{101}\stackrel{!}{=}0.95\Leftrightarrow \operatorname{WSBW} \approx [/mm] 0.99949$ gelten. Wenn man also folgenden Code:
1: | if ereignisgeschieht(WSBW):
| 2: | for x in range(N+1):
| 3: | neuerwohlklang.append(WS[randint(0, WSG-1)][x])
| 4: | else:
| 5: | for x in range(N+1):
| 6: | neuerwohlklang.append(randint(0, x//2)) |
durch Diesen ersetzt:
1: | for x in range(N+1):
| 2: | if ereignisgeschieht(WSBW):
| 3: | neuerwohlklang.append(WS[randint(0, WSG-1)][x])
| 4: | else:
| 5: | neuerwohlklang.append(randint(0, x//2)) |
Und WSBW von 0.95 auf 0.99949 setzt, müßten beide Schleifen die meiste Zeit ungefähr dasselbe leisten. Deshalb habe ich den Code auch nicht mehr verändert. Denn das Verfahren hat von der erhöhten "virtuellen" individuellen WSBW offenbar sehr stark profitiert. (Es scheint, daß für dieses Problem die Ausnutzung vom bereits vorhandenen Wissen ("Exploitation") wesentlich wichtiger ist, als die zufällige Erzeugung neuer Wohlklänge ("Exploration").)
Der 3te Schritt des Verfahrens besteht darin, den schlechtesten Wohlklang des WS durch den neuen Wohlklang zu ersetzen, sofern der neue Wohlklang besser ist. Das Programm prüft alle 20000 Iterationen, ob es sich beenden soll und schreibt gleichzeitig ständig den aktuellen Inhalt des WS auf ein Speichermedium, sowie eine kleine Statistik zur Verteilung der Wohlklänge.
Das Programm und zwei Testläufe dazu befinden sich, wie schon gesagt, im Anhang. Das beste Ergebnis war die Erzeugung von Summandenketten mit 22 Summanden, wie z.B. diese hier:
0 0 0 0 2 2 3 1 0 1 0 5 6 5 6 5 2 3 8 2 10 3 8 6 0 8 8 3 10 5 6 14 0 1 10 17 18 0 14 2 8 17 10 6 1 0 0 1 2 5 1 3 6 8 5 8 10 5 6 10 8 14 14 18 17 18 17 24 24 24 24 24 24 24 37 32 24 32 32 32 37 32 37 37 32 37 43 43 44 44 44 45 43 44 47 46 48 48 49 47 48 : 22
Es gilt also:
0 + 0 = 0, 0 + 1 = 1, 0 + 2 = 2, 0 + 3 = 3, 2 + 2 = 4, u.s.w.
Viele Grüße
Karl
Dateianhänge: Anhang Nr. 1 (Typ: zip) [nicht öffentlich]
|
|
|
|