Problem 10759 Dice Throwing，骰子點數的機率

此題是需要你輸入整數 n 和整數 x，問你擲 n 次骰子至少大於 x 點的機率是多少，以最簡分數表示。

除骰第一次骰子的點數機率是固定外，只要是骰一次以上的點數機率，都是由第一次骰子的點數機率衍生而來。你要創建一個類似以下的表格的陣列：
當陣列第一列定義好所有點數出現次數後，而當第二列的每一個數值會有這樣一個公式：當 i > 1，dice[i][j] = dice[i-1][j-6] + dice[i-1][j-5] + dice[i-1][j-4]+dice[i-1][j-3]+dice[i-1][j-2]+dice[i-1][j-1]。以上公式行的索引要在合理範圍，也就是說 j-6、j-5、....等不能是負值，不然會出錯。所以可以利用函式將此陣列創建出來，C 語言程式碼如下：

#define MAXN 24
#define MAXX 150

unsigned long long int dice[MAXN + 1][MAXX + 1];

void creat()
{
    dice[1][1] = 1, dice[1][2] = 1, dice[1][3] = 1, 
    dice[1][4] = 1, dice[1][5] = 1, dice[1][6] = 1;
    int i, j;
    for (i = 2; i <= MAXN; i ++)
        for (j = 2; j <= MAXX; j ++)
        {
            if (j - 6 >= i - 1) dice[i][j] += dice[i - 1][j - 6];
            if (j - 5 >= i - 1) dice[i][j] += dice[i - 1][j - 5];
            if (j - 4 >= i - 1) dice[i][j] += dice[i - 1][j - 4];       
            if (j - 3 >= i - 1) dice[i][j] += dice[i - 1][j - 3];
            if (j - 2 >= i - 1) dice[i][j] += dice[i - 1][j - 2];
            if (j - 1 >= i - 1) dice[i][j] += dice[i - 1][j - 1];   
        }
}

而主程式只須這樣寫， C語言程式碼如下：

creat();
int i, j, n, x;
unsigned long long int total, d;
while (scanf("%d %d", &n, &x) == 2)
{
    if (n == 0 && x == 0) break;
    total = 0, d = 0;
    for (i = 0; i <= MAXX; i ++ )
    {
        total += dice[n][i];
        if (i >= x) d += dice[n][i]; 
    }  
    while (total % 2 == 0 && d % 2 == 0)
        total /= 2, d /= 2;
    while (total % 3 == 0 && d % 3 == 0)
        total /= 3, d /= 3;
    if (d == 0) printf("0\n");        
    else if(d == total) printf("1\n");
    else printf("%lld/%lld\n", d, total);
}

By David.K

p10759題目連結
回ACM題庫目錄
回首頁