プログラムを参考に次のプログラムを作成せよ

[グフ]

ソースは4桁の2進数をすべて表示するプログラムなのですが、これを参考に男女各5人が同時にランダムに異性を1人選ぶときにカップルが出来る確率を求めるプログラㇺを書きたいのですがこのプログラムを参考にでは無理ではないですか？

再帰は総当たりの計算に使用できると書いてありましたが、本問題は総当たりではないような気がするのですが・・・

コード:

#include<stdio.h>
#define M 4
#define N 2

int c[M];

void show(void)
{
	int j;
	for(j = 0; j < M; j++) 
	{printf("%d", c[j]);

	}
	printf("\n");
}

void carry(int i)
{
	if(i == M) 
	{
		show();
	}
	else 
	{
		for(c[i] = 0; c[i] < N; c[i]++)
		{
			carry(i + 1);
		}
	}

}

int main(void)
{
	carry(0);
	return 0;
}

[かずま]

このプログラムを参考にでは無理ではないですか？

無理ではありません。
カップルが一組もできない確率を総当たりで求めて、
1から引けばよいと思います。

コード:

#include <stdio.h>   // printf
#include <math.h>    // pow

#define M 5     // 男性の人数
#define N 5     // 女性の人数

int c[M];       // c[i] は i番の男性の相手の女性の番号、
int k;

void show(int j)   // j は女性の番号
{
	int i;
	if (j == N)
		k++;       // カップルができなかった
	else
		for (i = 0; i < M; i++)
			if (c[i] != j)   // i番の男性の相手が j番の女性でなければ
				show(j + 1); //    次の女性について調べる
}

void carry(int i)  // i は男性の番号
{
	if (i == M)    // 男性の相手が全部決まったら
		show(0);   //   女性の先頭から調べる
	else 
		for (c[i] = 0; c[i] < N; c[i]++)
			carry(i + 1);
}

int main(void)
{
	double p = pow(N, M) * pow(M, N);
	carry(0);
	printf("1 - %d / %.15g = %.15g\n", k, p, 1 - k / p);
	return 0;
}

実行結果

コード:

1 - 2764880 / 9765625 = 0.716876288

私の勘違いで、完全に間違っているかもしれません。
その時は、ご指摘ください。
正しいと思ったら、どのように理解したかを説明してください。
理解できない場合は、どこが分からないかを質問していただければ、
ヒントを出したり、解説を行いたいと思います。

ところで、これは何の問題ですか？
出典を教えてください。

[グフ]

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

書いていただかれたプログラムが正しいか以前に、再帰の仕組み、また再帰のプログラムの読み方が少し微妙だと思うので教えていただきたいです。思ったことを下に書いていくので拙い文になりますが間違えていたら指摘お願いします。

まず最初にcarry関数が実行されると思うのですが、i==Mになるまでelse文の中のfor文の中のcarryが繰り返され、これが再帰だということですよね？

そこでの読み方についてです。
c[0] = 0 でcarry(1)
c[1] = 0 でcarry(2)
c[2] = 0 でcarry(3)
c[3] = 0 でcarry(4)
c[4] = 0 でcarry(5)

でそれぞれ再帰が実行されますよね？
しかし、for文なのでc = 5になるまで　cに1ずつ足していくんですよね？
なので
c[0] = 1 でcarry(1)
c[0] = 2 でcarry(1)
c[0] = 3 でcarry(1)
c[0] = 4 でcarry(1)

c[1] = 1 でcarry(2)
c[1] = 2 でcarry(2)
c[1] = 3 でcarry(2)
c[1] = 4 でcarry(2)

c[2] = 1 でcarry(3)
c[2] = 2 でcarry(3)
c[2] = 3 でcarry(3)
c[2] = 4 でcarry(3)

c[3] = 1 でcarry(4)
c[3] = 2 でcarry(4)
c[3] = 3 でcarry(4)
c[3] = 4 でcarry(4)

c[4] = 1 でcarry(5)
c[4] = 2 でcarry(5)
c[4] = 3 でcarry(5)
c[4] = 4 でcarry(5)
という感じになり、それぞれの配列に0~4までの数字が格納されてi == Mになりshow関数へ移動　
j = 0でj == N でないためelse文

で、ここで分からないのがfor文の中のif文の仕組みです。
c != j 、iの初期値が0なのでc[0] != jで表現した場合、c[0]に格納した値のうちjと一致するものでなければshow関数を再帰という意味でしょうか？
それをc[5]までやり、出来なかった場合のみを数え上げてそれを1からひく、といった感じでしょうか？

拙い文で本当に申し訳ないのですが、説明が難しくて理解してる範囲ではこれが限界です。

また、説明文とは別に答えが若干違うかなと思いました。

プログラム関係なしに数学で考えると男1人が女子を選んでカップルにならない確率は4/5、それが5人なので(4/5)^5
これを1からひくと

1-(4/5)^5＝2101/3125となるような・・・
pはpowを1つ減らせばいいと思うのですが、kの値はなぜこんな大きくなってるのかなと疑問があります。

この問題は学校で出された課題です。なので出典がどことまではちょっと分からないです・・・

[グフ]

色々試してみた結果showのfor文のjをc［j］に変えたところうまく出力されました！
出力の結果の疑問は解けましたので説明について添削お願いします。

[かずま]

次のプログラムは、男性M人、女性N人の場合に、
全パターンと、できたカップルを表示するものです。

コード:

#include <stdio.h>   // printf
#include <math.h>    // pow

int M = 5;   // 男性の人数
int N = 5;   // 女性の人数
int b[10];   // b[i] は i番の男性が選択した女性の番号
int g[10];   // g[j] は j番の女性が選択した男性の番号
int k;       // カップルができない個数

void show(void)
{
	for (int i = 0; i < M; i++) printf(" %d", b[i]);
	printf(" :");
	for (int j = 0; j < N; j++) printf(" %d", g[j]);
	printf(" :");
	int m = 0;
	for (int i = 0; i < M; i++)
		if (g[b[i]] == i) printf(" %d-%d", i, b[i]), m++;
	if (m == 0) k++;
	printf("\n");
}

void girl(int j)  // j は女性の番号
{
	if (j == N)     // 女性の相手が全部決まったら
		show();     //   全員の選択結果を表示
	else 
		for (g[j] = 0; g[j] < M; g[j]++)
			girl(j + 1);
}

void boy(int i)  // i は男性の番号
{
	if (i == M)    // 男性の相手が全部決まったら
		girl(0);   //   女性の先頭から調べる
	else 
		for (b[i] = 0; b[i] < N; b[i]++)
			boy(i + 1);
}

int main(void)
{
	while (1) {
		printf("enter M N>> ");
		if (scanf("%d%d", &M, &N) != 2) break;
		k = 0;
		boy(0);
		double p = pow(N, M) * pow(M, N);
		printf("1 - %d / %.15g = %.15g\n", k, p, 1 - k / p);
	}
}

実行結果

コード:

enter M N>> 1 1
0 : 0 : 0-0
1 - 0 / 1 = 1
enter M N>> 2 1
 0 0 : 0 : 0-0
 0 0 : 1 : 1-0
1 - 0 / 2 = 1
enter M N>> 2 2
 0 0 : 0 0 : 0-0
 0 0 : 0 1 : 0-0
 0 0 : 1 0 : 1-0
 0 0 : 1 1 : 1-0
 0 1 : 0 0 : 0-0
 0 1 : 0 1 : 0-0 1-1
 0 1 : 1 0 :
 0 1 : 1 1 : 1-1
 1 0 : 0 0 : 0-1
 1 0 : 0 1 :
 1 0 : 1 0 : 0-1 1-0
 1 0 : 1 1 : 1-0
 1 1 : 0 0 : 0-1
 1 1 : 0 1 : 1-1
 1 1 : 1 0 : 0-1
 1 1 : 1 1 : 1-1
1 - 2 / 16 = 0.875
enter M N>> 3 3
 0 0 0 : 0 0 0 : 0-0
 0 0 0 : 0 0 1 : 0-0
 0 0 0 : 0 0 2 : 0-0
 0 0 0 : 0 1 0 : 0-0
 0 0 0 : 0 1 1 : 0-0
 0 0 0 : 0 1 2 : 0-0
  ...
 1 2 0 : 1 2 0 :
 1 2 0 : 1 2 1 : 1-2
 1 2 0 : 1 2 2 :
 1 2 0 : 2 0 0 : 0-1 2-0
 1 2 0 : 2 0 1 : 0-1 1-2 2-0
 1 2 0 : 2 0 2 : 0-1 2-0
 1 2 0 : 2 1 0 : 2-0
 1 2 0 : 2 1 1 : 1-2 2-0
 1 2 0 : 2 1 2 : 2-0
  ...
 2 2 2 : 2 1 2 : 2-2
 2 2 2 : 2 2 0 : 0-2
 2 2 2 : 2 2 1 : 1-2
 2 2 2 : 2 2 2 : 2-2
1 - 156 / 729 = 0.786008230452675
enter M N>> 

表示のフォーマットは次の通り。
　男性が選択した女性の番号 : 女性が選択した男性の番号 : できたカップル

男性1人女性1人の場合、お互いに選択肢がなく、カップルができます。

男性2人女性1人の場合もカップルができます。

男性2人女性2人の場合、すべての組み合わせ 2⁴ = 16通りのうち
　2組のカップルができるのが 2通り。
　1組のカップルができるのが 12通り。
　カップルができないのが 2通り。

男性3人女性3人の場合、すべての組み合わせ 3⁶ = 729通りのうち
　カップルができないのが 156通り。

男性4人女性4人の場合と男性5人女性5人の場合は時間がかかるので、
リダイレクトでファイルに出力して、表示させないようにしましょう。
男性5人女性5人の場合は表示させなくても数十秒かかるでしょう。

[かずま]

プログラム関係なしに数学で考えると男1人が女子を選んでカップルにならない確率は4/5、それが5人なので(4/5)^5
これを1からひくと

1-(4/5)^5＝2101/3125となるような・・・

男性2人女性2人の場合、1-(1/2)^2 = 3/4 となりますか？

[かずま]

コード:

で、ここで分からないのがfor文の中のif文の仕組みです。
c[i] !=  j 、iの初期値が0なのでc[0] != jで表現した場合、
c[0]に格納した値のうちjと一致するものでなければ
show関数を再帰という意味でしょうか？
それをc[5]までやり、出来なかった場合のみを数え上げてそれを1からひく、
といった感じでしょうか？

コード:

c[i] と書くと、[i]がイタリック(斜体)タグと解釈されて消えて c になるので、
コードタグを使っています。

さて、#5 のプログラムは、男女の全パターンを求めてからカップルが
できるかどうかチェックしているので、5対5 の場合、
5¹⁰ = 9765625通りを求めていて、とても時間がかかります。

#2 のプログラムでは、男性が女性を選択するパターンだけを求めて、
女性は、先頭の人から順に見て、
　カップルが成立しなかった場合、次の女性に行く。
　カップルが成立した場合、次の女性に行かない。
このようにして、早い段階で次の女性に行く無駄を回避しています。