国产日韩欧美在线,国产精品激情久久,有坂深雪无码破解在线网站

本文介紹了如何用N個六邊骰子計算得到和X的概率的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學習吧！

問題描述

挑戰：
例如，當使用3個六面骰子時，得到15之和的概率是多少。這可以通過獲得5-5-5、6-6-3、3-6-6或更多選項來實現。

2個骰子的暴力解決方案-復雜性為6^2：

假設我們只有兩個六面骰子，我們可以編寫一個非常基本的代碼：

public static void main(String[] args) {
   System.out.println(whatAreTheOdds(7));
}

public static double whatAreTheOdds(int wantedSum){
    if (wantedSum < 2 || wantedSum > 12){
        return 0;
    }

    int wantedFound = 0;
    int totalOptions = 36;

    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            int sum = i+j;
            if (sum == wantedSum){
                System.out.println("match: " + i  + " " + j );
                wantedFound +=1;
            }
        }
    }

    System.out.println("combinations count:" + wantedFound);
    return (double)wantedFound / totalOptions;
}

，7的輸出將為：

匹配：1 6

匹配：2 5

匹配：3 4

匹配：4 3

匹配：5%2

匹配：6 1

組合計數：6

0.16666666666666666

問題是如何推廣算法以支持N骰子：

public static double whatAreTheOdds(int wantedSum, int numberOfDices)

因為無法動態創建嵌套的for循環，所以必須使用不同的方法。

我想到了類似的東西：

 public static double whatAreTheOdds(int sum, int numberOfDices){

    int sum;
    for (int i = 0; i < numberOfDices; i++) {
        for (int j = 1; j <= 6; j++) {

        }
    }
}

但未能提出正確的算法。

這里的另一個挑戰是-有沒有一種方法可以有效地完成這項工作，而不是在6^N的復雜性中？

推薦答案

如Alex’s answer所示，存在一個組合公式：

在這個公式中，p是擲出的數字的總和(在你的問題中是X)，n是骰子的數目，s是每個骰子的邊數(在你的問題中是6)。無論是使用循環計算二項式系數，還是使用帕斯卡三角形預計算，如果我們取s&nbsp；=-nbsp；6為常數，X-nbsp；-&nbsp；n為O(N)，則時間復雜度為O(n²)。

這里有一個替代算法，它一次計算所有的概率。其思想是使用discrete convolution來計算給定分布的兩個隨機變量之和的分布。通過使用exponentiation by squaring算法中的分治方法，我們只需進行O(log&nbsp；n)次卷積。

偽代碼在下面；sum_distribution(v, n)返回一個數組，其中索引X-nbsp；-&nbsp；n處的值是n擲骰子總數為X的組合數。

// for exact results using integers, let v = [1, 1, 1, 1, 1, 1]
// and divide the result through by 6^n afterwards
let v = [1/6.0, 1/6.0, 1/6.0, 1/6.0, 1/6.0, 1/6.0]

sum_distribution(distribution, n)
    if n == 0
        return [1]
    else if n == 1
        return v
    else
        let r = convolve(distribution, distribution)
        // the division here rounds down
        let d = sum_distribution(r, n / 2)
        if n is even
            return d
        else
            return convolve(d, v)

卷積不能在線性時間內完成，因此運行時間由長度為3n的兩個數組上的最后一個卷積控制，因為其他卷積位于足夠短的數組上。

這意味著如果使用簡單的卷積算法，計算所有概率需要O(n²)時間，如果使用fast Fourier transform，則需要O(Nlogn)時間。

這篇關于如何用N個六邊骰子計算得到和X的概率的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，