Ｃ言語のソースコードの書き方

質問

Ｃ言語のソースコードの書き方に関する質問です。
０を５個と１を４個の、合わせて９個の数字を並べて出来上がる数列のパターン（126通り）を全て羅列させるプログラムを作りたいと考えていますが、そのためにどういった方針を立ててソースコードを書けばよいかが分かりません。
どういった構造かだけでも構いませんので、教えて頂けると幸いです。
よろしくお願いします。

回答No.2

hanabutako · ベストアンサー

という方針で書くとこんな感じね。
#include <stdio.h>

void
print_pattern(char pattern[], int size)
{
for (int i = 0; i < size; i++) {
printf("%c", pattern[i]);
}
printf("\n");
}

void
iter(char pattern[], int end, int n, int m)
{
if (n == 0 && m == 0) {
print_pattern(pattern, end);
return;
}

if (n == 0) {
pattern[end] = 'b';
iter(pattern, end + 1, n, m - 1);
return;
}
if (m == 0) {
pattern[end] = 'a';
iter(pattern, end + 1, n - 1, m);
return;
}

pattern[end] = 'b';
iter(pattern, end + 1, n, m - 1);
pattern[end] = 'a';
iter(pattern, end + 1, n - 1, m);
}

int
main(void)
{
int m = 5, n = 4;
char pattern[m + n];
iter(pattern, 0, m, n);
return 0;
}

お礼

回答ありがとうございます。

回答No.4

tsunji

数字的には9ビットの2進数なので、0～511までの数字となります。
forで0～511までループし、2進数に変換して、0が5個、1が4個の
組み合わせの数字を見つければいいだけです。

回答No.3

hanabutako

色々と蛇足だった。これでいい。
void
iter(char pattern[], int end, int n, int m)
{
if (n == 0 && m == 0) {
print_pattern(pattern, end);
}

if (n > 0) {
pattern[end] = 'a';
iter(pattern, end + 1, n - 1, m);
}
if (m > 0) {
pattern[end] = 'b';
iter(pattern, end + 1, n, m - 1);
}
}

回答No.1

hanabutako

コンピューターのプログラムを考えるとき、難しい問題を簡単な問題に分解して考えるのが普通です。
この問題、0が1個、1が1個で出来上がるパータンはどうやって出しますか？
0が2個、１が1個だとどうでしょう。0が3個、1が1個だとどうでしょう？
0が3個、1が1個のパターンは、
実は、一番最初に0を置く場合、0が2個、1が1個のパターンと同じです。
逆に、1が最初に来る場合、あとは0しか来ません。

数字の0と文字の0が紛らわしいので、ちょっと問題を変えます。
一般化すると、aをn個、bをm個の組み合わせの表示は、
nが0個の場合、bをm個並べるという1パターンしかありません。
mが0個の場合も、aをn個並べるという1パターンしかありません。
それ以外の場合、
aを最初において、そのあと、aをn-1個、bをm個並べるパターンか
bを最初において、そのあと、aをn個、bをm-1個並べるパターンとなるでしょう。

aをn-1個、bをm個並べるパターンは上の問題のnとmの数字を入れ替えれば同じ考えでできます。
あとは、これまでおいたものを配列などに保存しておいて、n=0、m=0となったときに表示するようにすればよいでしょう。

こういうやり方を再帰呼び出しと言います。自分のところでできることは自分のところでやり、自分のところで解けないものは自分を違ったパラメーターでもう一度呼び出して解くというやり方です。

お礼

回答ありがとうございます。