Lösungen mit VBA

Beiträge zum Forumthread

Beiträge zu diesem Forumthread

Betreff

Datum

Anwender

Public Sub pruefen(a) Dim i As Integer Dim x As Integer Dim y As Integer Dim bol As Boolean For i = 1 To 100 bol = False For x = 0 To 16 For y = 0 To 16 If a(x) + a(y) = i Then bol = True End If Next Next If bol = False Then Debug.Print i; Next End Sub

Hallo Gemeinde,
hatte mich zwar bei der Anzahl der Kombinationen geirrt, aber habe inzwischen eine Formellösung gefunden, die mit der von Alifa inzwischen bekannt gegebenen Lösung, die eine gute Formelansatzmöglichkeit bietet, übereinstimmt. Habe diese Lösung ohne vorherige Kenntnis dieses Ergebnisses mit Trial&Error und anschließender manueller Datenstrukturanalyse gefunden.
Bei der Aufgabe scheint es sich um eine Variation der bekannten Aufgabe Addiere alle Zahlen von 1 bis 100 zu handeln. Deshalb bietet sich folgender Losungsansatz an...
1. Hinzufügen der 0 (1.Zahl der Lösung) → Anzahl der zu bildenden Zahlen wird ungerade und es wdn immer 2 Zahlen addiert, die - in 1.Zeile und 1.Spalte einer Matrix angeordnet - automatisch die Addition mit sich selbst (Verdopplung der Zahl) beinhalten.
2. Durch diese Null ergibt sich der Mittelwert aller Ergebniszahlen mit 50 → 17.=Endzahl der Lösung, denn 50+50=100.
3. Da aus der Analyse anzunehmen war, das die Lösungsreihe symmetrisch ist, sollte hier auch die Zahl 50/2=25 eine zentrale Rolle spielen... (17*25=425 → Summe aller positiven Differenzen aus allen Ergebniszahlen und einer Zahl der Lösungsreihe)
4. Die 1 ist unverzichtbar → so ergibt sich auch 2. Die nächste bisher fehlende Zahl wäre dann 3...
5. Ab 3+1=4 müssen die kleinsten bisher fehlenden Zahlen, die ja sonst keine Bildungsmöglichkeit mehr fänden, um 1 (die 1.Zahl der Lösungsreihe>0) vermindert wdn, um eine möglichst große "Additionsbreite" zu erreichen.
6. Auf diese Weise wird 25 als 9. (mittlere) von 17 Zahlen der Lösungsreihe erreicht. Von hier an wdn die Differenzen ("Abstände") der bereits ermittelten Zahlen der Lösungsreihe in umgekehrter Reihenfolge verwendet.
Userbild

Auf dieser Basis sollte es auch nicht schwer fallen, eine reine VBA-Lösung zu entwickeln, was ich ebenso wie eine exakte mathematische Beweisführung und das Finden evtl weiterer Lösungen gerne dem Forum überlasse... ;-)
Gruß Luc :-?
PS: Habe leider doch vergessen, die relativen Adressen der bedingten Formatierung (letzte 2 Formelzeilen) anzupassen (d.h., xlAutomatik rückgängig zu machen). Deshalb bitte B26 als A2 und B27 als B2 lesen!

Hallo,
habe auch noch mal nachgedacht. (Puuhh, das war schwer)
Mein Ansatz wäre folgender:
1. "1" Bestandteil
2. eine Zahl der Reihe muss >= 50 (um die 100 darstellen zu können)
3. eine weitere Zahl muss >= 25 (um die 49 darstellen zu können)
4. bei aufsteigender Zahlenreihe gilt für das (n+1)-te Glied = maximal 2* (n)-te Glied +1
5. die ersten 14 Zahlen müssen mind. 1-25 darstellen können
6. die ersten 15 Zahlen müssen mind. 1-50 darstellen können
7. eine unvollständige x( Lösung analog dem 8-Damen-Problem
Ausgang: 14-zahlige Reihe von 1,2,3...,14
15. Zahl: 25
16. Zahl 50
wenn keine Lösung, dann erhöhe 16. Zahl - bis Lösung oder Abbruchkriterium (hier greift wohl zuerst 4.)
wenn keine Lösung, dann erhöhe 15. Zahl - setzte 16. Zahl auf max(15.Zahl+1;50) bis Lösung oder Abbruchkriterium (hier greift wohl zuerst 4.)
- wiederhole bis für 15. Zahl die 4. Abbruchbedingung greift.
- erhöhe 14. Zahl - Prüfe 5.,6.,7, - ....
- erhöhe 13. Zahl - Prüfe 5. 6.,7. - ...
d.h. in den ersten Zweigen des Lösungsbaums werden nur wenige Kombinationen ausgeschlossen (es greift zumeist nur 2. als Abbruch), aber es werden auch nur wenige geprüft.
je weiter man im Lösungsbaum nach oben steigt, desto häufiger greifen die Bedinungen 5.-7. und größere Äste werden komplett abgeschnitten.
Alternativ:
Löse das max.14-aus-14-mit-1-bis-14-Spiel - heißt alle Zahlenreihen mit max. 14 Zahlen aus 1-14, welche 1-14 darstellen können (sind max. 4864 Lösungen) - nur diese können das Spiel lösen.
Erweitere auf max.15-aus-15-mit-1-bis-15-Spiel und prüfe Bedingungen 1-7
Erweitere auf max.16-aus-16-mit-1-bis-16-Spiel und prüfe Bedingungen 1-7
Erweitere auf max.16-aus-17-mit-1-bis-17-Spiel und prüfe Bedingungen 1-7
Anfangs steigt die Anzahl der möglichen (Zwischen)Lösungen mit Faktor von fast 2 mit sinkender Tendenz, bei Erweiterung auf 25 ist der Faktor nur noch Ab ca. 70 ist der Faktor dann deutlich unter 1.
Problem ist hier nur das sinnvolle Verwalten der Zwischenlösungen und das clevere Merken der Prüfergebnisse der vorherigen Erweiterung, da hier Reihen mehrfach auf ähnliche Sachverhalte geprüft werden.
Nach grober Abschätzung dürfte zwischenzeitlich max. 10^9 Zwischenlösungen enstehen. Ob VBA dafür aus Performancegründen geeignet, keine Ahnung
LG
Carlo

Beliebteste Forumthreads (12 Monate)

21 Beiträge zum Forumthread Beiträge zu diesem Forumthread

Beliebteste Forumthreads (12 Monate)

Beliebteste Forumthreads (12 Monate)

21
Beiträge zum Forumthread

Beiträge zu diesem Forumthread