nyoj-彈球II



彈球II

描述

遊戲廳裡有一種很常見的遊戲機，裡面有很多根管子有規律地排成許多行。小球從最上面掉下去，碰到管子會等機率地往管子左邊或者右邊的空隙掉下去。不過在最靠邊的小球隻會往一邊掉（如圖，灰色小球隻可能掉到右邊空隙）。現在已知共2 * n - 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      

來源

GDUT校賽

上傳者

ACM_李如兵

    本題是計算機率的問題，也就是從頂端扔下一個小球，輸出在下面每個出口處的機率的大俠，精确到小數點後的第六位。在奇數行，總有偶數跟柱子，有奇數個空，在偶數行，總有奇數個柱子，偶數個空，而且奇數和偶數交替進行。第一行和最後一行都是奇數行，是以開始和結束的空總是相同的。解決本題，設兩個一維數組，進行一次for循環即可。分别為a[11],b[11]。在第一行第k個空投入，則a[k]=1；在第二行，則有a[k]=a[k+1]=0.5;可以看出。每兩行之間遵從這樣的規律，從奇數行到偶數行，a[k]=(a[k]+a[k+1])/2.0;邊界處有a[1]=a[i]/2.0,a[m-1]=a[m]/2.0;之後a[m]指派為0，因為偶數行沒有第m個空，同樣從偶數行到奇數行，也遵從相同規律，也之後邊界處不同，在邊界處有a[1]=a[1]+(a[2]/2.0),a[m]=a[m-1]/2.0;隻要把握好這個規律，解決這道題就算是很簡單的問題了

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
double mm[210][12];

int main()
{
    int t,n,m,k,i,j;
    scanf("%d",&t);
    while(t--)
    {
        memset(mm,0,sizeof(mm));
        scanf("%d%d%d",&n,&m,&k);
        if(m==2)
            printf("1.000000\n");
        else
        {
            mm[1][k]=1;
            for(i=2;i<=2*n-1;i++)
            {
                if(i%2==0)
                {
                    mm[i][1]=mm[i-1][1]/2;//處理邊界情況
                    mm[i][m]=mm[i-1][m-1]/2;
                    for(j=2;j<m;j++)
                        mm[i][j]=(mm[i-1][j-1]+mm[i-1][j])/2;
                }
                else
                {
                    mm[i][1]=mm[i-1][1]+mm[i-1][2]/2;
                    mm[i][m-1]=mm[i-1][m-1]/2+mm[i-1][m];
                    for(j=2;j<m-1;j++)
                        mm[i][j]=(mm[i-1][j]+mm[i-1][j+1])/2;
                }
            }
            printf("%.6lf",mm[i-1][1]);
            for(j=2;j<m;j++)
                printf(" %.6lf",mm[i-1][j]);
            printf("\n");
        }
    }
    return 0;
}