Gunnar Bittersmann: Informatik zum Jahresanfang – Auflösung für n

Beitrag lesen

@@Gunnar Bittersmann

… und damit haben wir unseren Automaten:

$$\left( S, s_{-0}, \Sigma, \delta, F \right) = \left( {s_{-0}, s_0, s_1, \ldots, s_{n-1}}, ;; s_{-0}, ;; {0, 1, \ldots, 9}, ;; \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n, ;; {s_0} \right)$$

FWIW, ich hab das Ding mal in JavaScript implementiert. Na, nicht genau den Automaten, der die Teilbarkeit durch einen (den) Endzustand anzeigt, sondern einen, der bei jeder Eingabe „teilbar“ (W wie wahr) bzw. „nicht teilbar“ (F fie falsch) ausgibt – wie irgendwo in den Untiefen dieses Threads schon mal erwähnt. Da die Ausgabe zu einer Eingabe erfolgt, muss man dann nicht zwischen den Zuständen s₋₀ und s₀ unterscheiden und der Automat kommt mit n Zuständen aus.

$$\begin{align} \text{Zustandsmenge:} &\ S = {s_0, s_1, \ldots, s_{n-1}}
\text{Startzustand:} &\ s_0
\text{Eingabealphabet:} &\ \Sigma = {0, 1, \ldots, 9}
\text{Ausgabealphabet:} &\ \Gamma = {\mathrm W, \mathrm F}
\text{Übergangsfunktion:} &\ \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n
\text{Ausgabefunktion:} &\ \omega(s_u, d) = \begin{cases} \mathrm W,& \text{wenn } \delta(s_u, d) = s_0, \text{ d.h. wenn } v = (10u + d) \bmod n = 0
\mathrm F,& \text{sonst} \end{cases} \end{align}$$

class DivisibilityFSA
{
	n;
	currentState = 0;
	inputAlphabet = [0,1,2,3,4,5,6,7,8,9];

	constructor(n)
	{
		this.n = n;
	}

	transition = input => this.inputAlphabet.includes(input) ?
		!(this.currentState = (10 * this.currentState + input) % this.n) :
		undefined;
}

In der Kürze liegt die Würze: Eine Zuweisung liefert einen Wert (nämlich den zugewiesenen).
Wenn also für den Index des Folgezustands, d.h. die Restklasse (10 * this.currentState + input) % this.n die falsy 0 rauskommt, wird durch die Negation true zurückgegeben (d.h. „teilbar“).
Kommt ein anderer, ein truthy Wert von 1 bis n − 1 raus, dann false („nicht teilbar“).

Und das nur, wenn die Eingabe aus dem Eingabealphabet ist, ansonsten kommt undefined zurück. Oder wäre null passender?

7er Automat (❤️):

const fsa = new DivisibilityFSA(7);

console.log( fsa.transition(9) ); // false –    9 ist nicht durch 7 teilbar
console.log( fsa.transition(8) ); // true  –   98 ist durch 7 teilbar
console.log( fsa.transition(7) ); // true  –  987 ist durch 7 teilbar
console.log( fsa.transition(6) ); // false – 9876 ist nicht durch 7 teilbar

Mit new DivisibilityFSA(13) schlägt’s dreizehn. Zum Rumspielen

Ich dachte, man könnte currentState und inputAlphabet durch vorangestelltes # privat machen, aber da spielt CodePen nicht mit?

LLAP 🖖

--
„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
0 105

Informatik zum Jahresanfang

  1. 0
    1. 0
  2. 0
  3. 0

    Informatik zum Jahresanfang – Zusatzaufgabe

    1. 0
      1. 0
        1. 0
          1. 0
            1. 0
    2. 0

      Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8

      1. 0
        1. 0
          1. 0
            1. 0
  4. 0
    1. 0
  5. 0

    Informatik zum Jahresanfang – Auflösung für 4

    1. 0
      1. 0
        1. 0
          1. 0
    2. 0
  6. 0

    Informatik zum Jahresanfang – noch mehr Teiler

    1. 0
      1. 0
        1. 0
          1. 0
          2. 0

            Informatik zum Jahresanfang – Auflösung für 7

    2. 0

      Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

      1. 0
        1. 0
          1. 0
            1. 0
              1. 0
                1. 0
                  1. 0
        2. 0
          1. 0
            1. 0
            2. 0
              1. 0
                1. 0
        3. 0
          1. 0
            1. 0
              1. 0
                1. 0
            2. 0
        4. 0

          Informatik zum Jahresanfang – Auflösung für n

          1. 0
            1. 0
              1. 0
                1. 0
          2. 0
            1. 0
              1. 0
    3. 0
      1. 0
        1. 0
        2. 0
          1. 0
      2. 0
    4. 0

      Informatik zum Jahresanfang – Auflösung für 3, 6 und 15

      1. 0

        Informatik zum Jahresanfang – Auflösung für 9

        1. 0
          1. 0
        2. 0
  7. 0

    Informatik zum Jahresanfang – noch eine Variation

    1. 0
      1. 0
        1. 0
          1. 0
            1. 0
              1. 0
              2. 0
                1. 0
              3. 0
                1. 0
                  1. 0
                    1. 0
                      1. 0
                        1. 0
                          1. 0
                            1. 0
                            2. 0
                              1. 0
                            3. 0
    2. 0
      1. 0
        1. 0
          1. 0
            1. 0
              1. 0
                1. 0
                  1. 0
                    1. 0
                    2. 0
                    3. 0
                2. 0
                  1. 0
    3. 0
      1. 0
  8. 2
  9. 1