Uva 11181 Probability|Given
Problem's Link: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18546
Mean:
n个人去逛超市，第i个人会购买东西的概率是Pi。出超市以后发现有r个人买了东西，问你每个人购买东西的实际概率是多少。
analyse:
转换模型：
有n个员工，每个员工被选出来的概率是Pi。最后选出了r个，问你第i个员工在这r个中的概率是多少。
设：
事件A----第i个员工在这r个员工中。
事件B----从n中选出r个员工。
求的就是在B事件发生的情况下，A事件发生的概率。
Pb为从n个员工中选出r个员工的概率总和，也就是C(n,r)中选中的r个算的是pi，未选中的算(1-pi)。
Pa为第i个员工在选中的r个员工中的概率总和，这个可以在算上面那个的时候一并算出。
最后的答案就是Pa/Pb.
数据很小，直接用递归枚举所有的组合数就行。
Time complexity: O(n^2)
Source code: