最大公約数と最小公倍数
２つの数の最大公約数と最小公倍数を作るプログラムをつくります。
最大公約数
まず、ある数の約数をすべてリストアップすることを考えます。CindyScriptのリスト処理をする関数を使うと次のように簡単にできます。
yaku=select(1..n,mod(n,#)==0);
1..n で、１からｎまでの整数のリストを作成できます。select関数は、そのリストから、mod(n,#)==0 を満たすものを選び出してリストを作ります。mod(n.#) は、nを# ( #はリストの要素になります) で割った余りなので、mod(n,#)==0 ということは「割り切れる」ということです。
たとえば、 n=12 のとき
1..n で、[1,2,3,4,5,6,7,8,9.10,11,12] というリストができます。その要素の始めから mod(12,#) つまり12をその要素で割った余りを調べて割り切れるものを選び出します。結果として 1,2,3,4,6,12 が選び出されます。
つぎに、これを関数にします。
yakusuu(n):=select(1..n,mod(n,#)==0);
これで、yakusuu(12) とすれば12の約数がリストアップされます。
２つの数に共通な約数が「公約数」です。そのうち最大のものが「最大公約数」です。では、2つの数の約数のリストを作り、最大公約数を求めてみましょう。2つの数の約数のリストは、それぞれ先ほどの処理で求められているとしましょう。CindyScriptには、２つのリストから共通な要素を抜き出すcommon(list1,list2)という関数があらかじめ用意されています。
yaku3=comon(yaku1,yaku2);
とすれば公約数のリストができます。
次に、最大公約数ですが、CindyScriptには、リストの中から最大値をとり出す関数があり、中身がどんな順序になっていても構いません。
では、やってみましょう。90と72の公約数のリストと、最大公約数を求めます。
それぞれの約数のリストと公約数をすべて表示する必要がなく、最大公約数だけ求めればよいのなら
yakusuu(n):=select(1..n,mod(n,#)==0);
gcd(a,b):=max(common(yakusuu(a),yakusuu(b)));
println(gcd(90,72));
の３行でできます。最大公約数の18だけが表示されます。
ユークリッドの互除法
２つの数の最大公約数を求める方法に、ユークリッドの互除法があります。
a,bの最大公約数を gcd(a,b) で表すことにします。
いま、a>b とします。すると gcd(a,b)=gcd(a-b,b) が成り立ちます。
なぜなら、aとbの最大公約数をGとすると、
a=mG ・・ (1)
b=nG ・・ (2) m,nは互いに素
と表せるので a-b=(m-n)G です。このとき、m-nとnは互いに素なので
（そうでないとすると、１でない公約数c があり m-n=ck , n=ch から m=ck+n=c(k+h) で mとnが互いに素でなくなります）
(2)から、bとa-bの最大公約数はＧということになります。つまり gcd(a,b)=gcd(a-b,b) です。
これをもう一度繰り返すと gcd(a,b)=gcd(a-b,b)=gcd(a-b-b,b) となります。つまり gcd(a,b)=gcd(a-2b,b) です。
さて、aをbで割った商をq , 余りを r とするとき、a=bq+r となりますので a-bq=r です。
すると、 gcd(a,b)=gcd(a-b,b)=gcd(a-2b,b)=・・・=gcd(a-bq,b)=gcd(r,b) となり
結局
gcd(a,b)=gcd(b,r)
が成り立ちます。これがユークリッドの互除法の原理です。
言葉でいうと、「aとbの最大公約数は、bと、aをbで割ったときの余りrとの最大公約数に等しい」ということです。
すると、つぎに、「bとrの最大公約数は、rと、bをrで割ったときの余りr2との最大公約数に等しい」となり
「割った余り」が０でない限り、このことが繰り返されます。そして、最終的に「余りが０」になればそこで最大公約数が得られることになります。
具体的にやってみましょう。72と20でやります。
gcd(72,20) ・・・72を20で割ると余りは12
=gcd(20,12) ・・・20を12で割ると余りは8
=gcd(12,8) ・・・12を８で割ると余りは4
=gcd(8,4) ・・・8を4で割ると余りは0 残ったのは4と0
ここで最後に残った数４が72と20の最大公約数です。
２つの数が互いに素の場合は次のようになります。
gcd(35,8) ・・・ 35を8で割ると余りは3
=gcd(8,3) ・・・ 8を3で割ると余りは2
=gcd(3,2) ・・・ 3を2で割ると余りは1
=gcd(2,1) ・・・ 2を1で割ると余りは0 残ったのは1と0
最後に残ったのは１なので最大公約数は１，すなわち互いに素です。
では、これをCindyScriptで書いて見ましょう。「小さい方の数と、割った余りで考える」ということを何度も繰り返します。このような場合、「再帰的プログラム」という方法を使います。この「再帰的プログラム」は少し難しい概念ですので、何が何だか分からない、という人もいると思います。それはそれで、まあ、よいことにしましょう。
aとbの最大公約数を求める関数をgcd(a,b) としましょう。この関数の処理の中で、aをbで割った余りrを求めてgcd(b,r) を求めます。
すると、関数の処理の中で、自分自身の関数を使うことになります。これが「再帰的プログラム」です。
次のようになります。
---------------------------------------------------------------------------
gcd(a,b):=if(b==0, a, // 最後に0になったらそのときのaを返す
if(b>a, // そうでなければ、もし b>a なら
gcd(b,a), // 引数を入れ替えて gcd()を実行
gcd(b,mod(a,b)) // そうでなければ、bと余りでgcd()を実行
);
);
println(gcd(72,20));
---------------------------------------------------------------------------
次が実行結果です。
最小公倍数
aとbの最大公約数を用いて最小公倍数を求めます。aとbの最大公約数をGとすると
a=mG , b=nG (m,nは互いに素)
で、最小公倍数は mnG ですから、ab/G が最小公倍数となります。
リストを使って最大公約数Gを求め、 ab/G で最小公倍数を表示しましょう。
----------------------------------------------------------------------------------------------------------------------
a=90;
b=72;
yakusuu(n):=select(1..n,mod(n,#)==0);
gcd(a,b):=max(common(yakusuu(a),yakusuu(b)));
LCM=a*b/gcd(a,b);
print(LCM);
----------------------------------------------------------------------------------------------------------------------
＜戻る＞