ページ 11

教えてください

Posted: 2011年6月08日(水) 11:14
by さゆうう
このプログラムわからなんで教えてくれませんか?
2個の整数を読み込んで、mとnのすべての公約数を出力するプログラムを書いてください

実行例
1個目の整数を入力してください。:90
2個目の整数を入力してください。:120

1 2 3 5 6 10 15 30

自分がやったのこれですが、実行結果が違いました;;
何が間違えっているのでしょうか?
code
#include<stdio.h>
int main(void)

{
int m,n,i;

printf("1個目の整数を入力してください。:");
scanf("%d",&m);
printf("2個目の整数を入力してください。:");
scanf("%d",&n);

for(i=m;i>=1;i--)
if(m%i==0)
for(i=n;i>=1;i--)
if(n%i==0)

printf("%d",m/i & n/i);
putchar('\n');

return(0);
}
/code

Re: 教えてください

Posted: 2011年6月08日(水) 11:35
by さゆうう
[quote="さゆうう"]このプログラムわからなんで教えてくれませんか?
2個の整数を読み込んで、mとnのすべての公約数を出力するプログラムを書いてください

実行例
1個目の整数を入力してください。:90
2個目の整数を入力してください。:120

1 2 3 5 6 10 15 30

自分がやったのこれですが、実行結果が違いました;;
何が間違えっているのでしょうか?

コード:

#include<stdio.h>
int main(void)

{
	int m,n,i;

	printf("1個目の整数を入力してください。:");
	scanf("%d",&m);
	printf("2個目の整数を入力してください。:");
	scanf("%d",&n);

	for(i=m;i>=1;i--)
		if(m%i==0)
	for(i=n;i>=1;i--)
		if(n%i==0)

			printf("%d",m/i & n/i);
	putchar('\n');

	return(0);
}
すいません;;

Re: 教えてください

Posted: 2011年6月08日(水) 11:55
by hidden
こんにちは トピックの二重になっているようですが
たぶん副管理人さんあたりがなんとかしてくれると思うのであまり気にせずにいきましょう。

まずはさゆううさんがどんなアルゴリズムで公約数を導き出そうとしているのか書いてみてください。

二重for文のiの初期化は意図があってのものですか?
printfの m/i & n/i はどんな目的ですか?

Re: 教えてください

Posted: 2011年6月08日(水) 22:02
by 初級者
とりあえず動くコードを差し上げます。効率は無視。

コード:

#include <stdio.h>

int main(void)
{
    int n[2], i;

    for (i = 0; i < 2; i++) {
        do {
            printf("%d個目の自然数を入力してください > ", i + 1);
            scanf("%d", &n[i]);
        } while (n[i] <= 0);
    }

    for (i = 1; i <= n[0]; i++) {
        if (n[0] % i == 0 && n[1] % i == 0) {
            printf("%d ", i);
        }
    }
    putchar('\n');
    return 0;
}

Re: 教えてください

Posted: 2011年6月09日(木) 23:04
by setton

コード:

    for(i=m;i>=1;i--)
        if(m%i==0)
    for(i=n;i>=1;i--)
        if(n%i==0)
というところがおかしいんだと思います。
公約数を見つけたいのに、mを割り切れるものを見つけた後、それとはまた別のnを割り切れるものを見つけています。
ここでiの値を変えているのが原因だと思います。

コード:

for(i=1;i<=m && i<=n;i++){
            if(m%i == 0){
                    if(n%i == 0){
                           printf("%d  ",i);
                     }
             }
}
printf("\n");
こうすれば、1からmかnと同じ値になるまで小さい方から順番に割っていく事が出来ます。
mがiで割り切れれば、iの値を変えずにnが割り切れるかどうかをチェックしています。

もし、効率化がしたいのであれば、mの約数iが見つかった時、imという変数を用意してそこにm÷iを入れます。
そして、iでnが割り切れるかチェックした後、imでnが割り切れるかも同時にチェックします。
これを続けていき、もしiがimの値を超えればそこでプログラムを終了させる事が出来ます。

20と30の約数で考えてみましょう。
元のプログラムでは、1~20まで全ての値を総チェックしています。
これをi,imを使うとそれぞれの値は次のように変化していきます。
i = 1 im =20
i = 2 im =10
i = 4 im = 5
i = 5 im = 4
この時点で、iがimを上回りました。
ここから先のmを割り切れるiの値を探していっても、すでにimで出てきたものしかありません。
よって、本来1~20までチェックしなければならないところを、
1~5までのチェックに減らす事が出来たのです。
こうすることによって効率化する事が出来ます。
大きな値を扱う時になればかなり楽になるかと思います。