情報数学第1-1章 - Tominaga Lab, Chausson

情報数学１第1-1章
除法定理と整除演算
香川大学工学部富永浩之
[email protected]
概
要
■ 数の集合と四則演算の表記
自然数・整数・有理数・実数
加減乗除
和差積商
■ 整数化記号
切捨
切上
四捨五入
ガウス記号
■ 除法定理と整除演算
除法等式
剰余条件
整商と剰余
■ 様々な剰余と整商
正剰余
負剰余
切捨整商
切上整商
■ 整除演算の応用とデータ表現
最小剰余
第01節 [1] 数の集合の表記
整数
[integer]
自然数 [natural number]
Ｚ
Ｎ
正負
0および正整数
離散
離散
有理数 [rational number]
実数
[real number]
複素数 [complex number]
Ｑ
Ｒ
Ｃ
整数の比
数直線上の数
実部と虚部
稠密
連続
連続
正の数
0でない数
・
・
・
・
・
Ｘ+
Ｘ*
Ｎ+ Ｚ+ Ｑ+ Ｒ+
Ｚ* Ｑ* Ｒ* Ｃ*
情報科学では、自然数Ｎに 0 を含める
Ｎ+ とＺ+ は同じ集合
整数Ｚはドイツ語の数 Zahl から
有理数Ｑは英語の商 Quotient から
稠密とは隙間(区間の穴)がないこと、連続とは1点の穴もないこと
第01節 [2] 四則演算の表記
演算
加法
減法
乗法
除法
[addition]
[subtraction]
[multiplication]
[division]
累乗 [power]
剰余 [reminder]
実商
整商
数学
Ａ＋Ｂ
Ａ－Ｂ
Ａ×Ｂ
Ａ÷Ｂ
計算機
a + b
a - b
a * b
a / b
演算結果
和 [sum]
差 [difference]
積 [product]
商 [quotient]
Ａ↑Ｂ a ^ b
Ａ％Ｂ a % b
実数の除法としての結果の実数
整数の除法としての結果の整数 (実商の切捨)
・累乗は、標準的な記法がない
・通常の整商は、実商の切捨整数
実商 17÷5＝3.4
整商 17÷5＝3
第02節 [1] 整数化記号
切捨
x 
floor(x)
x以下の最大の整数
n ≦ x
＜ n+1
切上
x 
ceil(x)
x以上の最小の整数
n ＜ x
≦ n+1
四捨五入
x
round(x)
xに最も近い整数
n ≦ x+0.5 ＜ n+1
・負数に対する整数化は、間違えやすいので注意する
[-3.2] ＝ -3
[-3.6] ＝ -4
・整数化記号は、ガウス記号ともいう
・プログラム言語では、ライブラリ関数として用意されている
・ C言語には、round(x) がないので、floor(x+0.5) で求める
・ 100の位での切捨(345→300)は、[x/100]*100 とする
第03節 [1] 割り算の意味と計算方法
割り算
17 ÷ 5 ＝ 3 ‥ 2
17 割る 5 は 3 余り 2
右辺には2つの値が並べられている
本当の意味での等式ではない (簡略表記)
意味
17 に 5 の塊が何個あるか、残りは何個か
計算
17から5をできるだけ引いていく
引けなくなるまで(負にならない間)の回数を数える
17
12
7
2
－
－
－
－
5
5
5
5
＝ 12
＝ 7
＝ 2
＝ ×
1回
2回
3回
3回引けて、残りは2
17 ÷ 5 ＝ 3 ‥ 2
17 ＝ 5 × □ ＋ □
1
12
2
7
3
2
4
-3
穴埋め等式
第03節 [2] 除法定理
穴埋め等式
除法定理
任意の整数 a と正整数 b に対し
除法等式
a ＝ b × q ＋ r
剰余条件
0 ≦ r ＜ b
を満たす整数 q, r が
一意に存在する
・
・
・
・
・
a ＝ b × □ ＋ □
に入る値は
幾つも考えられる
1組に特定するには
何か条件が必要である
除法定理は、整除演算の原理である
証明は、数学的帰納法による
整数に関する多くの性質は、除法定理から導かれる
除法等式は、題意の立式や式変形において、頻出である
剰余条件を変えると、様々な剰余を考えることができる
第03節 [3] 整除演算
整除演算
a ÷ b ＝ q ‥ r
//---r = a;
// 剰余の初期化
被除数
除数
a
b
q = 0;
// 整商の初期化
整商
剰余
q
r 0≦r＜b
b＞0
入力
整除演算
a, b
// 反復前の前提
q＝0
while ( r >= b ) {
b＞0
// 引ける間
r = r - b;
// 減算
q++;
// 計数
// 反復内で不変
剰余は 0,1,‥, b-1 の b 通り
r≧0
a＝q×b＋r
}
整除演算の記号
// 反復後に成立
整商
剰余
出力
q ＝ a @ b
r ＝ a % b
q, r
q≧0
0≦r＜b
第05節 [1] 整商と剰余の性質
除法等式
整除等式
a ＝ b × (a@b) ＋ (a%b)
(a － (a%b)) ÷ b ＝ a@b
和の剰余
積の剰余
(a＋b) % c ＝ ( (a%c)＋(b%c) ) % c
(a×b) % c ＝ ( (a%c)×(b%c) ) % c
二重整商
n @ (p×q) ＝ (n@p) @ q
10000 @ 91 ＝？
10000 % 91 ＝？
10000 ＝ 100×100
100 % 91 ＝ 9
を利用
より
91 ＝ 7×13
を利用
10000 @ 7 ＝ 1428
より
積の剰余から
二重整商から
与式＝ (9×9) % 91 ＝ 81
与式＝ 1428 @ 13 ＝ 109
第06節 [1] 正剰余と負剰余
除法等式
a ＝ b × q ＋ r
正剰余
剰余条件
0≦r＜b
整商
切捨
負剰余
-b＜r≦0
切上
+17 ＝ 5 × □ ＋ □
q 仮商
r 残余
+17 ÷ 5 ＝ +3 ‥ +2
-17 ÷ 5 ＝ -4 ‥ +3
+17 ÷ 5 ＝ +4 ‥ -3
-17 ÷ 5 ＝ -3 ‥ -2
-17 ＝ 5 × □ ＋ □
+3 ← 正 +2
-4 ← 正 +3
+4 ← 負 -3
-3 ← 負 -2
・除法等式を立て、先に剰余を考える
・除数が負数の場合、正負の剰余と切捨・切上の整商との関係が逆になる
第06節 [2] 整商と剰余の関係
元
数
除
数
整商
切切
捨上
剰余
正
負
+13 +6 +2 +3 +1
-5
-13 +6
切切
捨上
正
負
除法等式
切捨整商と正剰余
切上整商と負剰余
+13 ＝ (+6)×(+2)＋(+1)
+13 ＝ (+6)×(+3)＋(-5)
-13 ＝ (+6)×(
-13 ＝ (+6)×(
)＋(
)
切捨整商と負剰余
)＋(
)
切上整商と正剰余
+13 -6
+13 ＝ (-6)×(
)＋(
)
+13 ＝ (-6)×(
)＋(
)
-13 -6
-13 ＝ (-6)×(
)＋(
)
-13 ＝ (-6)×(
)＋(
)
除法等式を立てて、
整商と剰余を求める
第07節 [1] 最小剰余
最小剰余
剰余条件
-b/2 ≦r＜ +b/2
剰余の範囲
除数3 (奇数)
正剰余
負剰余
整商
四捨五入
除数4 (偶数)
0, +1, +2
-2, -1, 0
最小剰余
0, +1, +2, +3
-3, -2, -1, 0
-1, 0, +1
-2, -1, 0, +1
8
5
4
14
10
０
9 -１
11
+１
6
０
11 7 -１
+１
-２
-２
8
13
+２
6
7
12
10
5 9
第08節 [1] 整除演算の応用
下2桁が99で、21で割り切れる最小の自然数を求めよ。
自然数をNとし、その上位桁をN'とすると、 N ＝ [
] × N' ＋ [ ] と表される。
また、Nを21で割った整商をQとする。除法等式より N ＝ [ ] ×Q と表される。
ここで、Q＝Q0' の各桁を下位から求めていく。
整理して、 [
] × N' ＝ [
] × Q0' ＋ [ ] ‥ ① を得る。
Q0'の下1桁を Q1 とすると、①から明らかに Q1＝9 となる。
上位桁 Q1' とすると、 Q0' ＝ [
] ×Q1'＋ [ ] となる。
①に代入して、 100×N'＝21×(10×Q1'＋9)－99＝210×Q1'＋90 となり、
10×N' ＝ [
] × Q1'＋ [
] ‥ ② を得る。
Q1'の下1桁を Q2 とすると、②から明らかに Q2＝1 となる。
上位桁 Q2' とすると、 Q1' ＝ [
] ×Q2'＋ [ ] となる。
②に代入して、 10×N'＝21×(10×Q2'＋1)＋9＝210×Q2'＋30 となり、
N'＝ [ ] × Q2' ＋ [ ] ‥ ③ を得る。
Q2'＝0 のとき、N'＝3 で、③は満たされる。
よって、 N＝ 100 × [
] ＋ 99 ＝ [ ] を得る。
また、Qの各桁は、上位から 0,1,9 であり、Q＝19 となる。
このとき、 399＝21×19 で題意を満たしている。
第08節 [2] トランプカードの識別番号
A
S
0
2
1
3
2
4
3
5
4
6
5
7
6
8
7
9
8
T
J
Q
K
9 10 11 12
H
13 14 15 16 17 18 19 20 21 22 23 24 25
D
26 27 28 29 30 31 32 33 34 35 36 37 38
C
39 40 41 42 43 44 45 46 47 48 49 50 51
33 ÷ 13 ＝ 2 ‥ 7 ⇒ D8
H5 ⇒ 1 × 13 ＋ 4 ＝ 17
列数 b で、q 行 r 列の位置の数 a
a＝b×q＋r
q＝a@b, r＝a%b

Download Report