再帰関数

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

再帰関数

#1

投稿記事 by ice » 6ヶ月前

【問題】8以下の正整数nを入力として受け取って,それぞれ1からnまであるような整数をn個並べたものをすべて出力するプログラムを書け。重複を許す順列といえば分かりやすいかも知れない。n = 3の場合,出力の先頭の数行は,次のようになる。
1 1 1
1 1 2
1 1 3
1 2 1
.....
n^n個の結果が出力されるはずである。この問題は,n重のfor文を書くことができれば簡単に解決できるのだが,nが可変なため,n重のfor文ということはあり得ない。そこで再帰呼び出しの出番である。再帰関数には,左から何番目の数を担当するかを表す引数を渡す。
関数の中で値を生成する部分にはfor文を一つだけ書いて(プリント用にもう一つfor文が必要),担当する位置に置いてある数を順に変えていく。そして,このfor文の中で再帰呼び出しをすることがポイントである。再帰呼び出しがn段になれば,n重のfor文と同じことになる。
for文で決めた数をすぐに出力することはできないので,出力1行分の値を保存する配列が必要である。大域的に(関数の外で)宣言すること。この配列の添字には,再帰関数の引数を使う。再帰の途中ではプリントしない。再帰せずにreturnする時に1行文をプリントする。

コードを見て頑張って理解するので,コードだけでも構いません。よろしくお願いします。

アバター
usao
記事: 1565
登録日時: 6年前

Re: 再帰関数

#2

投稿記事 by usao » 6ヶ月前

n重のforがどこに必要になるのかさっぱり謎だし
再帰をどこにどう使うと嬉しいことがあるのかも意味不明すぎるので,
そこらへんの話を完全に無視した直感的なコードを示す.もちろん再帰を使ってない.
1mmでも参考になれば.

コード:

void Test( int n )
{
    //行バッファ.nは8以下とされているので8個用意すればOKってことで
    int buff[8] = { 1,1,1,1, 1,1,1,1 };

    while( true )
    {
        //行の表示と終了判定
        int count_of_n = 0;
        for( int i=0; i<n; ++i )
        {
            if( buff[i]==n )++count_of_n;
            std::cout << buff[i] << " ";
        }
        std::cout << std::endl;
        if( count_of_n==n )break;

        //次の行の内容をつくる
        for( int i=n-1; i>=0; --i )
        {
            if( ++buff[i] > n )
            {   buff[i]=1;  }
            else
            {   break;  }
        }
    }
}
#「再帰」をやらせること自体が目的の課題なんだろうけど.

かずま

Re: 再帰関数

#3

投稿記事 by かずま » 6ヶ月前

一部伏字にしたので、そこを補ってプログラムを完成し、
それを理解し、プログラムの詳しい説明をしてください。

コード:

#include 適切なヘッダ

int a[8], n;

void step(int i)
{
	if (再帰の終了条件) {
		a の内容を表示する
	}
	else {
		for (a[i] = 1; a[i] <= n; a[i]++) {
			再帰呼出し
		}
	}
}

int main(void)
{
	n に 1~8 を入力
	step を適当な引数で呼び出す
}

アバター
usao
記事: 1565
登録日時: 6年前

Re: 再帰関数

#4

投稿記事 by usao » 6ヶ月前

挑戦してみたら素で失敗してワラタ

コード:

int Buff[8];  //バッファは(何故か)関数の外におく

//引数で「何番目を担当するか」を受ける関数を書く.
//(nの値も必要だよね)
void Func(
    int nth, //「何番目」だから,一番左を示す値は1である.
    int n  //nの値は8以下の正の整数とのこと
    )
{
    //forを1個書いて,担当する位置に置いてある数を順に変えていく
    for( int i=0; i<n; ++i )
    {
        Buff[nth-1] = i+1;  //担当箇所を変える処理

        //このfor文の中で再帰呼び出しをすること
        if( nth < n )
        {  Func( nth+1, n );  }
        else
        {
            //「再帰せずにreturnする時に1行文をプリントする」
            //  このコードはこの条件が守れていない.
            //  再帰しない場合に出力しているが「returnする時」ではない.
            for( int k=0; k<n; ++k ){  std::cout << Buff[k] << " ";  }  //プリント用にもう一つfor文が必要
            std::cout << std::endl;
        }
    }
}

//※nの値が与えられた際に, Func( 1, n ); としてコールする

Math

Re: 再帰関数

#5

投稿記事 by Math » 6ヶ月前

VisualStudio2019Community  use (^^;

コード:

#include <stdio.h>
#include <math.h>

int n = 0;

void print(int i, int x) {

	if (x == 0) return;
	print(i / n, x - 1);
	putchar("12345678"[i % n]);
	putchar(' ');
}

int main(void) {

	int i = 0;
	char a;
	
	printf(" n = "); a = getchar();	printf("%c\n", a);

	n = (int)a;  printf("%d\n", n);  n = n - 48; printf("%d\n", n);

	int x = (int)(pow((double)n,(double) n) - 1);

	do {
		print(i, n);
		putchar('\n');
	} while (i++ != x);

	return 0;
}

実行

コード:

 n = 2
2
50
2
1 1
1 2
2 1
2 2

C:\19\VS2019\c\001\c_05_15_a\Debug\c_05_15_a.exe (プロセス 12452) は、コード 0 を伴って終了しました。
このウィンドウを閉じるには、任意のキーを押してください . . .


Math

Re: 再帰関数

#6

投稿記事 by Math » 6ヶ月前

まず、閏年補正ですね

と書いたようにそれ以外はそのまま。
むつかしいようなことは皆無なので どうしても質問者 様の手におえない質問があったら聞いてね

Math

Re: 再帰関数

#7

投稿記事 by Math » 6ヶ月前

失礼投稿場所を間違えました

アバター
みけCAT
記事: 6235
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 再帰関数

#8

投稿記事 by みけCAT » 6ヶ月前

再帰を使わずに書いてみました。
int型が16ビットの環境では足りません。
int型で少なくとも0~16,777,216の整数を保存できる環境で実行してください。(n<=8の場合)

コード:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int n;
	int i, j;
	int max;
	int* data;
	if (scanf("%d", &n) != 1) return 1;
	if ((data = malloc(sizeof(int) * n)) == NULL) {
		perror("malloc");
		return 1;
	}
	max = 1;
	for (i = 0; i < n; i++) max *= n;
	for (i = 0; i < max; i++) {
		int cur = i;
		for (j = 0; j < n; j++) {
			data[j] = cur % n + 1;
			cur /= n;
		}
		printf("%d", data[n - 1]);
		for (j = n - 2; j >= 0; j--) {
			printf(" %d", data[j]);
		}
		putchar('\n');
	}
	free(data);
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

かずま

Re: 再帰関数

#9

投稿記事 by かずま » 6ヶ月前

問題文にある解き方の説明が理解されていないようなので
例を挙げて解説します。
この問題は, n重のfor文を書くことができれば簡単に解決できるのだが,
nが可変なため,n重のfor文ということはあり得ない。
n が 3 の場合、次のように 3重の for文で簡単に解決できます。

コード:

#include <stdio.h>

int main(void)
{
	int n = 3, a[8];
	for (a[0] = 1; a[0] <= n; a[0]++)
		for (a[1] = 1; a[1] <= n; a[1]++)
			for (a[2] = 1; a[2] <= n; a[2]++)
				for (int i = 0; i < n; i++)
					printf("%d%c", a[i], i == n-1 ? '\n' : ' ');
}
n が 4 になると、a[3] の for文を追加しなければなりません。
実行中に決まる n に従ってコードを実行時に変更することはできません。
(できる言語(Lispなど?)もありますが)
そこで再帰呼び出しの出番である。再帰関数には,
左から何番目の数を担当するかを表す引数を渡す。

コード:

#include <stdio.h>

int n, a[8];

void func(int i)
{
	if (i < n)
		for (a[i] = 1; a[i] <= n; a[i]++)
			func(i + 1);
	else
		for (i = 0; i < n; i++)
			printf("%d%c", a[i], i < n-1 ? ' ' : '\n');
}

int main(void)
{
	n = 3;
	func(0);
}
このコードは次の説明にも合致します。
関数の中で値を生成する部分にはfor文を一つだけ書いて
(プリント用にもう一つfor文が必要),
担当する位置に置いてある数を順に変えていく。
そして,このfor文の中で再帰呼び出しをすることがポイントである。
再帰呼び出しがn段になれば,n重のfor文と同じことになる。

for文で決めた数をすぐに出力することはできないので,
出力1行分の値を保存する配列が必要である。
大域的に(関数の外で)宣言すること。
この配列の添字には,再帰関数の引数を使う。
再帰の途中ではプリントしない。
再帰せずにreturnする時に1行文をプリントする。

返信

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