R54 0,30 最大公約数の求め方
考察
面白い、今度は最大公約数が一瞬で求められるようになった！1329と1111の最大公約数なんてコンピュータで計算したら一瞬！スーパーコンピューターとかこのようなことを大量に考えられないスピードでやっているんだろうな、コンピュータおそるべし。
再帰処理もなんか理解できてきた。単純に条件に合わないなら上に戻って再度計算みたいな感じ。
問題
キーボードから入力した二つの数字の最大公約数を表示する｡なお、最大公約数を求める
のに､kouyakusu()関数という再帰関数を利用する｡
二つの数xとｙの最大公約数を求める手順（ユークリッドの互助方）
まず、ｘ÷ｙの余りを求める｡「余り≠0」なら、「ｘ←ｙ」「ｙ←余り」として、「余り＝0」
になるまでｘ÷ｙを繰り返す｡
例.ｘ＝６３、ｙ＝４５の場合
６３ ÷ ４５ ＝ １ ・・・ １８
４５ ÷ １８ ＝ ２ ・・・ ９
１８ ÷ ９ ＝ ２ ・・・ ０ ⇒ （最大公約数は「９」）
表示例
--------最大公約数を求める関数-------
１つめの数字を入力してください---->63
２つめの数字を入力してください---->45
63 ÷ 45 = 1 余り 18
45 ÷ 18 = 2 余り 9
18 ÷ 2 = 9 余り 0
最大公約数9はです。
--------------------------------------
考え方
（１）数字１(suuji1)、数字２(suuji2)を入力する。
（２）最大公約数を求める関数(kouyakusu)に上記の数字を引数として実行し、
戻り値(kotae)を受け取り、表示する｡
「kotae = kouyakusu(suuji1,suuji2)」
（３）最大公約数を求める関数
①仮引数をｘ、ｙとする。
②ｘ、ｙ、ｘ÷ｙの値、余りを表示する｡
③ｘ÷ｙの余り(amari)が0だったらそのときのｙを戻り値として返す｡
「return y」
④そうでない時、戻り値としてｙ→ｘ、余り→ｙとして関数を再帰する。
「return kouyakusu(y,amari)」
#include
int kouyakusu(int x,int y)
{
int amari;
amari = x % y;
printf("%5d ÷ %5d = %5d余り %5d\n",x,y,x/y,amari);
if (amari ==0) {
return y;
}
else{
return kouyakusu(y,amari);
}
}
int main()
{
int suuji1,suuji2,kotae;
printf("----------最大公約数を求める関数---------\n");
printf("一つ目の数字を入力してください。\n");
scanf("%d",&suuji1);
printf("二つ目の数字を入力してください。\n");
scanf("%d",&suuji2);
kotae = kouyakusu(suuji1,suuji2);
printf("最大公約数は%dです。\n",kotae);
printf("-------------------------------\n");
return 0;
}
int kouyakusu(int x,int y)
{
int amari;
amari = x % y;
printf("%5d ÷ %5d = %5d余り %5d\n",x,y,x/y,amari);
if (amari ==0) {
return y;
}
else{
return kouyakusu(y,amari);
}
}
int main()
{
int suuji1,suuji2,kotae;
printf("----------最大公約数を求める関数---------\n");
printf("一つ目の数字を入力してください。\n");
scanf("%d",&suuji1);
printf("二つ目の数字を入力してください。\n");
scanf("%d",&suuji2);
kotae = kouyakusu(suuji1,suuji2);
printf("最大公約数は%dです。\n",kotae);
printf("-------------------------------\n");
return 0;
}
