Informatik zum Jahresanfang – noch mehr Teiler

[dedlfix]

Tach!

Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt.

Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt. Das Diagramm ersparen wir uns. Wir sind zu höheren Zielen berufen.

Auch der ensteht, wenn ich nach "meinem" Prinzip vorgehe, mit 9 plus 2 Zuständen. Allerdings konnte der Flaci den auf drei Zustände minimieren. Die Frage wäre also, warum das passieren kann. Hängt es mit dem Dezimalsystem zusammen?

Hier mal die komplette Beschreibung "meines" Prinzips:

Für das Prinzip braucht man keine mathematischen Teilungsregeln zu kennen. Der erste Schritt ist, alle Zahlen von 0 bis exklusive 10 × (n + 1) aufzuschreiben, am besten in 10er-Gruppen. Also beim 3er Automaten bis 39, beim 6er bis 69, etc. Dann markiert man sich alle Vielfachen. Man sieht nun, welche 10er nach der 0 nicht markiert sind. Für diese erstellt man Zustände und nummeriert sie von 1 an aufwärts. Den Startzustand benennt man mit 0 und fügt dann noch einen finiten Zustand benannt mit E hinzu. Man braucht für Primzahlen n Zustände plus den E, bei Nicht-Primzahlen sind es weniger, weil Vielfache von ihnen durch 10 teilbar sind. Nun zeichnet man für alle Vielfachen (inklusive 0) bis zum 10-Fachen die Wege zum E ein. Dazu kommen noch die Wege, die von E auf sich selbst zeigen. Das ist auf alle Fälle die 0 und - bei allen n, die kleiner als 10 sind - alle Endziffern von Vielfachen bis zum nächsten Zehner. Also, beim 3er Automaten sind es 0, 3, 6 und 9 wegen 30, 33, 36 und 39, beim 6er sind es die 0 und 6 wegen 60 und 66. Anschließend wechselt man zur Übergangstabelle. Die Zustände sollten von 0 bis E untereinander stehen. Flaci sortiert sie aber nicht natürlich, weswegen Zustände >= 10 nicht richtig platziert sind. Jedenfalls hat man in der ersten Zeile den Zustand 0 (oder Startzustand) und da ist bereits bei Eingabe der Ziffer 0 (obere Reihe) ein E eingetragen. Dann fügt man nur noch aufsteigend mit 1 nach dem E beginnend alle Zustände ein. Wenn keiner mehr übrig ist, geht es mit 0 beginnend weiter. Es sei denn, es steht bereits ein E in dem Feld, dann geht es im darauf folgenden mit 1 weiter. Ist die Zeile voll, setzt man in der nächsten (numerisch aufsteigend) fort bis inklusive E-Zeile. Fertig ist der Automat.

dedlfix.