第９講 ユークリッド互除法

第４話 ユークリッド互除法プログラム解説

を実現するプログラム再掲
#! ruby -Ks
def f(a,b)
　a=a%b
　if a==0 then
　　return b
　end
　f(b,a)
end
def g(a,b)
　if b>a then
　　w=a
　　a=b
　　b=w
　end
end
print "aを入力して下さい。 a="
a=gets.to_i
print "bを入力して下さい。 b="
b=gets.to_i
g(a,b)
print "aとbの最大公約数は",f(a,b),"です。\n"
参考ダウンロード添付ファイル



解説

まず、g(a,b)すなわち
def g(a,b)
　if b>a then
　　w=a
　　a=b
　　b=w
　end
end
では、では何が行われているのでしょうか。
ここでは、bの方がaより大きい場合に、
aとbを交換しています。
大きい方を小さい方で割っていくのがユークリッド互除法です。
メソッドfではaをbで割っていますので、
aの方が小さい場合は、交換して交換しておかなければなりません。

交換は一回だけで済みます。
理由は、
def f(a,b)
　a=a%b
　if a==0 then
　　return b
　end
　f(b,a);
end
のa=a%bにあります。
aをbで割った余りは、bより小さいので、
f(b,a)の()内の前者の方が小さくなることはありません。

また、
　if a==0 then
　　return b
　end
　f(b,a);
を見ればお分かりのように、遡及（入れ子式人形のより中への旅）は、
余りが０になるまで続けられます。
余りが０になったとき初めてreturn bで値を返します。
つまり、一番小さい人形が値bを返し、
中から２番目以降の人形は、その値（＝一番小さい人形が返した値）を返し続けます。
結果的には、社長が、
print "aとbの最大公約数は",f(a,b),"です。\n"
によって、一番中の人形が返したbの値が表示されます。
def f(a,b)
　a=a%b
　if a==0 then
　　return b
　end
　f(b,a)
end
によって、
互い違いに割っていくユークリッド互除法が実現されていることが分かります。
ポイントはf(a,b)の中がf(b,a)となっていることです。
互除法互い違いに割っていくのでしたね。
互い違いを実現しているのが、
逆順なのです。

第５話の課題は、ランダムに０より大きい整数aとbを発生させ、
分数a/bをつくり、その整数がユークリッド互除法を使い、
約分できるかを判定し、約分できる場合には約分し、
約分できない場合は、約分できないと表示するプログラムを考えて下さい。


ヒント：約分できるかどうかは、最大公約数が１より大きいかどうかで判定できます。
＊　ａとｂの最大公約数が１のとき、ａとｂは互いに素といいます。

第３話へ　第５話へ

eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
vc++講義へ
vba 2013 2010 2007 入門へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座へ
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
専門用語なしの C言語 C++ 入門（Visual C++ 2010で学ぶ C言語 C++ 入門）
専門用語なしの excel vba マクロ 入門 2013 2010 2007 対応講義 第1部
eclipse java 入門へ
excel 2016 vba 入門第１部へ
本サイトトップへ