In some region there exists 8 lakes,in which lived 6 sorts of birds,with the number of 1000,1500,2000,2500,3000,3500.Moreover,the number of the birds living in each lake is:2400,1100,1400,1900,2500,1800,1400,1000. Try to develop algorithms to solve the number of EACH kind of birds living in EACH lake. 先写出逻辑关系： 各种鸟总数的数组：bird[0-5] 最终各个湖泊中鸟总数的数组：lake[0-7] 最终每个湖中各种鸟的个数：l_b[0-7][0-5] 已知sum(bird[])=sum(lake[])=sumbird=13500 sum(l_b[i][0-5])=lake[i] sum(l_b[0-7][i])=bird[i] 看起来很棘手的题，总共14个已知数，逻辑关系只有四条，却有6*8=48个未知数，似乎是不大可能解决的事情 。 当然，只是看起来棘手而已。 现在用Mont Carlo法进行模拟实验求解(其实也能利用数学期望来求解，但只能得到近似数据。而且…用纯数学方法不是我风格，尽管我本科念的数学系)。把所有的鸟做为一个样本，样本容量为sumbird。每次实验从样本中随机抽取一只鸟，随机地放入任何一个湖中。总共进行sumbird次实验。 算法设计： 如果完全随机地进行这sumbird次实验的话，最终得到符合条件的结果的概率很小。这个算法所需要做的是成立一个法则，在遵循这个法则的前提下，随机地进行所有实验，而所得到的结果能够满足所有条件。显然，这个法则一定是建立在已知条件上的。 问题：定制一个怎样的法则，才能使遵循它的sumbird 次实验能够符合条件？ 初始状态：每个湖里鸟的数量为0; 最终状态：每个湖里鸟的数量为lake[i:0-5]。 第一次实验，取到i类鸟的概率为bird[i]/sumbird，把它放入j湖的概率为lake[j]/sumbird。(i∈[0,5]; j∈[0,7]) 此时，样本中还有sumbird-1只鸟，其中i类鸟还剩bird[i]-1只；j湖中已经有1只鸟。 第二次实验，取到i类鸟的概率为(bird[i]-1)/sumbird(因为已经抽走了一只)，把它放入j湖的概率为(lake[j]-1)/sumbird。(因为j湖中已经有一只鸟了，离lake[j]还差lake[j]-1只) 以此类推。 那么，可以推出，第n次实验(n∈[1,sumbird])时，抽到样本中i类鸟的概率为( bird[i]-已经抽走的i类鸟的总数)/(sumbird-已经抽走的鸟的总数);把它放入j湖中的概率为( lake[j]-j湖中已有鸟的总数)/ (sumbird-已经抽走的鸟的总数)　　…………………………※ 只要每次的抽取实验都遵循※，就能sumbird次实验后得到的结果符合所有条件。 实现方法： 易得：第n次实验时已经抽走的i类鸟的总数= sum(l_b[0-7][i]); 　　　　　　　　　j湖中已有鸟的总数= sum(l_b[j][0-5])。 设置两个动态数组： w_b[i:0-5]:在样本余下的鸟中抽到种类为i的鸟的概率； w_l[j:0-7]:将抽取到的鸟放入编号为j的湖中的概率。 易得：w_b[i]=(c[i]-sum(l_b[0-7][i]))/sumball 　　　w_l[j]= (l[i]-sum(l_b[j][0-5]))/sumball 每次抽取实验后sumball自减1。 循环进行sumball次实验，即可得符合条件的结果。
Less