Binärzahlen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi,
Wie kann ich schnell feststellen, wann eine Zahl im 2er-System
restlos durch 3 teilbar ist? Im Dezimalsystem ist dies ja z.B. dann der
Fall, wenn die Quersumme einer Zahl durch 3 teilbar ist.
Ich muß jedenfalls einen deterministischen endlichen Automaten bauen,
in dessen Sprache eine Binärzahl genau dann vorkommt, wenn sie den
obigen Bedingungen entspricht.
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
genauso wie im 10erSystem die Teilbarkeit durch elf:
die Differenz der Ziffernsummen der "geraden" und "ungeraden" Stellen muß durch 3 Teilbar sein.
|
|
|
| |
|
Hallo Friedrich,
Danke für deine Antwort!
> genauso wie im 10erSystem die Teilbarkeit durch elf:
> die Differenz der Ziffernsummen der "geraden" und
> "ungeraden" Stellen muß durch 3 Teilbar sein.
Ich hab's gerade an einigen Beispielen wie 110110, 1111 und
1100 ausprobiert. Offenbar ist diese Differenz, von der du gesprochen
hast, bei durch 3 teilbaren Zahlen immer 0 (außer für 1). Stimmt das?
Viele Grüße
Karl
|
|
|
| |
|
Halo miteinender
Nein, die Differenz für 101010101 ist 5
Dezimale Darstellung ist ja auch 341, und das ist ersichtlich nicht durch 3 teilbar.
Mit lieben Grüssen
Paul
|
|
|
| |
|
Hallo, Christiane,
ist Dir das Rechnen mit "Resten", "Modulo", ... schon bekannt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:30 Mo 25.10.2004 | | Autor: | Bastiane |
Hallo Friedrich!
Ja, das modulo-rechnen ist mir bekannt, kann man das damit beweisen?
Falls du Zeit hast - würde mich schon interessieren, ist aber nicht wirklich wichtig.
Viele Grüße
|
|
|
| |
|
Hallo, Bastiane,
dann ist mein Tip [mm] $10^{2n} \equiv 1\text{ mod} [/mm] 11$ und [mm] $10^{2n+1} \equiv -1\text{ mod} [/mm] 11$
bzw.
läßt sich für Zahlensysteme mit eine beliebigen natürliche Basis $b > 1$ durch zuende gedachte Polynomdivision zeigen daß
[mm] $b^{2n} \equiv [/mm] 1 [mm] \text{ mod }(b+1)$ [/mm] und [mm] $b^{2n+1} \equiv -1\text{ mod }(b+1)$ [/mm] gelten.
Auch für andere Teiler lassen sich "ganz stur" mit Hilfe der Periodizität der Potenzreste Teilbarkeitsregeln ermitteln.
Gruß F.
|
|
|
|
