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

第５話 ユークリッド互除法ランダム版アプリ例


コード再掲
#include<stdio.h>
void f(int a,int b); //aとbを交換する社員
int g(int a,int b); //ユークリッド互除法を行う社員
int main(){
　　int a,b;
yarinaosi:;
　　printf("a=");
　　fflush(0); //pirntfを先に実行させるためのお呪い
　　scanf("%d",&a);
　　printf("b=");
　　fflush(0); //pirntfを先に実行させるためのお呪い
　　scanf("%d",&b);
　　if(a==0 || b==0){
　　　　printf("aにもbにも0より大きい値を入れて下さい。\n");
　　　　goto yarinaosi; //goto文、yarinaosiに戻る
　　}
　　if(a<b)f(a,b);
　　printf("aとbの最大公約数は%dです。\n",g(a,b));
　　return(0);
}
void f(int a,int b){
　　int w;
　　w=a;
　　a=b;
　　b=w;
}
int g(int a,int b){
　　a=a%b;
　　if(a==0){
　　　　return(b);
　　}
　　return(g(b,a));
}
コピペ用添付ファイル

解説

社員f
void f(int a,int b){
　　int w;
　　w=a;
　　a=b;
　　b=w;
}
の任務は、お分かりですよね。
どのようなときにコール（名前を呼ばれること、社員は名前を呼ばれると仕事を行う）
されるかと申しますと、
　　if(a<b)f(a,b);
ですから、bの方が大きいときです。

a=1008
b=1512
aとbの最大公約数は504です。

この例の場合が相当します。
1008<1512ですから。
社員g
int g(int a,int b){
　　a=a%b;
　　if(a==0){
　　　　return(b);
　　}
　　return(g(b,a));
}
の１行目を見ればお分かりのように、
aをbで割ったときの余りを求めていますから、
bの方が大きくては困るわけです。
o
小さい方で大きい方を割るのでしたね。
ですから、bの方が大きい場合には、
aとbを交換させるのが、サブプロシージャfの任務であるわけです。
　　if(a==0){
　　　　return(b);
　　}
の中身はaをbで割ったときの余りが0の場合すなわちaをbで割り切れてしまった場合に、
実行されます。
o
の例では割り切った６が答え＝最大公約数でしたよね。
余りがある場合ファンクションプロシージャgは、
さらに、自分の分身gを作り出して、
同じことを繰り返させます。
ただし、
　　return(g(b,a));
の引数を見ればお分かりのように、
bが今度は割られる対象になっています。
上の例では、４８が割る方だったのに、
４８が割られる対象になっています。
そして、
　　a=a%b;
ですから、割る方は６６（a）を４８（b）で割ったときの余り１８になっています。
　　return(g(b,a));
が、このプログラムの神髄であるといえるでしょう。

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

26242/29899
この分数は約分できません。
ヒント：約分できるかどうかは、最大公約数が１より大きいかどうかで判定できます。
　　　　 ０より大きい整数を発生させるためには、If文を使って下さい。
※　ａとｂの最大公約数が１のとき、ａとｂは互いに素といいます。



第４話へ　第６話へ

a


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