学步园

题目：10 个房间里放着随机数量的金币。每个房间只能进入一次，并只能在一个房间中拿
金币。一个人采取如下策略：前四个房间只看不拿。随后的房间只要看到比前四个房间都多
的金币数，就拿。否则就拿最后一个房间的金币。
编程计算这种策略拿到最多金币的概率。

解法如下：

1.理论分析

2.编程求解

一.理论分析

设随机放入的10个房间的金币从小到大排序后是g1, g2, g3, ... , g10.

1.假设我们采用开四个房间的策略。
令看过的四个房间中的金币最大值是m。那么要获得最后胜利的话，
m只能等于g4, g5, g6, g7, g8, g9中的一个。

当 m=g4 时，这时看过的四个房间金币分布有4！种可能，即g1, g2, g3, g4进行全排列。
后面6个房间排布可能性有6！种。而总排布的可能性是10！。
在进入之后的6个房间时，如果房间里的金币数是g5-g9中的任意一个，都比m大，都要拿，则任务失败。
也就是说，这种情况下，获胜的可能性是1/6（6个房间里必须第一次选中g10金币房间）。
或者换种说法：第5个房间必须是g10才能赢。

推出当 m=g4 时，
p(win|m=g4) = (1/6) * (4! * 6!) / 10! = 1/1260
p(win|m=g4) = 1*5! *(4!) / 10! = 1/1260（第5个房间固定g10，后面5中全排列） 

当m=g5时，看过的四个房间里有三个房间含有的金币数量是g1, g2, g3, g4 中的三个。
剩下的一个必然在后面六个房间的一个里。
也就是说，进入后6个房间时进到金币数少于g5的房间不会失败也不会获胜。
那么获胜概率取决于剩下的5个房间，即1/5。

当 m=g5 时，
p(win|m=g5) = (1/5) * c(4 3) * (4! * 6!) / 10! = 2/525
p(win|m=g5) = 6 *1*4! * (c(4 3)* 4! ) / 10! = 2/525
同理可得

p(win|m=g6) = (1/4) * c(5 3) * (4! * 6!) / 10! = 1/84
p(win|m=g7) = (1/3) * c(6 3) * (4! * 6!) / 10! = 2/63
p(win|m=g8) = (1/2) * c(7 3) * (4! * 6!) / 10! = 1/12
p(win|m=g9) = c(8 3) * (4! * 6!) / 10! = 4/15

或者直观表示：
p(win|m=g6) = 6*5*1*3! * (c(5 3)* 4! ) / 10! 
p(win|m=g7) = 6*5*4*1*2! * (c(6 3)* 4! ) / 10! 
p(win|m=g8) = 6*5*4*3*1*1！ * (c(7 3)* 4! ) / 10! 
p(win|m=g9) = 6*5*4*3*2*1* (c(8 3)* 4! ) / 10! 

把以上6种情况的概率全部加起来（因为是独立事件）
即是四房间策略的获胜概率：2509/6300，约等于0.3982539683。

进一步验证，考虑只看三个房间的策略：
p(win|m=g3) = (1/7) * (3! * 7!) / 10! = 1/840
p(win|m=g4) = (1/6) * c(3 2) * (3! * 7!) / 10! = 1/240
p(win|m=g5) = (1/5) * c(4 2) * (3! * 7!) / 10! = 1/100
p(win|m=g6) = (1/4) * c(5 2) * (3! * 7!) / 10! = 1/48
p(win|m=g7) = (1/3) * c(6 2) * (3! * 7!) / 10! = 1/24
p(win|m=g8) = (1/2) * c(7 2) * (3! * 7!) / 10! = 7/80
p(win|m=g9) = c(8 2) * (3! * 7!) / 10! = 7/30
相加的结果是3349/8400，约等于0.3986904762。
只看3个房间的获胜概率确实比4个房间要略高一点点。

二.编程求解

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

//rand()的用法  rand()不需要参数，它会返回一个从0到最大随机数的任意整数，
//最大随机数的大小通常是固定的一个大整数。
int genrand(int a, int b)
{
	return rand()%(b-a+1)+a;
}

void gennum(int *a,int size)//随机产生10个数 
{
	for (int i=0;i<size;i++)
	{
		a[i]=genrand(1,10000);
	}
}

int getnum(int *a, int size)//按规则取出的数
{
	int i,max=0;
	for (int i=0;i<4;i++)
	{
		if (a[i]>max) 
			max=a[i];
	}
	for (i=4;i<size-1;i++)
	{
		if (a[i]>max)
		 return a[i]; 
	}
	return a[size-1];
}

int getmax(int *a, int size)
{
	int max=0;
	for (int i=0;i<size;i++)
	{
		if (a[i]>max) max=a[i];
	}
	return max;
}

int success(int *a, int size)
{
	gennum(a,size);//随机产生10个数 
	if(getnum(a,size)==getmax(a,size))//按规则取出的数是否最大的数 
		return 1;
	return 0; 
}

int main()
{
	int a[10];
	int total=10000000;
	int count,k;
	k=0;
	while(k++<5)
	{
		count=0;
		for (int i=0;i<total;i++)
		{	
			if(success(a,10)) 
				count++;
		}
		cout<<"第"<<k<<"次,结果："<<(double)count/(double)total<<endl;	
	}
	return 0;
}