再帰呼び出しについて

[funky]

c＋＋のプログラミングについて質問です。
素因数分解をするプログラムを作りたいんですが、途中がわかりません。

#include < stdio.h >

#define NOERROR 0

int factor(int n);

int main()
{
int x;

do
{
printf("１以上の整数を入力してください：");
scanf("%d",&x);
}
while( x<1 );

factor(x);
printf("\n");

return NOERROR;
}

int factor(int n)
{
ここがわかりません。←←←←←←←


return NOERROR;
}

[h2so5]

どう分からないのか具体的に書いてください。

[funky]

どうすれば、

表示されるのか

が、わかりません。

例としてあげれば

３４＝５×１３　や　１９７４ ＝ ２×３×７×４７

と表示したいです。

[box]

３４＝５×１３　や　１９７４ ＝ ２×３×７×４７

前者は
３４＝２×１７
か
６５＝５×１３
の間違いであると仮定して、さて、まずは再帰呼び出しを使わない方法から考えてみてはどうでしょうか。
筆算で求めるときにどうするかを念頭に置きながら。

[naohiro19]

数学の素因数分解のアルゴリズムを元にプログラムを組めばわかりやすいと思います。

[funky]

boxさん
６５です、すいません。
再帰を使わないやり方・・・
わかりました。

naohiro19さん
なるほどです。

[かずま]

再帰呼び出ししようとすると、引数が 2つ要るのですが、むりやり 1つにしてみました。

コード:

int factor(int n)
{
    int r = n >> 16;
    n &= 0xffff;
    if (r == 0) {
        r = 1;
        if (n > 1) for (r = 2; n % r; r++) ;
        printf("%d = %d", n, r), factor(r << 16 | n / r);
    } else if (n > 1) 
        if (n % r) factor(r+1 << 16 | n);
        else printf(" x %d", r), factor(r << 16 | n / r);
    return NOERROR;
}

[funky]

かずまさん

自分もこんな感じでつくりました。
参考にさせていただきます。

n &= 0xffff;

の意味ってどんな意味ですか？

[tk-xleader]

コードを書いたかずまさんではありませんが…

n &= 0xffff;

の意味は、おそらく2つの16ビット整数をビット演算で無理やり一つにまとめた32ビット整数nから下位16ビットの整数を取り出してnに代入している。ということだと思います。
上位16ビットは r = n >>16; でrに代入しているようですし…

[non]

再帰呼び出ししようとすると、引数が 2つ要るのですが、むりやり 1つにしてみました。

なぜ、引数が２つ必要なのか、説明をお願いします。

[かずま]

なぜ、引数が２つ必要なのか、説明をお願いします。

例えば、60 の素因数分解を 2 2 3 5 と表示するだけなら、引数は 1つで済みます。
しかし、60 = 2 x 2 x 3 x 5 と表示しようとすると、最初の呼び出しに対しては 60 = 2 と表示し、そのとあの再帰呼び出しでは x 2、x 3、x5 のように表示することことになります。
ところが、factor() が呼び出されたとき、最初の呼び出しなのか、二度目以降の呼び出しなのかを区別する手段を私は思いつきません。

引数を 2つにして、main() からは factor(60, 0) で呼び出し、factor() の中では factor(30, 1)、factor(15, 1)、facor(5, 1) と呼び出せば、要求通りの表示ができます。

もしも引数 1つでこの問題を解決できる方法をご存じなら、ぜひご教示ください。

なお、引数を 2つ使うなら、もっと凝ったことができると考えたのが私のあの解答です。
本来ならループで書けるものをわざわざ再帰呼び出しに変えるのだから、再帰呼び出しをする部分に関してはループを一切使わないようにしようと考えました。

[non]

やはり、そういうことでしたか。
方法１
　static変数を使い、１回目か２回目以降かを区別する。
方法２
　最後の素因数の後に、Xがつくのかつかないのかを判断する。
　最後の素因数の次には　n/rは１になるので、それで判断する。
　発想の転換ですね。

[かずま]

方法１
　static変数を使い、１回目か２回目以降かを区別する。

static変数は私も考えましたが、スレッドセーフではないのが嫌だな、と思って避けていました。
でも、こんな問題にスレッドセーフを持ち出す意味はありませんね。

コード:

int factor(int n)
{
    static int first = 1;
    int r;
    if (first) {
        r = 1;
        if (n > 1) for (r = 2; n % r; r++) ;
        printf("%d = %d", n, r);
        first = 0;
        factor(n / r);
        first = 1;
    } else if (n > 1) {
        for (r = 2; n % r; r++) ;
        printf(" x %d", r);
        factor(n / r);
    }
    return 0;
}

方法２
　最後の素因数の後に、Xがつくのかつかないのかを判断する。
　最後の素因数の次には　n/rは１になるので、それで判断する。
　発想の転換ですね。

これはどういうことでしょうか？
もう少し具体的な説明をお願いします。

[non]

もう少し具体的な説明をお願いします。

申し訳ありません。私が勘違いしておりました。
60 = 2 x 2 x 3 x 5　の　　60=　を関数側で出力することを考えておりませんでした。
重ねてお詫びいたします。60=を関数側で出さなくて良いなら，

コード:

int factor(int n)
{
    int r;
	for (r = 2; n % r; r++) ;
    printf("%d ", r);
	if( n / r != 1){
		printf("x ");
		factor(n / r);
	}
    return 0;
}