Heim  >  Artikel  >  Was bedeutet Mod im Algorithmus?

Was bedeutet Mod im Algorithmus?

青灯夜游
青灯夜游Original
2020-08-29 12:43:4638650Durchsuche

Im Algorithmus bedeutet mod, dass man den Modul nimmt, also den Rest nimmt. Die Mod-Operation, also die Restoperation, ist eine Operation, die den Rest der Division einer ganzen Zahl x durch eine andere ganze Zahl y in ganzzahligen Operationen ermittelt, ohne den Quotienten der Operation zu berücksichtigen.

Was bedeutet Mod im Algorithmus?

Die Mod-Operation, also die Restoperation, ist eine Operation, die den Rest der Division einer ganzen Zahl x durch eine andere ganze Zahl y in ganzzahligen Operationen ermittelt, ohne den Quotienten der Operation zu berücksichtigen. In der Computerprogrammierung gibt es eine MOD-Operation und ihr Format ist: mod(nExp1,nExp2), was der Rest nach der Division zweier numerischer Ausdrücke ist.

Modulo p-Operationseditor

Gegeben eine positive ganze Zahl p und eine beliebige ganze Zahl n, muss es eine Gleichung geben

n = kp + r, wobei k und r ganze Zahlen sind und 0 ≤ r < der Quotient von n dividiert durch p, und r ist der Rest von n dividiert durch p.

Für positive ganze Zahlen p und ganze Zahlen a, b ist die folgende Operation definiert:

Moduloperation: a mod p stellt den Rest der Division von a durch p dar.

Addition modulo p: (a + b) mod p, das Ergebnis ist der Rest der arithmetischen Summe von a+b dividiert durch p, also (a+b) = kp +r, dann (a+b) mod p =r.

Modul p-Subtraktion: (a-b) mod p, das Ergebnis ist der Rest der arithmetischen Differenz von a-b dividiert durch p.

Multiplikation modulo p: (a × b) mod p, das Ergebnis ist der Rest der arithmetischen Multiplikation von a × b dividiert durch p.

Es kann festgestellt werden, dass die Modulo-p-Operation viele ähnliche Regeln wie die vier gewöhnlichen arithmetischen Operationen aufweist, wie zum Beispiel:

Assoziativgesetz
((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p
((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p
kommutativ Gesetz
(a + b) mod p = (b+a) mod p
(a × b) mod p = (b × a) mod p
Distributivgesetz
( (a +b )mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p
(a×b) mod c=(a mod c * b mod c ) mod c
(a+b) mod c=(a mod c+ b mod c) mod c
(a-b) mod c=(a mod c- b mod c) mod c

Einfach Beweis davon A-Formel:

((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p

Angenommen

a = k1*p + r1

b = k2 *p + r2

c = k3*p + r3

a+b = (k1 + k2) p + (r1 + r2)

Wenn (r1 + r2) >= p , dann

( a+ b) mod p = (r1 + r2) -p

Sonst

(a+b) mod p = (r1 + r2)

Und führen Sie dann die Modulo-p-Summenoperation mit c aus, das Ergebnis von

ist r1 + r2 + Der Rest der arithmetischen Summe von r3 dividiert durch p.

Das gleiche Ergebnis kann durch Berechnung der rechten Seite erzielt werden, und der Beweis wird erhalten.

Gleich modulo p

Wenn zwei Zahlen a und b einen mod p = b mod p erfüllen, dann werden sie als gleich modulo p bezeichnet, bezeichnet als

a ≡ b (mod p)

Das kann Dies kann bewiesen werden, wenn a und b a = kp + b erfüllen, wobei k eine ganze Zahl ist.

Für Gleichheit modulo p und Multiplikation modulo p gilt eine völlig andere Regel als die vier Rechenoperationen. Wenn c in den vier arithmetischen Operationen eine Ganzzahl ungleich 0 ist, kann

ac = bc als a =b

erhalten werden. Bei der Modulo-p-Operation existiert diese Beziehung jedoch nicht, zum Beispiel:

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

aber

3 mod 9 = 3

6 mod 9 =6

Theorem (Eliminationsgesetz): Wenn gcd(c, p) = 1, dann kann aus ac ≡ bc mod p abgeleitet werden a ≡ (b mod p)

Beweis:

Weil ac ≡ bc (mod p)

also ac = bc + kp, also c(a-b ) = kp

Da c und p keine anderen gemeinsamen Faktoren als 1 haben, muss eine der folgenden beiden Bedingungen erfüllt sein, damit die obige Formel wahr ist

1) c kann k teilen

2) a = b

Wenn 2 nicht wahr ist, dann c|kp

Da c und p keine gemeinsamen Faktoren haben, ist es offensichtlich, dass c|k, also k = ck'

Daher kann c(a-b)=kp als c ausgedrückt werden (a-b) =ck'p

Daher ist a-b = k'p, wir erhalten a ≡ b (mod p)

Wenn a = b, dann ist a ≡ b mod p offensichtlich etabliert

Bewiesen

Für weitere verwandte Kenntnisse , besuchen Sie bitte: Chinesische PHP-Website!

Das obige ist der detaillierte Inhalt vonWas bedeutet Mod im Algorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn