Foren » 30. BwInf

• PaulJJ

  

  • 45 Beiträge
   

  2. Dezember 2011 13:47:06 CET

  Na dann fange ich mal an:

   

  Mir ist aufgefallen, dass

  a) die Reihenfolge, in der die Taster gedrückt werden, nicht entscheidend ist und

  b) jeder Taster maximal 1 Mal gedrückt werden muss

   

  Damit bleiben insgesamt 2^n mögliche Kombinationen bei n Schaltern/Lampen. Diese habe ich alle durchprobiert.

   

  Wie habt ihr es gemacht?

   

  Paul

• mah b

  

  • 2 Beiträge
   

  2. Dezember 2011 18:54:00 CET

  Man kann den Lampenzustand als Bit-Folge interpretieren.

  Nun lässt sich jeder Schalter selbst als Bitmaske der Lampen, die er umschaltet, darstellen, soadas Lampenzustand XOR Schaltermaske = Neuer Zustand.

  Daraus ergeben sich auch deine beiden Eigenschaften. a, XOR kommutativ ist, b, weil es eine Involution ist.

   

  Dies lässt sich nun in die einzelnen Stelle zu einer Art LGS zusammenbauen, welches dann per Gauss-Jordan gelöst werden kann.

   

  Es lässt sich auch dadurch schön feststellen, ob eine Schaltung funktioniert, indem überpüft wird, ob das LGS unterbestimmt ist.

   

  Damit ist der Aufwand nicht mehr exponentiell, sondern kubisch.

  
  Dieser Beitrag wurde am 2. Dezember 2011 18:55:06 CET von mah b bearbeitet
• PaulJJ

  

  • 45 Beiträge
   

  3. Dezember 2011 08:58:20 CET

  Deine Idee habe ich soweit verstanden, aber kannst du mir mal ein Beispiel geben, wie du das LGS aufstellst, sodass es z.B. mit Gauss-Jordan lösbar ist?
  
  Paul
• mah b

  

  • 2 Beiträge
   

  3. Dezember 2011 10:21:08 CET

  OK, nehmen wir an, es gibt drei Schalter.

  Schalter 1 schaltet Lampe 1 und Lampe 2 an.

  Schalter 2 schaltet Lampe 2 und Lampe 3 an.

  Schalter 3 schaltet Lampe 3 und Lampe 1 an.

  Zu Beginn sind Lampe 1 an.

   

  Dann ist der

  Lampen-Bitstring 100

  Schalter 1: 110

  Schalter 2: 011

  Schalter 3: 101

   

  Dies wird jetzt auf die einzelnen Stellen umgelegt.

  s1, s2, s3 sind die Variablen, ob der Schalter gedrückt werden muss.

   

  1. Lampe: (1 AND s1) XOR (0 AND s2) XOR (1 AND s3) = (1 [Endzustand]) XOR (1 [Startzustand])

  2. Lampe (1 AND s1) XOR (1 AND s2) XOR (0 AND s3) = 1 XOR 0

  3. Lampe (0 AND s1) XOR (1 AND s2) XOR (1 AND s3) = 1 XOR 0

   

  Die Matrix:

  1 0 1 | 0

  1 1 0 | 1

  0 1 1 | 1

   

  Und jetzt Gauss-Jordan mit XOR als Elimination:

   

  2. Zeile XOR 1. Spalte, um in der 1. Spalte oben nur die 1 stehen zu haben.

   

  1 0 1 | 0

  0 1 1 | 1

  0 1 1 | 1

   

  Offensichtlich ist das unterbestimmt, geht aber auf, weil es nicht auf 0 0 0 | 1 in einer Spalte hinausläuft.

   

  3. Zeile XOR 2. Zeile.

   

  1 0 1 | 0

  0 1 1 | 1

  0 0 0 | 0

   

  Einen Wert für s3 aussuchen: s3 = 0

   

  Dann ist s1 XOR 0 = 0 => s1 = 0

  Und s2 XOR 0 = 1 => s2 = 1

   

  Somit muss (Überraschung) einmal der zweite Schalter gedrückt werden.