最小公倍数・最小公約数についておしえてください。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kimi

最小公倍数・最小公約数についておしえてください。

#1

投稿記事 by kimi » 13年前

最大公約数(GCD),最小公倍数(LCM)を求めるプログラムを作成しようとしています。
最終的な最大公約数が求まるまでの途中過程を表示をしたいのですが、実行すると途中経過がうまく表示されていないようです。
改善点をおしえてください。

#include <stdio.h>

int gcd(int,int);

int main()
{

int m,n,g,l;
printf("m,nの最大公数約,最小公倍数を求めます\n");
printf("mとnを整数で入力してください。\n");

printf("m=");
scanf("%d",&m);
printf("n=");
scanf("%d",&n);

if(m<=0||n<=0)
printf("再入力してください。\n");

g=gcd(m,n);

l=(m*n)/gcd(m,n);

printf("GCD=%d\n",g);
printf("LCM=%d\n",l);
}


int gcd(int x,int y)
{
int r;

while (x>0&&y>0)
{
r=x%y;
x=y;
y=r;

printf("(m,n)=(%d,%d)\n",x,y);
}
return x;
}

しひ

Re: 最小公倍数・最小公約数についておしえてください。

#2

投稿記事 by しひ » 13年前

どう上手くいかないのか分からないので何とも言えないのですが

コード:

g=gcd(m,n);

l=(m*n)/gcd(m,n);
最小公倍数を求めるとき、直前で変数gに最大公約数を代入しているので、再度gcd()関数を呼ぶ必要は無いですよね。

maru
記事: 150
登録日時: 13年前

Re: 最小公倍数・最小公約数についておしえてください。

#3

投稿記事 by maru » 13年前

kimi さんが書きました:最終的な最大公約数が求まるまでの途中過程を表示をしたいのですが、実行すると途中経過がうまく表示されていないようです。
うまく表示されていないとは、「どうなって欲しい」が、「今どうなっている」を説明しないと何とも言ってみようがありません。
m=24, n=20として実行してみたところ、
(m,n)=(20,4)
(m,n)=(4,0)
と表示されますが、引数として渡した
(m,n)=(24,20)
が表示されないことが問題なのでしょうか?
それでしたら、while文に入る前に表示処理を入れる必要があります。
kimi さんが書きました:改善点をおしえてください。
1.gcd関数は x > y である必要がありますが、チェックされていません。
2.lcmを求めるのに既に求めたgcdの結果を使用せずに、もう一度gcdを呼び出しています。無駄です。g が使用できます。
3.lcmを求める途中で m*n がオーバーフローする可能性があります。
 m / g * n とする方がオーバーフローする可能性が小さくなります(結果的にオーバーフローするのは救いようがない)。

フリオ

Re: 最小公倍数・最小公約数についておしえてください。

#4

投稿記事 by フリオ » 13年前

>1.gcd関数は x > y である必要がありますが、チェックされていません。

 試してみればわかりますが、x < y でも while の最初の一回で x と y が入れ替わるので
問題ありません。

maru
記事: 150
登録日時: 13年前

Re: 最小公倍数・最小公約数についておしえてください。

#5

投稿記事 by maru » 13年前

フリオ さんが書きました:>1.gcd関数は x > y である必要がありますが、チェックされていません。

 試してみればわかりますが、x < y でも while の最初の一回で x と y が入れ替わるので
問題ありません。
あれ、剰余演算子は除数の方が大きくてもいいんですね。いわれてみればそうですね。

閉鎖

“C言語何でも質問掲示板” へ戻る