Überprüfen Sie, ob eine Zahl durch 3 teilbar [geschlossen]
https://stackoverflow.com/questions/844867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
nimmt Code, um zu bestimmen, ob eine Zahl von 3. Die Eingabe in die Funktion teilbar ist, ist ein Single Bit, 0 oder 1, und die Ausgabe 1 sein soll, wenn die Anzahl der bisher empfangen ist binäre Darstellung einer Zahl durch 3 teilbar, sonst Null.
Beispiele:
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
Dies basiert auf einem Interview Frage. Ich bitte um eine Zeichnung von Logikgattern, aber da dieses Stackoverflow Ich werde jede Codierung Sprache akzeptieren. Bonuspunkte für eine Hardware-Implementierung (verilog usw.).
Teil eines (leicht). Die erste Eingang ist das MSB
Teil b (ein wenig härter.): Der erste Eingang ist das LSB
Teil c (schwer): Welches ist schneller und kleine, (a) oder (b)? (Nicht theoretisch in dem Big-O Sinne, aber praktisch schneller / kleiner.) Nun nehmen Sie die langsame / größerer und macht es so schnell / klein wie die schnell / kleinere.
Lösung
Heh
Zustandstabelle für LSB:
S I S' O
0 0 0 1
0 1 1 0
1 0 2 0
1 1 0 1
2 0 1 0
2 1 2 0
Erläuterung: 0 ist durch drei teilbar ist. 0 << 1 + 0 = 0. Wiederholen Sie mit S = (S << 1 + I) % 3 und O = 1 wenn S == 0.
Zustandstabelle für MSB:
S I S' O
0 0 0 1
0 1 2 0
1 0 1 0
1 1 0 1
2 0 2 0
2 1 1 0
Erläuterung: 0 ist durch drei teilbar ist. 0 >> 1 + 0 = 0. Wiederholen Sie mit S = (S >> 1 + I) % 3 und O = 1 wenn S == 0.
S' unterscheidet sich von oben, sondern O funktioniert auf die gleiche, da S' 0 für die gleichen Fälle (00 und 11). Da O die in beiden Fällen gleich ist, O_LSB = O_MSB, so als kurz zu machen MSB als LSB, oder umgekehrt, nur um die kürzeste von beiden verwenden.
Andere Tipps
Es gibt ein ziemlich bekannter Trick zur Bestimmung, ob eine Zahl ein Vielfaches von 11 ist, durch abwechselndes Addieren und seine Dezimalstellen subtrahiert wird. Wenn die Nummer, die Sie am Ende bekommen ein Vielfaches von 11 ist, dann ist die Zahl, die Sie mit begann ist auch ein Vielfaches von 11:
47278 4 - 7 + 2 - 7 + 8 = 0, multiple of 11 (47278 = 11 * 4298) 52214 5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)
Wir können den gleichen Trick in Binärzahlen gelten. Eine binäre Zahl ist ein Vielfaches von 3, wenn und nur dann, wenn die alternierende Summe seiner Bits ist auch ein Vielfaches von 3:
4 = 100 1 - 0 + 0 = 1, not multiple of 3 6 = 110 1 - 1 + 0 = 0, multiple of 3 78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3 109 = 1101101 1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3
Es macht keinen Unterschied, ob Sie mit dem MSB oder LSB, so dass die folgenden Python-Funktion funktioniert genauso gut in beiden Fällen starten. Es dauert einen Iterator, der die Bits einer nach dem anderen zurückgibt. multiplier wechselt zwischen 1 und 2 statt 1 und -1 zu vermeiden, dass die Modulo einer negativen Zahl.
def divisibleBy3(iterator):
multiplier = 1
accumulator = 0
for bit in iterator:
accumulator = (accumulator + bit * multiplier) % 3
multiplier = 3 - multiplier
return accumulator == 0
Hier ... etwas Neues ... wie zu überprüfen, ob eine binäre Zahl von beliebiger Länge (sogar Tausende von Stellen) durch 3 teilbar ist.
-->((0))<---1--->()<---0--->(1) ASCII representation of graph
Aus dem Bild.
- Sie beginnen im Doppelkreis.
- Wenn Sie eine Eins oder eine Null erhalten, wenn die Ziffer innerhalb des Kreises ist, dann bleiben Sie in diesem Kreis. Allerdings, wenn die Ziffer auf einer Linie ist, dann fahren Sie über die Linie.
- Wiederholen Sie Schritt zwei bis alle Ziffern sind verzehrtem.
- Wenn Sie schließlich im Doppelkreis am Ende dann die binäre Zahl durch 3 teilbar ist.
Sie können dies auch für durch 3 teilbar Erzeugung von Zahlen verwenden Und ich würde es nicht Bild schwer sein, dies in eine Schaltung zu konvertieren.
1 Beispiel der Grafik mit ...
11000000000001011111111111101 durch 3 teilbar ist (endet wieder im Doppelkreis nach oben)
Versuchen Sie es selbst.
Sie können auch tun Ähnliche Tricks für 10 MOD durchgeführt wird, für wenn Binärzahlen in Basis Umwandlung 10 Zahlen. (10 Kreise, die jeweils verdoppelt eingekreisten und stellen die Werte 0 bis 9 aus dem resultierenden modulo)
EDIT:. Dies ist für Ziffern links nach rechts bewegt, ist es nicht schwer, die Finite-State-Maschine zu ändern, obwohl die umgekehrte Sprache zu akzeptieren
Hinweis: In der ASCII-Darstellung des Graphen () bezeichnet einen einzigen Kreis und (()) bezeichnet einen Doppelkreis. In endlichen Automaten sind diese Zustände genannt, und der Doppelkreis ist der Zustand annehmen (der Zustand, der durch drei seine schließlich teilbar bedeutet)
Hier ist ein einfacher Weg, um es von Hand zu tun. Da 1 = 2 2 mod 3, erhalten wir 1 = 2 2 n mod 3 für jede positive ganze Zahl ist. Außerdem 2 = 2 2n + 1 mod 3. Daher kann man bestimmen, ob eine ganze Zahl von 3 durch Zählen der 1-Bits an den ungeraden Bitpositionen, multiplizieren diese Zahl durch 2, fügt die Anzahl von 1- teilbar Bits sogar Bit posistions füge sie das Ergebnis und prüfen, ob das Ergebnis durch 3 teilbar ist.
Beispiel: 57 10 = 111001 2 . Es gibt 2 Bits an den ungeraden Positionen, und 2 Bits an geraden Positionen. 2 * 2 + 2 = 6 ist, durch 3 teilbar 57 daher durch 3 teilbar ist.
Hier ist auch ein Gedanke zu Frage c Lösung). Wenn man die Bitreihenfolge einer binären ganzen Zahl invertiert dann alle Bits bleiben bei geraden / ungeraden Positionen oder alle Bits ändern. Daher Invertieren der Reihenfolge der Bits einer ganzen Zahl n ergibt, ist eine ganze Zahl, die von 3, wenn und nur wenn n teilbar ist durch 3. Daher für jede Frage Lösung teilbar ist a) arbeitet ohne Änderungen für die Frage b) und umgekehrt. Hmm, vielleicht könnte dies helfen, herauszufinden, welchen Ansatz ist schneller ...
Sie müssen alle Berechnungen tun Arithmetik Modulo 3. Verwendung Dies ist die Art und Weise
MSB:
number=0
while(!eof)
n=input()
number=(number *2 + n) mod 3
if(number == 0)
print divisible
LSB:
number = 0;
multiplier = 1;
while(!eof)
n=input()
number = (number + multiplier * n) mod 3
multiplier = (multiplier * 2) mod 3
if(number == 0)
print divisible
Dies ist allgemeine Idee ...
Nun Ihrerseits ist zu verstehen, warum Das ist richtig.
Und ja, tun Hausaufgaben selbst;)
Die Idee ist, dass die Zahl beliebig lange wachsen kann, was bedeutet, dass Sie mod 3 hier nicht verwenden können, da Ihre Nummer über die Kapazität Ihrer integer Klasse wachsen wird.
Die Idee ist zu bemerken, was die Anzahl geschieht. Wenn Sie Bits nach rechts hinzufügen, was Sie eigentlich tun, ist ein Bit nach links verschiebt und das Hinzufügen des neuen Bit.
Umschalt-links ist das gleiche wie mit 2 multipliziert, und das Hinzufügen des neuen Bit wird entweder das Hinzufügen 0 oder 1. Unter der Annahme, die wir von 0 gestartet, können wir dies auf der Modulo-3 der letzten Nummer rekursiv basierte tun.
last | input || next | example
------------------------------------
0 | 0 || 0 | 0 * 2 + 0 = 0
0 | 1 || 1 | 0 * 2 + 1 = 1
1 | 0 || 2 | 1 * 2 + 0 = 2
1 | 1 || 0 | 1 * 2 + 1 = 0 (= 3 mod 3)
2 | 0 || 1 | 2 * 2 + 0 = 1 (= 4 mod 3)
2 | 1 || 2 | 2 * 2 + 1 = 2 (= 5 mod 3)
Nun wollen wir sehen, was passiert, wenn man ein wenig nach links hinzuzufügen. Beachten Sie zunächst, dass:
2 2 N mod 3 = 1
und
2 2n + 1 = 2 mod 3
So, jetzt haben wir entweder auf 1 oder 2 auf die Mod basiert auf hinzufügen, wenn die aktuelle Iteration gerade oder ungerade ist.
last | n is even? | input || next | example
-------------------------------------------
d/c | don't care | 0 || last | last + 0*2^n = last
0 | yes | 1 || 0 | 0 + 1*2^n = 1 (= 2^n mod 3)
0 | no | 1 || 0 | 0 + 1*2^n = 2 (= 2^n mod 3)
1 | yes | 1 || 0 | 1 + 1*2^n = 2
1 | no | 1 || 0 | 1 + 1*2^n = 0 (= 3 mod 3)
1 | yes | 1 || 0 | 2 + 1*2^n = 0
1 | no | 1 || 0 | 2 + 1*2^n = 1
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
sollte nicht die letzte Eingabe 12 werden, oder bin ich Missverständnis der Frage?
Eigentlich wäre die LSB-Methode tatsächlich diese einfacher machen. In C:
MSB-Methode:
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
unsigned value = 0;
char *p = input;
if (*p == '1') {
value &= 1;
}
p++;
while (*p) {
if (*p != ',') {
value <<= 1;
if (*p == '1') {
ret &= 1;
}
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
LSB-Methode:
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
unsigned value = 0;
unsigned mask = 1;
char *p = input;
while (*p) {
if (*p != ',') {
if (*p == '1') {
value &= mask;
}
mask <<= 1;
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
Persönlich habe ich eine harte Zeit, eine davon zu glauben, an den anderen deutlich anders sein wird.
ich glaube, Nathan Fellman für einen Teil eines auf dem richtigen Weg ist und b (außer b ein zusätzliches Stück Staat braucht: Sie den Überblick behalten muß aus, wenn Ihre Ziffernposition gerade oder ungerade ist).
I denkt der Trick für Teil C wird negiert den last Wert bei jedem Schritt. D. h 0 geht auf 0, 1 geht zu 2 und 2 geht auf 1.
Eine Zahl ist durch 3 teilbar, wenn die Summe davon Ziffern ist durch 3 teilbar ist
So können Sie die Ziffern addieren und die Summe erhalten:
- , wenn die Summe größer oder gleich 10 Verwendung der gleichen Methode
- wenn es 3, 6, 9 dann ist es teilbar
- , wenn die Summe anders als 3, 6, 9, dann ist es nicht teilbar
