紫书P327
题意：有n个人准备去超市逛，其中第i个人买东西的概率是 Pi 。逛完以后你得知有 r 个人买了东西。根据这一信息，计算每个人实际买东西的概率。输入 n （ 1 <= n <= 20 ）和r（ 0 <= r <= n) 输出每个人实际买了的东西概率
分析： “ r 个人买了东西 ” 这个事件叫做E， “ 第 i 个人买东西 ”这个事件叫做 Ei ，要求的就是 P( Ei | E ) = P ( Ei E) / P ( E ) ；
P（E)的求法利用全概率公式，每一种可能的情况的概率相加，假设 n = 4, r = 2, 有6中可能：1100，1010，1001，0110，0101，0011，其中1100的概率就是P1 * P2 * （ 1 - P3) * ( 1 - P4)， 其他的类似，假设求 P ( E1 E ) 就等于所有 P1 被访问过的，即等于1的每种可能之和，sum[ i ] 表示 vis[ i ] = 1 的概率之和，tot表示总概率和
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int Max = ;
double p[Max],sum[Max],tot;
int n,r;
int vis[Max],A[Max];
void dfs(int cur, int cnt)
{
if(cnt == r)
{
double ans = ;
for(int i = ; i <= n; i++)
{
if(vis[i])
{
ans *= p[i];
}
else
{
ans *= ( - p[i]);
}
}
for(int i = ; i <= n; i++)
{
if(vis[i])
{
sum[i] += ans;
}
}
tot += ans;
}
for(int i = cur + ; i <= n; i++)
{
if(vis[i] == )
{
vis[i] = ;
A[cnt + ] = i;
dfs(i, cnt + );
vis[i] = ;
}
}
}
int main()
{
int test = ;
while(scanf("%d%d", &n, &r) != EOF)
{
if(n == && r == )
break;
for(int i = ; i <= n; i++)
{
scanf("%lf", &p[i]);
}
memset(vis, , sizeof(vis));
memset(sum, , sizeof(sum));
tot = ;
dfs(,);
printf("Case %d:\n", ++test);
for(int i = ; i <= n; i++)
{
printf("%.6lf\n", sum[i] / tot);
}
}
return ;
}