【問題】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行文をプリントする。
コードを見て頑張って理解するので,コードだけでも構いません。よろしくお願いします。
再帰関数
Re: 再帰関数
n重のforがどこに必要になるのかさっぱり謎だし
再帰をどこにどう使うと嬉しいことがあるのかも意味不明すぎるので,
そこらへんの話を完全に無視した直感的なコードを示す.もちろん再帰を使ってない.
1mmでも参考になれば.
#「再帰」をやらせること自体が目的の課題なんだろうけど.
再帰をどこにどう使うと嬉しいことがあるのかも意味不明すぎるので,
そこらへんの話を完全に無視した直感的なコードを示す.もちろん再帰を使ってない.
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: 再帰関数
挑戦してみたら素で失敗してワラタ
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: 再帰関数
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;
}
Re: 再帰関数
再帰を使わずに書いてみました。
int型が16ビットの環境では足りません。
int型で少なくとも0~16,777,216の整数を保存できる環境で実行してください。(n<=8の場合)
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: 再帰関数
問題文にある解き方の説明が理解されていないようなので
例を挙げて解説します。
n が 4 になると、a[3] の for文を追加しなければなりません。
実行中に決まる n に従ってコードを実行時に変更することはできません。
(できる言語(Lispなど?)もありますが)
このコードは次の説明にも合致します。
例を挙げて解説します。
n が 3 の場合、次のように 3重の for文で簡単に解決できます。この問題は, n重のfor文を書くことができれば簡単に解決できるのだが,
nが可変なため,n重の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 に従ってコードを実行時に変更することはできません。
(できる言語(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行文をプリントする。