HOME»基本情報技術者試験掲示板»mod関数について
投稿する
mod関数について [2172]
ティムさん(No.1)
Q, pを2以上の整数とする。任意の整数nに対して、
n = kp + m (0 ≦ m < p)
を満たす整数kとmが一意に存在する。このmをnのpによる剰余といい、
n mod pで表す。( -1000 ) mod 32768に等しくなるものはどれか。
ア： - ( 1000 mod 32768 )
イ： ( -22768 ) mod 32768
ウ： 10000 mod 32768
エ： 22768 mod 32768
（ 引用:受かる！基本情報技術者 午後・アルゴリズム ）
この問題の説明を詳しくお教え名がいますでしょうか？
答えは"エ"です。
n = kp + m (0 ≦ m < p)
を満たす整数kとmが一意に存在する。このmをnのpによる剰余といい、
n mod pで表す。( -1000 ) mod 32768に等しくなるものはどれか。
ア： - ( 1000 mod 32768 )
イ： ( -22768 ) mod 32768
ウ： 10000 mod 32768
エ： 22768 mod 32768
（ 引用:受かる！基本情報技術者 午後・アルゴリズム ）
この問題の説明を詳しくお教え名がいますでしょうか？
答えは"エ"です。
2020.02.21 15:20
メタルさん(No.2)
★FE ブロンズマイスター
メタルさん(No.3)
★FE ブロンズマイスター
Gooで拾った解説を引用します
以下引用
まずは、大原則です。
「Ａ÷Ｂ＝Ｑ余りＲ」⇒「Ａ＝Ｂ×Ｑ＋Ｒ」かつ「|Ｒ| ＜|Ｂ|」
「Ａ÷Ｂ＝Ｑ余りＲ」であれば、必ず「Ａ＝Ｂ×Ｑ＋Ｒ」であり、|Ｒ| ＜|Ｂ| でなければなりません。| | の記号は絶対値を表します（プラスの値はそのまま、マイナスの値はプラスに変えるという意味です）。（例、－３の絶対値は＋３）
さて、ここで問題が生じます。
＜Ａがマイナス、Ｂがプラスのとき＞
たとえば、
ア.（-13)÷5＝-2あまり-3 ⇒ -13 = 5×(-2)＋(-3), |-3|＜|5|
イ.（-13)÷5＝-3あまり2 ⇒ -13 = 5×(-3)＋2, |2|＜|5|
と２通りの答があり、どちらも上の大原則を満たします。
以下引用
まずは、大原則です。
「Ａ÷Ｂ＝Ｑ余りＲ」⇒「Ａ＝Ｂ×Ｑ＋Ｒ」かつ「|Ｒ| ＜|Ｂ|」
「Ａ÷Ｂ＝Ｑ余りＲ」であれば、必ず「Ａ＝Ｂ×Ｑ＋Ｒ」であり、|Ｒ| ＜|Ｂ| でなければなりません。| | の記号は絶対値を表します（プラスの値はそのまま、マイナスの値はプラスに変えるという意味です）。（例、－３の絶対値は＋３）
さて、ここで問題が生じます。
＜Ａがマイナス、Ｂがプラスのとき＞
たとえば、
ア.（-13)÷5＝-2あまり-3 ⇒ -13 = 5×(-2)＋(-3), |-3|＜|5|
イ.（-13)÷5＝-3あまり2 ⇒ -13 = 5×(-3)＋2, |2|＜|5|
と２通りの答があり、どちらも上の大原則を満たします。
2020.02.21 19:22
メタルさん(No.4)
★FE ブロンズマイスター
このとうり、マイナスの割り算だと余りに、2通り答えがあるのです。
コンピュータの世界では、イの方を用いることが多い様です。
検索サイトでキーワード
情報処理 剰余
で探すと色々解説が見つかると思います。
コンピュータの世界では、イの方を用いることが多い様です。
検索サイトでキーワード
情報処理 剰余
で探すと色々解説が見つかると思います。
2020.02.21 19:29
てきとーさん(No.5)
理解しやすくする為に、まず簡単な数字を入れて考えてみます。
n = kp + m (0 ≦ m ＜ p)
17 = 5×3 + 2 (0 ≦ 2 ＜ 3)
「mはnのpによる剰余でありn mod pであらわす」という部分は
「2は17の3による剰余であり17 mod 3であらわす」ですね。
17を3で割ると商は5で余りは2です。
17 mod 3は17を3で割った時の余りを表しているわけですね。
これは余りを出す計算として以下のように変形できます。
2 = 17 - 5×3
m = n - kp
ここからが本題です。
m = n - kp
これに(-10000) mod 32768を当てはめると
m = (-10000) - (k × 32768)
となります。
このmには(0 ≦ m ＜ p)という範囲条件があるので
(0 ≦ m ＜ 32768)となります。
mと(-10000) - (k × 32768)は同じ値なので、範囲条件をつけて
0 ≦ (-10000) - (k × 32768) ＜ 32768
となります。
kは整数なので、この範囲を満たす整数を考えます。
kに0やプラスの値を入れると結果がマイナスになるのでこの範囲に入りません。
そこでkはマイナスの値だという事がわかります。
-1を入れると -10000+32768 で 22768になります。
-2を入れると -10000+65536 で 55536になり、範囲を超えます。
よって条件を満たすkは-1しかありません。
22768 = (-10000) mod 32768となります。
後はア～エを計算して答えが22768となるものを探していきます。
※kを出す部分はメタルさんのリンク先の解説が正攻法です。
しかし結果論になってしまいますが精度の低いざっくり計算でも充分ですね。
-10000を-1、32768を3として
0 ≦ -1 - 3k → -1/3 ≦ k
-1 -k3 ＜ 3 → k ＜ 4/3
-1/3 ≦ k ＜ 4/3
-0.3… ≦ k ＜ 1.3…
k = -1
n = kp + m (0 ≦ m ＜ p)
17 = 5×3 + 2 (0 ≦ 2 ＜ 3)
「mはnのpによる剰余でありn mod pであらわす」という部分は
「2は17の3による剰余であり17 mod 3であらわす」ですね。
17を3で割ると商は5で余りは2です。
17 mod 3は17を3で割った時の余りを表しているわけですね。
これは余りを出す計算として以下のように変形できます。
2 = 17 - 5×3
m = n - kp
ここからが本題です。
m = n - kp
これに(-10000) mod 32768を当てはめると
m = (-10000) - (k × 32768)
となります。
このmには(0 ≦ m ＜ p)という範囲条件があるので
(0 ≦ m ＜ 32768)となります。
mと(-10000) - (k × 32768)は同じ値なので、範囲条件をつけて
0 ≦ (-10000) - (k × 32768) ＜ 32768
となります。
kは整数なので、この範囲を満たす整数を考えます。
kに0やプラスの値を入れると結果がマイナスになるのでこの範囲に入りません。
そこでkはマイナスの値だという事がわかります。
-1を入れると -10000+32768 で 22768になります。
-2を入れると -10000+65536 で 55536になり、範囲を超えます。
よって条件を満たすkは-1しかありません。
22768 = (-10000) mod 32768となります。
後はア～エを計算して答えが22768となるものを探していきます。
※kを出す部分はメタルさんのリンク先の解説が正攻法です。
しかし結果論になってしまいますが精度の低いざっくり計算でも充分ですね。
-10000を-1、32768を3として
0 ≦ -1 - 3k → -1/3 ≦ k
-1 -k3 ＜ 3 → k ＜ 4/3
-1/3 ≦ k ＜ 4/3
-0.3… ≦ k ＜ 1.3…
k = -1
2020.02.22 11:16
助け人さん(No.6)
★FE ゴールドマイスター
横から失礼します。
この問題に限定すれば、次のように考えれば早く解けます。
まず、剰余は0以上であるため、アは不正解。問題文の－10000も、残りのイ～エも、剰余を求める必要はありません。
他の問題でもよく問われますが、
a mod xと同じものはどれか。
ア b mod x
イ c mod x
ウ d mod x
エ e mod x
と問われたら、b、c、d、eのうち、aとの差がxで割り切れるものが正解です。
bが正解の場合で説明すると、
a mod x＝b mod x
a mod x－b mod x＝0
(a－b) mod x＝0
つまり、a－bはxの倍数
－22768、10000、22768のうち、－10000との差が32768で割り切れるのは22768です。
この問題に限定すれば、次のように考えれば早く解けます。
まず、剰余は0以上であるため、アは不正解。問題文の－10000も、残りのイ～エも、剰余を求める必要はありません。
他の問題でもよく問われますが、
a mod xと同じものはどれか。
ア b mod x
イ c mod x
ウ d mod x
エ e mod x
と問われたら、b、c、d、eのうち、aとの差がxで割り切れるものが正解です。
bが正解の場合で説明すると、
a mod x＝b mod x
a mod x－b mod x＝0
(a－b) mod x＝0
つまり、a－bはxの倍数
－22768、10000、22768のうち、－10000との差が32768で割り切れるのは22768です。
2020.02.22 12:59