再帰呼び出しについて

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

再帰呼び出しについて

#1

投稿記事 by funky » 8年前

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

#include < stdio.h >

#define NOERROR 0

int factor(int n);

int main()
{
int x;

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

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

return NOERROR;
}

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


return NOERROR;
}

アバター
h2so5
副管理人
記事: 2212
登録日時: 8年前
住所: 東京
連絡を取る:

Re: 再帰呼び出しについて

#2

投稿記事 by h2so5 » 8年前

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

funky

Re: 再帰呼び出しについて

#3

投稿記事 by funky » 8年前

どうすれば、

表示されるのか

が、わかりません。

例としてあげれば

34=5×13 や 1974 = 2×3×7×47

と表示したいです。

box
記事: 1737
登録日時: 8年前

Re: 再帰呼び出しについて

#4

投稿記事 by box » 8年前

funky さんが書きました: 34=5×13 や 1974 = 2×3×7×47
前者は
34=2×17

65=5×13
の間違いであると仮定して、さて、まずは再帰呼び出しを使わない方法から考えてみてはどうでしょうか。
筆算で求めるときにどうするかを念頭に置きながら。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

naohiro19
記事: 256
登録日時: 9年前
住所: 愛知県

Re: 再帰呼び出しについて

#5

投稿記事 by naohiro19 » 8年前

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

funky

Re: 再帰呼び出しについて

#6

投稿記事 by funky » 8年前

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

naohiro19さん
なるほどです。

かずま

Re: 再帰呼び出しについて

#7

投稿記事 by かずま » 8年前

再帰呼び出ししようとすると、引数が 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

Re: 再帰呼び出しについて

#8

投稿記事 by funky » 8年前

かずまさん

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

n &= 0xffff;

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

アバター
tk-xleader
記事: 153
登録日時: 8年前
連絡を取る:

Re: 再帰呼び出しについて

#9

投稿記事 by tk-xleader » 8年前

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

n &= 0xffff;

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

non
記事: 1097
登録日時: 8年前

Re: 再帰呼び出しについて

#10

投稿記事 by non » 8年前

かずま さんが書きました:再帰呼び出ししようとすると、引数が 2つ要るのですが、むりやり 1つにしてみました。
なぜ、引数が2つ必要なのか、説明をお願いします。
non

かずま

Re: 再帰呼び出しについて

#11

投稿記事 by かずま » 8年前

non さんが書きました: なぜ、引数が2つ必要なのか、説明をお願いします。
例えば、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
記事: 1097
登録日時: 8年前

Re: 再帰呼び出しについて

#12

投稿記事 by non » 8年前

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

かずま

Re: 再帰呼び出しについて

#13

投稿記事 by かずま » 8年前

non さんが書きました: 方法1
 static変数を使い、1回目か2回目以降かを区別する。
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;
}
non さんが書きました: 方法2
 最後の素因数の後に、Xがつくのかつかないのかを判断する。
 最後の素因数の次には n/rは1になるので、それで判断する。
 発想の転換ですね。
これはどういうことでしょうか?
もう少し具体的な説明をお願いします。

non
記事: 1097
登録日時: 8年前

Re: 再帰呼び出しについて

#14

投稿記事 by non » 8年前

かずま さんが書きました:もう少し具体的な説明をお願いします。
申し訳ありません。私が勘違いしておりました。
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;
}
non

閉鎖

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