再帰関数

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

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。

BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF

トピックのレビュー
   

展開ビュー トピックのレビュー: 再帰関数

Re: 再帰関数

#9

by かずま » 4年前

問題文にある解き方の説明が理解されていないようなので
例を挙げて解説します。
この問題は, 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行文をプリントする。

Re: 再帰関数

#8

by みけCAT » 4年前

再帰を使わずに書いてみました。
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;
}

Re: 再帰関数

#7

by Math » 4年前

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

Re: 再帰関数

#6

by Math » 4年前

まず、閏年補正ですね

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

Re: 再帰関数

#5

by Math » 4年前

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 を伴って終了しました。
このウィンドウを閉じるには、任意のキーを押してください . . .

Re: 再帰関数

#4

by usao » 4年前

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

コード:

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 ); としてコールする

Re: 再帰関数

#3

by かずま » 4年前

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

コード:

#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 を適当な引数で呼び出す
}

Re: 再帰関数

#2

by usao » 4年前

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;  }
        }
    }
}
#「再帰」をやらせること自体が目的の課題なんだろうけど.

再帰関数

#1

by ice » 4年前

【問題】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行文をプリントする。

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

ページトップ