Presentation is loading. Please wait.

Presentation is loading. Please wait.

香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp.

Similar presentations


Presentation on theme: "香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp."— Presentation transcript:

1 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp
情報数学1 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之

2 概 要 ■ 数の集合と四則演算の表記 ■ 整数化記号 ■ 除法定理と整除演算 ■ 様々な剰余と整商 ■ 整除演算の応用とデータ表現
概 要 ■ 数の集合と四則演算の表記 自然数・整数・有理数・実数 加減乗除 和差積商 ■ 整数化記号 切捨 切上 四捨五入 ガウス記号 ■ 除法定理と整除演算 除法等式 剰余条件 整商と剰余 ■ 様々な剰余と整商 正剰余 負剰余 切捨整商 切上整商 最小剰余 ■ 整除演算の応用とデータ表現

3 第01節 [1] 数の集合の表記 整数 [integer] Z 正負 離散
自然数 [natural number] N 0および正整数 離散 有理数 [rational number] Q 整数の比 稠密 実数 [real number] R 数直線上の数 連続 複素数 [complex number] C 実部と虚部 連続 正の数 X+ N+ Z+ Q+ R+ 0でない数 X* Z* Q* R* C* ・ 情報科学では、自然数 N に 0 を含める ・ N+ と Z+ は同じ集合 ・ 整数 Z はドイツ語の数 Zahl から ・ 有理数 Q は英語の商 Quotient から ・ 稠密とは隙間(区間の穴)がないこと、連続とは1点の穴もないこと

4 第01節 [2] 四則演算の表記 演算 数学 計算機 演算結果 加法 [addition] A+B a + b 和 [sum]
演算 数学 計算機 演算結果 加法 [addition] A+B a + b 和 [sum] 減法 [subtraction] A-B a - b 差 [difference] 乗法 [multiplication] A×B a * b 積 [product] 除法 [division] A÷B a / b 商 [quotient] 累乗 [power] A↑B a ^ b 剰余 [reminder] A%B a % b 実商 実数の除法としての結果の実数 整商 整数の除法としての結果の整数 (実商の切捨) ・ 累乗は、標準的な記法がない ・ 通常の整商は、実商の切捨整数 実商 17÷5=3.4 整商 17÷5=3

5 第02節 [1] 整数化記号 切捨 floor(x) x以下の最大の整数 n ≦ x < n+1 切上 ceil(x) x以上の最小の整数
四捨五入 round(x) xに最も近い整数 n ≦ x+0.5 < n+1 ・ 負数に対する整数化は、間違えやすいので注意する [-3.2] = [-3.6] = -4 ・ 整数化記号は、ガウス記号ともいう ・ プログラム言語では、ライブラリ関数として用意されている ・ C言語には、round(x) がないので、floor(x+0.5) で求める ・ 100の位での切捨(345→300)は、[x/100]*100 とする

6 第03節 [1] 割り算の意味と計算方法 割り算 17 ÷ 5 = 3 ‥ 2 17 割る 5 は 3 余り 2
割り算 ÷ 5 = 3 ‥ 割る 5 は 3 余り 2 右辺には2つの値が並べられている 本当の意味での等式ではない (簡略表記) 意味 に 5 の塊が何個あるか、残りは何個か 計算 17から5をできるだけ引いていく 引けなくなるまで(負にならない間)の回数を数える 17 - 5 = 12 1回 12 - 5 = 7 2回 7 - 5 = 2 3回 2 - 5 = × 3回引けて、残りは2 17 ÷ 5 = 3 ‥ 2 17 = 5 × □ + □ 穴埋め等式

7 第03節 [2] 除法定理 除法定理 任意の整数 a と正整数 b に対し 除法等式 a = b × q + r
剰余条件 0 ≦ r < b を満たす整数 q, r が 一意に存在する 穴埋め等式 a = b × □ + □ に入る値は 幾つも考えられる 1組に特定するには 何か条件が必要である ・ 除法定理は、整除演算の原理である ・ 証明は、数学的帰納法による ・ 整数に関する多くの性質は、除法定理から導かれる ・ 除法等式は、題意の立式や式変形において、頻出である ・ 剰余条件を変えると、様々な剰余を考えることができる

8 第03節 [3] 整除演算 整除演算 a ÷ b = q ‥ r 被除数 a 除数 b b>0 整商 q 剰余 r 0≦r<b
//---- 整除演算 入力 a, b r = a; // 剰余の初期化 q = 0; // 整商の初期化 // 反復前の前提 q=0 r≧0 b>0 while ( r >= b ) { // 引ける間 r = r - b; // 減算 q++; // 計数 // 反復内で不変 a=q×b+r } // 反復後に成立 q≧0 0≦r<b 出力 q, r 剰余は 0,1,‥, b-1 の b 通り 整除演算の記号 整商 q = b 剰余 r = a % b

9 第05節 [1] 整商と剰余の性質 除法等式 a = b × (a@b) + (a%b)
整除等式 (a - (a%b)) ÷ b = 和の剰余 (a+b) % c = ( (a%c)+(b%c) ) % c 積の剰余 (a×b) % c = ( (a%c)×(b%c) ) % c 二重整商 (p×q) q 10000 % 91 = ? 10000 = 100×100 を利用 100 % 91 = 9 より 積の剰余から 与式 = (9×9) % 91 = 81 91 = ? 91 = 7×13 を利用 7 = より 二重整商から 与式 = 13 = 109

10 第06節 [1] 正剰余と負剰余 除法等式 a = b × q + r q 仮商 r 残余 剰余条件 整商
剰余条件 整商 正剰余 0≦r<b 切捨 ÷ 5 = +3 ‥ +2 -17 ÷ 5 = -4 ‥ +3 負剰余 -b<r≦0 切上 ÷ 5 = +4 ‥ -3 -17 ÷ 5 = -3 ‥ -2 +17 = 5 × □ + □ +3 ← 正 +2 +4 ← 負 -3 -17 = 5 × □ + □ -4 ← 正 +3 -3 ← 負 -2 ・ 除法等式を立て、先に剰余を考える ・ 除数が負数の場合、正負の剰余と切捨・切上の整商との関係が逆になる

11 第06節 [2] 整商と剰余の関係 除法等式を立てて、 整商と剰余を求める 元数 除数 整商 剰余 除法等式 切捨 切上 正 負
切捨整商 と 正剰余 切上整商 と 負剰余 +13 +6 +2 +3 +1 -5 +13 = (+6)×(+2)+(+1) +13 = (+6)×(+3)+(-5) -13 -13 = (+6)×( )+( ) 切捨整商 と 負剰余 切上整商 と 正剰余 -6 +13 = (-6)×( )+( ) -13 = (-6)×( )+( ) 除法等式を立てて、 整商と剰余を求める

12 第07節 [1] 最小剰余 剰余条件 整商 最小剰余 -b/2 ≦r< +b/2 四捨五入 剰余の範囲 除数3 (奇数) 除数4 (偶数)
剰余条件 整商 最小剰余 -b/2 ≦r< +b/2 四捨五入 剰余の範囲 除数3 (奇数) 除数4 (偶数) 正剰余 , +1, , +1, +2, +3 負剰余 , -1, , -2, -1, 0 最小剰余 , 0, , -1, 0, +1 10 5 9 -1 1 6 -2 +2 8 4 1 +1 5 9 -2 6 10

13 第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 で題意を満たしている。

14 列数 b で、q 行 r 列の位置の数 a a=b×q+r q=a@b, r=a%b 第08節 [2] トランプカードの識別番号
3 4 5 6 7 8 9 T J Q K S 1 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 r=a%b


Download ppt "香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp."

Similar presentations


Ads by Google