Հիմնական նյութ

Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 2

Դաս 5: Մոդուլյար թվաբանություն

Ինչ է մոդուլյար թվաբանությունը

Մոդուլյար մաթեմատիկա. ներածություն

Երկու ամբողջ թիվ բաժանելիս ստանում ենք հավասարում, որն այսպիսի տեսք ունի․

$\frac{A}{B} = Q, մնացորդ R$ ‍

A

-ն բաժանելին է

B

-ն բաժանարարն է

Q

-ն քանորդն է

R

-ը մնացորդն է

Երբեմն մեզ հետաքրքրում է միայն այն մնացորդը, որը ստանում ենք

A

-ն

B

-ի բաժանելիս։
Այս դեպքերի համար կա գործողություն, որը կոչվում է մոդուլո (կրճատ՝ mod)։

Նույն

A

-ն,

B

-ն,

Q

-ն ու

R

-ն օգտագործելով՝ կստանանք

A mod B = R

Ասում ենք այսպես՝

A

մոդուլո

B

-ն հավասար է

R

, որտեղ

B

-ն մոդուլուսն է։

Օրինակ՝

$\begin{array}{rcl} \frac{13}{5} & = & 2, մնացորդ 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

Մոդուլուսը պատկերացրու ժամացույցներով

Ի՞նչ կպատահի, երբ թվերն անընդհատ մեկով մեծացնենք ու ամեն անգամ բաժանենք 3-ի։

$\begin{array}{rcl} \frac{0}{3} & = & 0, մնացորդ 0 \\ \frac{1}{3} & = & 0, մնացորդ 1 \\ \frac{2}{3} & = & 0, մնացորդ 2 \\ \frac{3}{3} & = & 1, մնացորդ 0 \\ \frac{4}{3} & = & 1, մնացորդ 1 \\ \frac{5}{3} & = & 1, մնացորդ 2 \\ \frac{6}{3} & = & 2, մնացորդ 0 \end{array}$ ‍

Մնացորդները սկսվում են 0-ից և ամեն անգամ մեծանում 1-ով, մինչև թիվը հասնում է բաժանելիից մեկով փոքր արժեքի։ Դրանից հետո հաջորդականությունը կրկնվում է։

Սա նկատելով՝ մենք արդեն կարող ենք մոդուլոն պատկերացնել՝ շրջաններ օգտագործելով։

Շրջանի վերևում գրում ենք 0 և ժամսլաքի ուղղությամբ գրում ենք 1, 2, ... մինչև մոդուլուսից մեկով փոքր թիվը։

Օրինակ՝ այն ժամացույցը, որի 12-ի փոխարեն գրված է 0, կլինի 12 մոդուլուսով շրջանը։

A mod B

-ն գտնելու համար մենք պետք է հետևենք այս քայլերին․

Կառուցիր $B$ ‍ չափի այսպիսի ժամացույց:
Սկսիր 0-ից և ժամացույցի շուրջը շարժվիր $A$ ‍ քայլով:
Որտեղ կանգ առնենք, դա կլինի մեր լուծումը:

(Եթե թիվը դրական է, գնում ենք ժամսլաքի ուղղությամբ, եթե թիվը բացասական է, գնում ենք ժամսլաքին հակառակ ուղղությամբ)։

Օրինակներ

$8 mod 4 = ?$ ‍

4 մոդուլուսի դեպքում ժամացույցն ունենում է 0, 1, 2, 3 թվեր։
Սկսում ենք 0-ից և ժամսլաքի ուղղությամբ շարժվում 8 քայլ՝ 1, 2, 3, 0, 1, 2, 3, 0։

Մենք կանգ առանք 0-ի վրա, հետևաբար

8 mod 4 = 0

$7 mod 2 = ?$ ‍

2 մոդուլուսի դեպքում ժամացույցն ունենում է 0, 1 թվեր։
Սկսում ենք 0-ից և ժամսլաքի ուղղությամբ շարժվում 7 քայլ՝ 1, 0, 1, 0, 1, 0, 1։

Մենք կանգ առանք 1-ի վրա, հետևաբար

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

3 մոդուլուսի դեպքում ժամացույցն ունենում է 0, 1, 2 թվեր։
Սկսում ենք 0-ից և ժամսլաքին հակառակ ուղղությամբ շարժվում 5 քայլ (5-ը բացասական է)՝ 2, 1, 0, 2, 1։

Մենք կանգ առանք 1-ի վրա, հետևաբար

- 5 mod 3 = 1

Ամփոփում

Եթե ունենք

A mod B

, և

A

-ն մեծացնում ենք $B$ ‍-ի բազմապատիկով, մենք կանգ կառնենք նույն կետում՝

$A mod B = (A + K \cdot B) mod B$ ‍ կամայական $K$ ‍ ամբողջ թվի համար։

Օրինակ՝

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

Նշումներ ընթերցողի համար

mod-ը ծրագրավորման լեզուներում և հաշվիչներում

Բազում ծրագրավորման լեզուներ և հաշվիչներ ունեն mod գործողությունը՝ ներկայացված % նշանով։ Բացասական թվի դեպքում որոշ լեզուներ տալիս են բացասական արժեք։
Օրինակ՝

-5 % 3 = -2։

Մոդուլյար բաղդատում

Դու կարող ես այսպիսի արտահայտություն տեսնել․

$A \equiv B (mod C)$ ‍

Սա նշանակում է, որ

A

-ն խիստ հավասար է

B

modulo

C

-ին։ Դա նման է մեր օգտագործած արտահայտություններին, բայց նույնը չեն։

Հաջորդ հոդվածում կբացատրենք, թե ինչ է դա և թե ինչպես է կապված վերևի արտահայտությունների հետ։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Մուտք գործել

Դասակարգել ըստ

Առայժմ հրապարակումներ չկան։

Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում:

Համակարգչային գիտություն