Haus des Nikolaus Möglichkeiten? |
31.08.2021, 19:10 | Matheenoob32 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Haus des Nikolaus Möglichkeiten? Hallo, Ich habe die Aufgabe bekommen zu bestimmen, wie viele Möglichkeiten es gibt das Haus des Nikolaus ohne Absetzen zu zeichnen. Meine Ideen: Ich denke mal, dass es viele Möglichkeiten gibt und daher meine Frage, ob man das irgendwie ausrechnen kann und ja wie? Oder soll man da wirklich alle Möglichkeiten ausprobieren? |
||||||||||||||||||||||
31.08.2021, 19:20 | G310821 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten?
|
||||||||||||||||||||||
16.09.2021, 10:40 | Ulrich Ruhnau | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten? Als ich mit 17 Jahren einen Commodore-Pet 2000 erworben hatte, schrieb ich viele Basic-Programme, darunter auch eines, das die Möglichkeiten zählt, das Haus vom Nikolaus zu zählen. Es gibt 44 Möglichkeiten die mit dem linken unteren Punkt beginnen sowie 44 Möglichkeiten, die mit dem rechten unteren Punkt beginnen. Andere Möglichkeiten das Haus in einem Strich zu zeichnen gibt es nicht. Es sind also 88 Möglichkeiten.[attach]53638[/attach] |
||||||||||||||||||||||
16.09.2021, 11:22 | klauss | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten? In meiner Schulzeit ging es vor allem darum, ohne Absetzen zu zeichnen, wobei jede Teilstrecke nur 1 x durchlaufen werden darf. Das sind ja wohl viel weniger Möglichkeiten. |
||||||||||||||||||||||
16.09.2021, 11:54 | Ulrich Ruhnau | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten?
|
||||||||||||||||||||||
16.09.2021, 15:06 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Interessanterweise gibt es meines Wissens nach keinen "einfachen" Weg, diese Anzahl 44 kombinatorisch plausibel zu machen - man muss sich wohl wirklich in die Niederungen des Abzählens begeben. Aufgrund des Graphen kann man lediglich eine grobe obere Abschätzung für die Anzahl der Wege geben, und zwar folgendermaßen: Von links unten beginnend hat man anzufahren a) drei Knoten (inklusive Anfangsknoten), wo man beim ersten Durchlauf drei Möglichkeiten der Wegwahl, beim zweiten Durchlauf allerdings nur noch eine Möglichkeit hat. b) den Zielknoten mit zwei Möglichkeiten der Wegwahl beim ersten Durchlauf. c) einen Knoten (ganz oben) mit nur einem Durchlauf und auch nur einer Wahl. Mit diesen Überlegungen bekommt man eine Obergrenze für die Anzahl der Wege, von denen allerdings 10 nicht passen, weil sie "zu früh" den Zielknoten rechts unten zum zweiten Mal anfahren - Sackgasse! EDIT: Peinlich, peinlich, großer Fehler bei der Anzahl der Möglichkeiten beim Zielknoten - korrigiert! |
||||||||||||||||||||||
Anzeige | ||||||||||||||||||||||
|
||||||||||||||||||||||
16.09.2021, 16:18 | klauss | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten? Aha, so unterschätzt man also die Anzahl, wenn man eine Handvoll Wege gefunden hat und dabei auch in ein paar Sackgassen geraten ist. |
||||||||||||||||||||||
16.09.2021, 16:49 | jmd | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Und wieviele Möglichkeiten gibt es,so dass man das Haus nicht zeichnen kann? Oder genauer Um das Haus zu zeichnen sind 8 Striche notwendig Wieviele Möglichkeiten gibt es,so dass man nur 7 bzw 6 usw Striche zeichnen kann? Bei 3 Strichen gibt es offenbar 2 Möglichkeiten. Da beginnt man oben und zeichnet einfach das Dach |
||||||||||||||||||||||
16.09.2021, 17:22 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Sowas würde ich schon mal gar nicht zulassen: Soviel graphentheoretische Grundbildung sollte schon sein, dass man links oder rechts unten anfängt. |
||||||||||||||||||||||
16.09.2021, 17:27 | klauss | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten? Etwas förmlicher gefragt: Wie sieht die Wahrscheinlichkeitsverteilung aus, dass man von einem beliebigen Startpunkt aus zufällig einen erlaubten Weg findet? |
||||||||||||||||||||||
16.09.2021, 17:35 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Wenn man, wie von mir oben beschreiben, an jedem Punkt wo man noch mehr als eine Möglichkeit hat, jede dieser Möglichkeiten gleichberechtigt wählt, dann müsste das sein. Man kann es so begründen: Jeder erfolgreiche Weg ist dadurch gekennzeichnet, dass man an den vier Punkten des Quadrats beim erstmaligen Passieren dieser Punkte eine Entscheidung für einen von drei (bzw. im Zielpunkt nur zwei) möglichen Wegen getroffen hat, d.h., genau dieser Erfolgsweg hat die Wahrscheinlichkeit . Dies trifft nun auf JEDEN der 44 Erfolgswege zu, daher ist die bedingte Wahrscheinlichkeit für den Erfolg unter der Bedingung, links unten zu starten, gleich . Genauso für den Start rechts unten, während die Erfolgswahrscheinlichkeit unter der Bedingung des Starts in einem der drei anderen Punkte gleich Null ist. P.S.: Gehen wir mal davon aus, dass man von einem der beiden unteren Punkte startet. Dann ist die bedingte Wahrscheinlichkeit zu scheitern dreimal so hoch, wenn man als ersten Zug den anderen unteren Randpunkt anfährt, als wenn man einen der beiden anderen Wege wählt: Im ersteren Fall , in den beiden anderen Fällen nur , was dann eben in der Mischung ergibt. |
||||||||||||||||||||||
03.10.2021, 14:07 | ML_ | Auf diesen Beitrag antworten » | ||||||||||||||||||||
RE: Haus des Nikolaus Möglichkeiten? Hallo,
es bietet sich an, hierzu ein Computerprogramm zu schreiben. Als Schüler (vor vielen Jahren) habe ich ein solches Programm für ein doppeltes Haus des Nikolaus (Spiegelung an der unteren Kante) geschrieben. Es ließ sich mit einer Rekursion recht gut lösen und hat deutlich mehr als die genannten 88 Lösungen; ich erinnere mich aber nicht mehr an die Zahl. Viele Grüße Michael |
||||||||||||||||||||||
03.10.2021, 14:51 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Ist wohl auch nicht ganz so wichtig, da nach der Anzahl für das Einfach- statt für das Doppelhaus gefragt wurde. |
||||||||||||||||||||||
04.10.2021, 06:48 | Finn_ | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Das ist wieder so ein typisches Beispiel für den Einsatz des Backtracking-Verfahrens. Es fängt bei einem gewählten Knoten an. Zum Knoten wird jede der noch verfügbaren Kanten separat betrachtet. Die jeweilige Kante wird bei ihrer Betrachtung aus der Kantenmenge entfernt und dann auf den Nachbarknoten das soeben beschriebene Verfahren abermals angewandt. Falls die Kantenmenge leer sein sollte, ist ein Eulerweg gefunden. In aller Ausführlichkeit:
|
||||||||||||||||||||||
04.10.2021, 07:30 | Finn_ | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Oder in aller Kürze, wenn euch das vorherige Programm zu langatmig war:
|
||||||||||||||||||||||
04.10.2021, 11:10 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Spielt aber beim Nikolaushaus noch keine Rolle, da muss man den Algorithmus wohl mit einem größeren Graph füttern. |
||||||||||||||||||||||
04.10.2021, 16:07 | Finn_ | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Aber vorsichtig sein, wenn das Programm weniger funktional geschrieben ist. Weder ist
Bemerkung: Das neuartige strenge Typsystem von Rust würde einen solchen Fehler übrigens erst gar nicht zulassen. Mit linearen/affinen (Ownership) und regionalen Typen (Lebenszeiten) kann man eben weit mehr erreichen als nur Speichersicherheit. Zweite Bemerkung: Man darf übrigens
|
||||||||||||||||||||||
04.10.2021, 17:53 | Finn_ | Auf diesen Beitrag antworten » | ||||||||||||||||||||
OK, die kürzeste Fassung, die ich anbieten kann:
|
||||||||||||||||||||||
04.10.2021, 20:10 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Ich weiß nicht, da geht bestimmt noch ein bisschen mehr in Hinblick Unverständlichkeit und Verschleierung der Funktionsweise. Vielleicht trennt man den letzten Teils des Threads ab unter dem Thema "Wie schreibe ich Python-Code mit maximaler Zeilenlänge und extrem viel Funktionalität pro Zeile". |
||||||||||||||||||||||
19.09.2022, 21:43 | MaiVale | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Haus vom Nikolaus in 3d Hallo. Ich habe ein kleines Problem und ich denke ihr könnt mir dabei am Besten helfen. Ich habe mich an eurem vorherigem Code bedient und ihn angepasst, um das Haus vom Nikolaus nicht in 2d sondern in 3d auszulesen. Leider zeigt mir Python kein Ergebnis an und ich weiß nicht wo der Fehler liegt. def traverse(E, v): return sum(traverse(E - {e}, e[v == e[0]]) for e in E if v in e) if E else 1 def count_paths(G): return sum(traverse(set(G[1]), v) for v in G[0]) Haus_des_Nikolaus = ( [1, 2, 3, 4, 5, 6, 7, 8, 9], [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 8), (3, 4), (3, 5), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 9), (6, 8), (6, 9), (7, 8), (7, 9), (8, 9)] ) print(count_paths(Haus_des_Nikolaus)) Hab ich mich irgendwo vertan oder bin ich auf der völlig falschen Fährte? Ich freue mich über eure Hilfe |
||||||||||||||||||||||
20.09.2022, 06:33 | Finn_ | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Es wird wohl ein gleichartiges Problem wie beim nachfolgenden Algorithmus sein, wo das Problem offensichtlicher hervortritt. Es sind da sämtliche Permutationen der Kantenliste abzuklappern. Wie lange das dauert, hängt also (unter anderem) von der Anzahl der Permutationen ab.
|
|