配布プリント

計算機数学演習 A 2015.6.2. ユークリッドの互除法
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
約数, 公約数, 最大公約数
1
記号 Z で整数全体を表す. 整数 a, b について, a が b を割り切る時, a は b の約数である (b は a の倍数である) とい
う. a, b のどちらの約数にもなっている数を a と b の公約数といい, その中で最大のものを a と b の最大公約数と呼び,
GCD(a, b) で表す.
例 1 (約数, 公約数, 最大公約数). 16, 60 について, 上の定義を確認すれば次のようになる.
16 の約数全体
60 の約数全体
16 と 60 の公約数全体
16 と 60 の最大公約数
問題 2. 与えられた整数 A の約数をすべて表示する関数 divisor(A) を作成せよ. (ヒント : 変数 K を 1 から A まで動かし, K が A を割り切る時だけ K を表示. A % K で A を K で割った余りの計算. )
1. 約数の列挙 divisor.txt
def divisor(A)
{
}
end$
<--
ここまでプログラムの終わりは end; と書いていたが, 値 0 が表示されるので end$ に変更.
問題 3. 与えられた 2 つの整数 A, B の公約数をすべて表示する関数 common_divisor(A, B) を作成せよ. (プログラ
ムを単純にするために, A > B としておく. )
2. 公約数の列挙 divisor.txt
def common_divisor(A, B)
{
}
end$
問題 4. 上の問題で作成した common_divisor(A, B) を変更して, 与えられた 2 つの整数 A, B の最大公約数を返す関数
naive_gcd(A, B) を作成せよ. (効率は考えていない素朴な方法)
3. 最大公約数の計算 naive gcd.txt
def naive_gcd(A, B)
{
}
end$
1
ユークリッドの互除法
2
定理 5 (ユークリッドの互除法の原理). 整数 a, b について, a を b で割った商を q とし, 余りを r とする. （すなわち,
a = qb + r
(0 ≤ r < b) が成り立つ.）この時, GCD(a, b) = GCD(b, r) が成り立つ.
(証明)
上の原理を基に, GCD を計算するアルゴリズムがユークリッドの互除法である.
アルゴリズム 6 (ユークリッドの互除法).
入力 : 整数 a, b, 出力 : GCD(a, b)
1. b ̸= 0 である限り, 2, 3, 4 を続ける.
2.
r ← (a を b で割った余り)
3.
a ← b,
4.
1 へ.
b←r
5. a を出力.
問題 7. GCD(240, 184) を手で計算してみよ. また, GCD(38254, 17577) を Asir の計算機能を使って計算せよ. (Asir で
余りを計算するには, % を使う. 例えば 240 % 184 で 240 を 184 で割った余りが計算できる.)
a
b
r
a
b
240
184
38254
r
17577
上のアルゴリズムに従い, Asir でプログラムを組むと次のようになる.
4. ユークリッドの互除法 my gcd.txt
def my_gcd(A, B)
{
}
end$
問題 8. 上のプログラムを使って, GCD(987654321, 123456789) を計算せよ. また naive_gcd を使ってこの GCD は計
算できるか実験してみよ.
問題 9. 上のプログラムを変更して, 途中経過の表示 (変数 A, B, R の値の表示), 余りの計算回数の表示をするようにせ
よ. (A, B, R の値を一度に表示するには print([A, B, R]); と書く)
2

Download Report