Rolf B: Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

Beitrag lesen

Hallo Gunnar,

Ich bin vielleicht der letzte, der’s verstanden hat; aber ich glaube, jetzt hab auch ich es.

Nein, bist Du nicht, ich glaube, ich war's. Aber dafür versuche ich jetzt mal, es aufzuschreiben, am Beispiel der 7.

Man braucht für einen solchen Automaten einen Startzustand sowie einen Zustand R0 bis Rn für jeden möglichen Divisionsrest. Die Werte der Übergangsfunktion des Startzustandes sind identisch mit denen des Endzustandes. Er existiert nur, damit das leere Wort nicht als "teilbar durch N" akzeptiert wird. Endzustand ist logischerweise R0.

Man muss nun herausfinden, wie sich k und 10k mod 7 verhalten:

Wenn $$k \equiv n \pmod 7$$, dann ist $$10k = 7k+3k \equiv 0 + 3n \pmod 7$$. Mit $$p = (3n \bmod 7)$$ erhält man also den Status Rp, der bei Antreffen der Ziffer 0 auf den Rn folgen muss. Die übrigen ergeben sich fortlaufend automatisch: Zum Beispiel ist p=5 für n=4, damit hat der Zustand R4 die Übergänge

0,7 -> R5
1,8 -> R6
2,9 -> R0
  3 -> R1
  4 -> R2
  5 -> R3
  6 -> R4

Oder - aus FLACI kopiert, diese Deltafunktion:

 δ  0   1   2   3   4   5   6   7   8   9
R0	R0	R1	R2	R3	R4	R5	R6	R0	R1	R2
R1	R3	R4	R5	R6	R0	R1	R2	R3	R4	R5
R2	R6	R0	R1	R2	R3	R4	R5	R6	R0	R1
R3	R2	R3	R4	R5	R6	R0	R1	R2	R3	R4
R4	R5	R6	R0	R1	R2	R3	R4	R5	R6	R0
R5	R1	R2	R3	R4	R5	R6	R0	R1	R2	R3
R6	R4	R5	R6	R0	R1	R2	R3	R4	R5	R6

Ob das bei zweistelligen Teilern genauso funktioniert? Wenn $$k \equiv n \pmod{37}$$, was ist dann mit 10k?

$$10k = 37k - 27k \equiv 0 - 27n \pmod{37}$$, d.h. für $$p=(-27n) \bmod 37$$ erhält man zum Status n den Folgestatus p bei Antreffen der Ziffer 0. Dabei ist der Rest so zu bestimmen, dass er nicht negativ ist, d.h. es muss beispielsweise $$-27 : 37 = -1$$ mit Rest 10 gelten.

Auf den Zustand R1 müsste bei Antreffen der Ziffer 0 also der Zustand $$-27\cdot 1 \bmod{37}= 10$$ folgen, demzufolge bei Antreffen der 4 der Zustand R14. Und auf R14 der Zustand $$-27\cdot 14 \bmod{37}=29$$ für Ziffer 0, demzufolge R0 für Ziffer 8. Kurzer Blick auf den Taschenrechner: $$148=4\cdot 37$$ - scheint zu passen.

Ich bin total perplex, das hatte ich für unmöglich gehalten.

Rolf

--
sumpsi - posui - clusi
0 105

Informatik zum Jahresanfang

Gunnar Bittersmann
  • informatik
  1. 0
    Matthias Apsel
    1. 0
      Gunnar Bittersmann
  2. 0
    Gunnar Bittersmann
  3. 0

    Informatik zum Jahresanfang – Zusatzaufgabe

    Gunnar Bittersmann
    1. 0
      Matthias Apsel
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            Gunnar Bittersmann
            1. 0
              Gunnar Bittersmann
              • menschelei
    2. 0

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

      Gunnar Bittersmann
      1. 0
        dedlfix
        1. 0
          Gunnar Bittersmann
          1. 0
            dedlfix
            1. 0
              Gunnar Bittersmann
  4. 0
    Gunnar Bittersmann
    1. 0
      Matthias Apsel
  5. 0

    Informatik zum Jahresanfang – Auflösung für 4

    Gunnar Bittersmann
    1. 0
      Matthias Apsel
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            Rolf B
    2. 0
      Gunnar Bittersmann
      • typografie
  6. 0

    Informatik zum Jahresanfang – noch mehr Teiler

    Gunnar Bittersmann
    1. 0
      Rolf B
      1. 0
        Matthias Apsel
        • informatik
        • mathematik
        1. 0
          Gunnar Bittersmann
          1. 0
            Matthias Apsel
          2. 0

            Informatik zum Jahresanfang – Auflösung für 7

            Gunnar Bittersmann
    2. 0

      Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

      dedlfix
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            Gunnar Bittersmann
            1. 0
              Matthias Apsel
              1. 0
                Gunnar Bittersmann
                1. 0
                  Matthias Apsel
                  1. 0
                    Gunnar Bittersmann
        2. 0
          dedlfix
          1. 0
            Gunnar Bittersmann
            1. 0
              dedlfix
            2. 0
              MudGuard
              1. 0
                dedlfix
                1. 0
                  MudGuard
        3. 0
          Rolf B
          1. 0
            Matthias Apsel
            1. 0
              Rolf B
              1. 0
                Matthias Apsel
                1. 0
                  Matthias Apsel
            2. 0
              Matthias Apsel
              • mathematik
        4. 0

          Informatik zum Jahresanfang – Auflösung für n

          Gunnar Bittersmann
          1. 0
            Gunnar Bittersmann
            1. 0
              Gunnar Bittersmann
              1. 0
                Matthias Apsel
                • mathematik
                1. 0
                  Matthias Apsel
          2. 0
            Gunnar Bittersmann
            • informatik
            • javascript
            1. 0
              Doktor Seltsam
              1. 0
                Gunnar Bittersmann
    3. 0
      Gunnar Bittersmann
      1. 0
        dedlfix
        1. 0
          Gunnar Bittersmann
        2. 0
          Rolf B
          1. 0
            dedlfix
      2. 0
        Gunnar Bittersmann
    4. 0

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

      Gunnar Bittersmann
      1. 0

        Informatik zum Jahresanfang – Auflösung für 9

        Gunnar Bittersmann
        • informatik
        • javascript
        • svg
        1. 0
          dedlfix
          1. 0
            Gunnar Bittersmann
        2. 0
          Gunnar Bittersmann
  7. 0

    Informatik zum Jahresanfang – noch eine Variation

    Gunnar Bittersmann
    1. 0
      dedlfix
      1. 0
        Gunnar Bittersmann
        1. 0
          dedlfix
          1. 0
            Gunnar Bittersmann
            1. 0
              dedlfix
              1. 0
                Gunnar Bittersmann
              2. 0
                Rolf B
                1. 0
                  Gunnar Bittersmann
              3. 0
                Matthias Apsel
                1. 0
                  dedlfix
                  1. 0
                    Matthias Apsel
                    1. 0
                      dedlfix
                      1. 0
                        Matthias Apsel
                        1. 0
                          Gunnar Bittersmann
                          1. 0
                            dedlfix
                            1. 0
                              Rolf B
                            2. 0
                              Gunnar Bittersmann
                              1. 0
                                Matthias Apsel
                                • menschelei
                            3. 0
                              Matthias Apsel
    2. 0
      Rolf B
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            dedlfix
            1. 0
              Matthias Apsel
              1. 0
                Matthias Apsel
                1. 0
                  Gunnar Bittersmann
                  1. 0
                    Matthias Apsel
                    1. 0
                      Rolf B
                    2. 0
                      Gunnar Bittersmann
                    3. 0
                      Gunnar Bittersmann
                2. 0
                  Gunnar Bittersmann
                  • grafik
                  • grafik
                  • zu diesem forum
                  1. 0
                    Christian Kruse
    3. 0
      Gunnar Bittersmann
      1. 0
        Gunnar Bittersmann
  8. 2
    Gunnar Bittersmann
  9. 1
    Gunnar Bittersmann