程序员面试题精选（32）：金币概率问题（威盛笔试题）

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

int genrand(int a, int b)

{

 return rand()%(b-a+1)+a;

}

void gennum(int *a, int size)

{

 for (int i=0;i<size;i++)

 {

  a[i] = genrand(1,10000);

 }

}

int getnum(int *a, int size)

{

 int max4 = 0;

 for (int i=0;i<4;i++)

 {

  if (a[i]>max4) max4 = a[i];

 }

 for (i=4;i<size-1;i++)

 {

  if (a[i]>max4) 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);

 if (getnum(a,size)==getmax(a,size))

  return 1;

 return 0; 

}

主程序调用：

srand(LOWORD(GetCurrentTime()));

 int a[10];

 int total = 10000000;

 int count = 0;

 for (int i=0;i<total;i++)

 {

  if (success(a,10)) count++;

 }

 cout<<(double)count/(double)total<<endl;

最后得到结果是：成功的概率接近40%，例如39.826%