関数k
void k(int a,int b){
int w;
w=a;
a=b;
b=w;
}
では、aとbを交換しています。
大きい方を小さい方で割っていくのがユークリッド互除法です。
関数ykではaをbで割っていますので、
aの方が小さい場合は、交換して交換しておかなければなりません。
交換は一回だけで済みます。
理由は、
int yg(int a,int b){
a=a%b;
if(a==0)return(b);
yg(b,a);
}
のa=a%bにあります。
aをbで割った余りは、bより小さいので、
yg(b,a)の()内の前者の方が小さくなることはありません。
また、
if(a==0)return(b);
yg(b,a);
を見ればお分かりのように、遡及（入れ子式人形のより中への旅）は、
余りが０になるまで続けられます。
余りが０になったとき初めてreturn(b);で値を返します。
つまり、一番小さい人形が値bを返し、
中から２番目以降の人形は、その値（＝一番小さい人形が返した値）を返し続けます。
結果的には、void main()において、
cout<<"最大公約数は"<<yg(a,b)<<"です。"<<endl;
で一番中の人形が返したbの値が表示されます。
int yg(int a,int b){
a=a%b;
if(a==0)return(b);
yg(b,a);
}
によって、
互い違いに割っていくユークリッド互除法が実現されていることが分かります。
第５話の課題は、ランダムに０より大きい整数aとbを発生させ、
分数a/bをつくり、その整数がユークリッド互除法を使い、
約分できるかを判定し、約分できる場合には約分し、
約分できない場合は、約分できないと表示するプログラムを考えて下さい。
ヒント：約分できるかどうかは、最大公約数が１より大きいかどうかで判定できます。
＊ ａとｂの最大公約数が１のとき、ａとｂは互いに素といいます。
第３話へ 第５話へ
eclipse c++ 入門講義第１部へ
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ
