Frage von Goolash, 99

Wie bilde ich aus folgendem Problem eine Formel/ einen Algorithmus für leichte Berechnung?

Weiß nicht genau, wie ich die Frage besser formulieren soll...

Ich habe 11 Knöpfe. Mein Ziel ist es, dass jeder Knopf am Ende leuchtet. Wenn ich auf einen Knopf drücke, leuchtet aber nicht dieser, sondern ein anderer auf.

Drücke ich erneut, passiert jedoch nichts, d.h. ich kann einen Knopf nur anschalten wenn ich den passenden andere drücke. Um den Knopf auszuschalten muss ich den Knopf selbst drücken.

In diesem Beispiel:

Knopf 1 drücken: Knopf 5 leuchtet

Knopf 2 drücken: Knopf 11 leuchtet

Knopf 3 drücken: Knopf 7 leuchtet

Knopf 4 drücken: Knopf 1 leuchtet

Knopf 5 drücken: Knopf 3 leuchtet

Knopf 6 drücken: Knopf 2 leuchtet

Knopf 7 drücken: Knopf 6 leuchtet

Knopf 8 drücken: Knopf 9 leuchtet

Knopf 9 drücken: Knopf 10 leuchtet

Knopf 10 drücken: Knopf 4 leuchtet

Knopf 11 drücken: Knopf 8 leuchtet

Wie stelle ich eine Formel auf, um das mathematisch lösen zu können bzw. gibt es einen bestimmten Algorithmus den ich hierfür verwenden kann? Schon mal vielen Dank im Voraus!

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von Roach5, 33

Die Antwort:

Es gibt keine Lösung.

Begründung: Wir fangen bei unserer Untersuchung bereits am Ende an, also wir nehmen an, dass wir durch eine endliche Sequenz an Knopf-drücken auf eine Lösung gekommen sind, also alle Lichter sind an, oBdA betrachten wir die kürzeste solche Sequenz.

Aber was ist einen Knopfdruck davor passiert? Klar ist, dass durch Annahme der kürzesten Lösung einen Knopfdruck vor der Lösung noch nicht alle Knöpfe geleuchtet haben, und pro Knopfdruck kann nur ein Licht angeschaltet werden, also leuchten alle Knöpfe bis auf einen. Der letzte Knopfdruck MUSS also der des Knopfes sein, der unseren letzten Knopf anschaltet. Dieser Knopf selbst muss bereits leuchten, wird also ausgeschaltet. Also leuchtet dieser Knopf am Ende unserer Sequenz nicht, Widerspruch!

Also gibt es entweder keine Lösung oder der Aufgabenstellung fehlt ein wichtiges Detail, das doch zur Lösung führt.

Alle Knöpfe bis auf einen anzuschalten ist sogar relativ einfach, das ganze hab ich in C++ zusammengeschrieben und geht so:

Du schaltest einen beliebigen Knoten an. Jetzt drückst du den Knopf, der leuchtet, ein anderer geht an, der Knopf den du gedrückt hast geht wieder aus, jetzt drückst du den Knopf, den du am Anfang gedrückt hast usw. Also brauchst du, um n Knöpfe anzuschalten, 1+2+...+n = n(n+1)/2 Knopfdrücke, in deinem Beispiel kann man also durch 55 Knopfdrücke 10 der 11 Knöpfe zum Leuchten bringen. Wenn du bei 1 anfängst, leuchten am Ende alle Knöpfe außer die 4, weil 4 der Knopf ist, der die 1 anschalten würde.

Das ganze in C++ mit deinem Beispiel hab ich mal nachprogrammiert. Ich möchte dir hier nicht ganze Projektordner über Dropbox übermitteln, also habe ich alles in eine Datei gequetscht, entschuldige also die Unordnung: https://www.dropbox.com/s/qk3zo8vf34894lg/main.cpp?dl=0

LG

Kommentar von Roach5 ,

Der Algorithmus geht sogar noch einfacher, du gehst den Kreis rückwärts, siehe Roderic: 4->10->9->8->11->2->6->7->3->5 und alles außer der 5 leuchtet in 10 Schritten.

Kommentar von Goolash ,

Hat funktioniert, trotz der fehlenden 5 am Ende. Vielen lieben Dank!

Kommentar von Roderic ,

Kann eigentlich nicht sein. ;-)

Kommentar von Goolash ,

Hat funktioniert im Sinne von "Habe das Level geschafft obwohl die 5 gefehlt hat"

Expertenantwort
von DepravedGirl, Community-Experte für Mathe & Mathematik, 37
(407 x^10)/1814400-(4943 x^9)/362880+(6227 x^8)/17280-(329531 x^7)/60480+(4484501 x^6)/86400-(5593187 x^5)/17280+(482198693 x^4)/362880-(39849017 x^3)/11340+(40758661 x^2)/7200-(2489677 x)/504+1746

Du kannst hier nach rechts scrollen um alles zu sehen.

Diese Funktion macht natürlich nur Sinn, wenn du für x die Nummer deines Knopfes eingibst, für krumme Werte oder Werte außerhalb der Definition kommt natürlich Unfug heraus.

Für die umgekehrte Verknüpfung / Beziehung stellst du am besten eine neue Funktion auf.

Ich bin mir nicht sicher, ob ich richtig verstanden habe, was du willst !

Kommentar von Goolash ,

Vielen Dank!

Kommentar von DepravedGirl ,

Gerne :-)) !

Antwort
von Roach5, 62

Du machst das ganze wenn ich mich nicht irre mit gerichteten Graphen (bin mir nicht sicher, da du dein Problem echt komisch beschrieben hast):

Du hast 11 Knoten und eine Kante von a, nach b, wenn die Aussage "Knopf a drücken: Knopf b leuchtet" erfüllt ist. Jetzt prüfst du, ob dein Graph kreisfrei ist. Wenn es einen Kreis gibt, dann guck ob er alle Knoten enthält, dann kannst du diesen benutzen. Wenn nicht, dann suchst du nach einer topologischen Ordnung im Graph, also eine Ordnung k1 < k2 < k3 < ... < k11 von Knoten, sodass gilt: Wenn du Knopf 1 drückst, kannst du Knopf 2 drücken, also Knopf 3 usw. bis Knopf 11. Dafür gibt es genügende Algorithmen, Wikipedia (https://de.wikipedia.org/wiki/Topologische\_Sortierung#Algorithmus) hilft weiter ;)

LG

Kommentar von Roach5 ,

Anmerkung: In deinem Beispiel hast du einfach nur einen Kreis mit allen 11 Knoten, also weiß ich gerade nicht wo das Problem liegt.

Kannst du noch einmal genau beschreiben was du willst, wann du einen Knopf drücken kannst, wann nicht, was der Ausgangszustand ist und was der Zustand ist, den du erreichen willst. Sonst kann man nur raten, was du willst.

Ah ich glaube ich sehe was du willst, Knopf a drücken bringt Knopf a zum Leuchten aber wenn Knopf a leuchtet, geht Knopf a aus, richtig?

Kommentar von Roach5 ,

Ah ich glaube ich sehe was du willst, Knopf a drücken bringt Knopf b* zum Leuchten aber wenn Knopf a leuchtet, geht Knopf a aus, richtig?

Kommentar von Goolash ,

Vielen Dank, das schau ich mir mal an.
Ich versuche es noch mal:
Ich habe 11 Knöpfe (Ausgangspunkt: keiner leuchtet). Mein Ziel ist es, dass jeder leuchtet. Wenn ich auf Knopf 1 drücke, leuchtet jedoch nicht Knopf 1, sondern Knopf 5 usw.

1 drücken -> 5 leuchtet(1 nicht)
5 drücken -> 3 leuchtet, 5 geht aus
3 drücken -> 7 leuchtet, 3 geht aus
Usw

Antwort
von Hannibu, 55

Als Abbildung vielleicht? Du Bildes halt die Menge {1,2,...,11} bijektiv auf sich selbst ab

Kommentar von Goolash ,

Danke! Wie macht man das? Matheabi ist schon eine Weile her

Antwort
von Roderic, 32

Die Aufgabe läuft darauf hinaus, in dem gerichteten Graphen deiner Schaltfunktion einen sogenannten

Eulerkreis

https://de.wikipedia.org/wiki/Eulerkreisproblem

zu finden.

Und ja, es existiert einer.

;-)

Kommentar von Roach5 ,

Ich habe mir auch gedacht, dass damit das Problem gelöst ist.

Problem: Wenn du den Kreis entlang gehst (es gibt hier leider nur einen), kommst du am Ende immer wieder damit aus, dass alle Lichter aus sind. Du kommst nämlich für alle i immer am Punkt f(i) im Eulerkreis vorbei, wodurch du irgendwann immer ein eingeschaltetes Licht wieder ausschaltest. Das "Ausschalten" des Lichts ist mit Graphen echt schwer darzustellen, da scheitert das nämlich bei mir.

Kommentar von Roderic ,

Neenee - das haut hin.

Wenn du den Eulerkreis genau einmal entlanglatschst, schaltest du am Ende genau den Knopf an, den du als erstes gedrückt hast.

Der Trick dabei ist:

Den Eulerkreis rückwärts abzulaufen.

Kommentar von Roderic ,

Autsch!

Zum Geier! Du hast ja recht.

Der letzte schaltet immer sich selber aus!

Kommentar von Roach5 ,

Wir wurden veräppelt, es gibt - wenn ich keinen groben Fehler gemacht habe - keine Lösung, siehe meine zweite Antwort.

Kommentar von Roderic ,

Richtig. Es gibt keine Lösung.

Keine passende Antwort gefunden?

Fragen Sie die Community