課題
最大公約数
正 整 数 a,bの 最 大 公 約 数 を ユ ー ク リ ッ ド 互 除 法 で 求 め よ 。
a = bq + r ( 0＜ r＜ b） の と き 、 aと bの 最 大 公 約 数 gcd(a,b)と bと rの 最 大 公 約
数 gcd(b,r)が 一 致 す る こ と に 基 づ く 。 す な わ ち 、 gcd(a,b)=gcd(b,r)。
a=155, b=40 の 場 合 ,
155 = 40 * 3 + 35
40 = 35 * 1 + 5
35 = 5 * 7
gcd(155,40)=gcd(40,35)
gcd(40,35)=gcd(35,5)
gcd(35,5)=5
となる。
●再帰的定義
gcd(a,b) = gcd(b,r)
= b
(a=bq+r,r>0)
(a=bq+r,r=0)
関 数 gcd(a,b)は 、 定 義 通 り に 書 け る 。
● プ ロ グ ラ ム (KA811.bas)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
' << K811.bas >>
' 最大公約数
'
Do
' 正 整 数 A,Bの 読 み 込 み 。
Read A,B
If (A <= 0) Or (B <= 0) Then Exit Do
RST=Fcd(A,B)
Print"Fcd(";A;",";B;") =";RST
Loop
End
'
' 最 大 公 約 数 。 Gcdは 予 約 語 と 重 な る た め Fcdと す る 。
Function Fcd(A,B)
R = A Mod B
If R =
Then
Z=
Else
Z=
End If
Fcd=Z
End Function
'
' データ。
Data 1234,567, 120,64, 0,0
- 1 -
実行結果
Fcd( 1234, 567) = 1
Fcd( 120, 64) = 8
OK
● a=155,b=40の 場 合 、 プ ロ グ ラ ム KA811.basの 動 作 は ① か ら ⑤ の よ う に な る 。
⑤ gcd(155,40)は 値 5を 返 す 。
gcd(155,40)
① gcd(155,40)は gcd(40,35)を 呼 び 出 す
④ gcd(40,35)は 値 5を gcd(155,40)に 返 す 。
gcd(40,35)
② gcd(40,35)は gcd(35,5)を 呼 び 出 す
③ gcd(35,5)は 値 5を gcd(40,35)に 返 す 。
gcd(35,5)
（ 考 察 ） gcd(a,b)=gcd(b,r)の 証 明 。
a = bq + r (0<r<b) の と き 、 a,bの 公 約 数 の 集 合 を G(a,b)と お く と 、
G(a,b) = G(b,r)
が 成 り 立 つ 。 こ れ は 、 a,bの 最 大 公 約 数 と b,rの 最 大 公 約 数 が 一 致 す る こ と を 意 味
する。
G(a,b)⊂ G(b,r)を 示 す 。
a=a'k, b=b'k と す る と 、 a'k=b'kq+r と な り 、 変 形 し て 、 r=(a'-b'q)k と な
る 。 こ れ は 、 b,rが 約 数 kを 持 つ こ と を 意 味 す る 。
す な わ ち 、 G(a,b)⊂ G(b,r)が 示 さ れ た 。
G(a,b)⊃ G(b,r)を 示 す 。
b=b'm, r=r'm と す る と 、 a=b'mq+r'm と な り 、 変 形 し て 、 a=(b'q+r')m と な
る 。 こ れ は 、 a,bが 約 数 mを 持 つ こ と を 意 味 す る 。
す な わ ち 、 G(a,b)⊃ G(b,r)が 示 さ れ た 。
以 上 よ り 、 G(a,b) = G(b,r) が 証 明 さ れ た 。
- 2 -
© Copyright 2024 ExpyDoc
