NYOJ 374 弹球II

链接:​​click here​​

题意：

游戏厅里有一种很常见的游戏机，里面有很多根管子有规律地排成许多行。小球从最上面掉下去，碰到管子会等概率地往管子左边或者右边的空隙掉下去。不过在最靠边的小球只会往一边掉（如图，灰色小球只可能掉到右边空隙）。现在已知共2* n - 1行管子，第i行有Ai个管子，如果i是奇数，那么Ai等于m，如果i是偶数，Ai等于m- 1。小球从第1行第k个管子右边掉下去，要求小球从最后一行各个出口掉出来的概率。

第一行是一个整数t（1≤t≤50），表示有t组测试数据。

每组数据第一行有两个整数n（1≤n≤100）和m（2≤m≤10），表示有2*n-1行管子，奇数行有m个管子，偶数行有m-1个管子。

第二行是一个整数k（1≤k≤m-1），表示小球从第1行第k个管子右边掉下去。

输出 输出m-1个小数，第i个数表示小球从最后一行第i个出口出来的概率。

每个小数保留小数点后六位，小数与小数之间用一个空格隔开。

样例输入

1 3 3 2

样例输出

0.375000 0.625000

这道题比较有趣，其实是一个概率模拟问题。

思路：

定义一个二维数组，map[i][j]表示第i行第j列从管子之间掉出来的概率，因为弹球是最上面放入的，所有我们想到只要弄清楚球从每一个管子掉下去，左边和右边的概率问题分别是多少，对数组里面的元素进行一个特别的操作，这里注意，因为管子每隔一行的数量要么别上一行多一个，要么比下一行多一个，因此分奇偶讨论：

输入三个数：n,m,k刚开始放入有：map[i][k]=1;

m为奇数： 有map[i][1]=map[i-1][1]（最靠边只会往一边掉）+map[i-1][2]/2,map[i][m-1]=map[i-1][m1-1]/2+map[i-1][m];

m为偶数：有 map[i][1]=(map[i-1][1])/2,map[i][m]=(map[i-1][m-1])/2;  //处理边界，可以对照上图模仿

对于中间的数，我们知道球掉入的概率是上一行两边和的1/2。

因此，把整个过程仔细分析一遍，代码实现就不难了：

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define lowbit(a) a&-a#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);static const int inf= ~0U>>2;static const int maxn =110;double map[250][15];int main(){ //freopen("11.txt","r",stdin); //freopen("22.txt","w",stdout); int n,m,m1,k,i,j; cin>>n; while(n--) { mem(map,0); cin>>m>>m1>>k; if(m1==2) puts("1.000000"); else { map[1][k]=1; for(i=2; i<=m*2-1; i++) { if(!(i%2)) { map[i][1]=(map[i-1][1])/2,map[i][m1]=(map[i-1][m1-1])/2; //处理边界 for(j=2; j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。