計算路數推出一定數量

Question

我是一個高中計算機科學的學生，今天我得到了一個問題：

程序說明：有骰子玩家之間的信念，在投擲三個骰子十個比九個更容易得到。你能寫一個證明或反駁這種信念的程序嗎？

有計算機計算所有可能的方式三個骰子可以 拋出：1 + 1 + 1,1 + 1 + 2，1 + 1 + 3等添加了每一種 可能性，看看有多少給出九個結果以及有多少個給定十個。如果再給十個，那麼這個信念就證明了。

我很快就摸索出蠻力的解決方案，因爲這樣

int sum,tens,nines; 
    tens=nines=0; 

    for(int i=1;i<=6;i++){ 
     for(int j=1;j<=6;j++){ 
      for(int k=1;k<=6;k++){ 
       sum=i+j+k; 
       //Ternary operators are fun! 
       tens+=((sum==10)?1:0); 
       nines+=((sum==9)?1:0); 
      } 
     } 

    } 
    System.out.println("There are "+tens+" ways to roll a 10"); 
    System.out.println("There are "+nines+" ways to roll a 9"); 

這工作得很好，和蠻力解決方案是什麼，老師要我們做的。然而，它不能縮放，我試圖找到一種方法來製作一個算法，該算法可以計算滾動 n骰子以獲得特定數字的方法數量。因此，我開始生成一些方法來獲得每個總和 n骰子。有1死，每個顯然有1個解決方案。然後我通過蠻力計算了2個和3個骰子的組合。這些是2：

有1種方式滾2
有2種方式滾動3
有3種方法對卷4
有4種方式滾5
有有5種方法對卷6
有6點的方式來滾7
有5種方法來滾8
有4種方式滾9
有3種方法對卷10
有2種方式滾動一個11
有1種方法可以滾動12

看起來很簡單;它可以用一個簡單的線性絕對值函數來計算。但事情開始變得棘手。以3：

有1種方式滾3
有3種方法對卷4
有6點的方式來滾5
有10種滾6
有15個方式來滾7
有21點的方式來滾8
有25種方式滾動9
有27種方式滾10
有27種方式滾11
有25點的方式滾動a 12
有21種方法可以滾動13
再是15點的方式來滾14
有10種滾15
有6點的方式來滾16
有3種方法對卷17
有1種方式滾18

所以我看看，我想：酷，三角數字！然而，我注意到那些討厭的25和27。所以它顯然不是三角形數，但仍然是一些多項式展開式，因爲它是對稱的。
所以我帶到谷歌，我遇到了this page，詳細說明了如何用數學來做到這一點。使用重複的派生或擴展可以很容易地找到它（雖然很長），但對於我來說編程會更困難。我不太明白第二和第三個答案，因爲我以前從未在我的數學研究中遇到這種符號或那些概念。有人能解釋我怎麼可以寫一個程序來做到這一點，或解釋在該頁面上給出的解決方案，我自己理解組合？

編輯：我正在尋找解決這一數學方法，給出了一個確切的理論值，而不是通過模擬骰子

Answer 1

使用生成函數法N(d, s)的解決方案是可能是最容易編程。您可以使用遞歸來很好地模擬問題：

public int numPossibilities(int numDice, int sum) { 
    if (numDice == sum) 
     return 1; 
    else if (numDice == 0 || sum < numDice) 
     return 0; 
    else 
     return numPossibilities(numDice, sum - 1) + 
       numPossibilities(numDice - 1, sum - 1) - 
       numPossibilities(numDice - 1, sum - 7); 
} 

乍一看，這看起來像是一個相當直接和有效的解決方案。但是您會注意到許多相同的numDice和sum值的計算可能會重複並重新計算一遍又一遍，使得該解決方案可能比您最初的強力方法效率更低。例如，在計算所有計數3骰子，我的方案共15106次跑numPossibilities功能，而不是你的循環只需要6^3 = 216處決。

爲了使此解決方案可行，您需要添加一項技術 - 以前計算結果的記憶（緩存）。例如，使用HashMap對象，您可以存儲已經計算出的組合，並在運行遞歸之前先參考這些組合。當我實現緩存時，numPossibilities函數只運行總計151來計算3骰子的結果。

爲您增加骰子的數量提高效率變得更大（結果是基於仿真我自己實施的解決方案）：

# Dice | Brute Force Loop Count | Generating-Function Exec Count 
3  | 216 (6^3)    | 151 
4  | 1296 (6^4)    | 261 
5  | 7776 (6^5)    | 401 
6  | 46656 (6^6)   | 571 
7  | 279936 (6^7)   | 771 
... 
20  | 3656158440062976  | 6101 

Answer 2

退房Monte Carlo Methods他們通常與inputsize線性擴展。在這種情況下，這個例子很簡單，我們假設一旦投擲骰子不會影響另一個而不是計算組合，我們可以簡單地計算隨機拋出的骰子的面積總和（足夠多次）。

public class MonteCarloDice { 

    private Map<Integer, Integer> histogram; 
    private Random rnd; 
    private int nDice; 
    private int n; 

    public MonteCarloDice(int nDice, int simulations) { 
     this.nDice = nDice; 
     this.n = simulations; 
     this.rnd = new Random(); 
     this.histogram = new HashMap<>(1000); 
     start(); 
    } 

    private void start() { 
     for (int simulation = 0; simulation < n; simulation++) { 
      int sum = 0; 
      for (int i = 0; i < nDice; i++) { 
       sum += rnd.nextInt(6) + 1; 
      } 
      if (histogram.get(sum) == null) 
       histogram.put(sum, 0); 
      histogram.put(sum, histogram.get(sum) + 1); 
     } 
     System.out.println(histogram); 
    } 


    public static void main(String[] args) { 
     new MonteCarloDice(3, 100000); 
     new MonteCarloDice(10, 1000000); 
    } 

} 

誤差與模擬的數目，但在CPUTIME的成本降低，但上述值是相當快的。

3骰子

{3=498, 4=1392, 5=2702, 6=4549, 7=7041, 8=9844, 9=11583, 10=12310, 11=12469, 12=11594, 13=9697, 14=6999, 15=4677, 17=1395, 16=2790, 18=460} 

10骰子

{13=3, 14=13, 15=40, 17=192, 16=81, 19=769, 18=396, 21=2453, 20=1426, 23=6331, 22=4068, 25=13673, 24=9564, 27=25136, 26=19044, 29=40683, 28=32686, 31=56406, 30=48458, 34=71215, 35=72174, 32=62624, 33=68027, 38=63230, 39=56008, 36=71738, 37=68577, 42=32636, 43=25318, 40=48676, 41=40362, 46=9627, 47=6329, 44=19086, 45=13701, 51=772, 50=1383, 49=2416, 48=3996, 55=31, 54=86, 53=150, 52=406, 59=1, 57=2, 56=7} 

Answer 3

，因爲你的第一個卷確定你不需要蠻力什麼值可用於第二卷，第一卷和第二卷確定第三卷。我們以十個例子爲例，假設你滾動6，所以10-6=4意味着你仍然需要4。對於第二卷，您至少需要3，因爲您的第三卷應該至少包括1。所以第二卷從1到3。假設你的第二卷是2，你有10-6-2=2，這意味着你的第三卷是2，沒有別的辦法。數十

僞代碼：

tens = 0 

for i = [1..6] // first roll can freely go from 1 to 6 
    from_j = max(1, 10 - i - 6) // We have the first roll, best case is we roll a 6 in the third roll 
    top_j = min(6, 10 - i - 1) // we need to sum 10, minus i, minus at least 1 for the third roll 
    for j = [from_j..to_j] 
     tens++ 

注意，每個循環加1，所以在最後，你知道這個代碼循環正是27倍。

下面是所有18個值的Ruby代碼（對不起，它不是Java，但它可以很容易地遵循）。請注意最小值和最大值，它們決定了每個骰子滾動的值。

counts = [0] * 18 

1.upto(18) do |n| 
    from_i = [1, n - 6 - 6].max # best case is we roll 6 in 2nd and 3rd roll 
    top_i = [6, n - 1 -1].min # at least 1 for 2nd and 3rd roll 
    from_i.upto(top_i) do |i| 
    from_j = [1, n - i - 6].max # again we have the 2nd roll defined, best case for 3rd roll is 6 
    top_j = [6, n - i -1].min # at least 1 for 3rd roll 
    from_j.upto(top_j) do 
     # no need to calculate k since it's already defined being n - first roll - second roll 
     counts[n-1] += 1 
    end 
    end 
end 

print counts 

對於數學方法，看看https://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-t

Answer 4

數學描述僅僅是一個「竅門」，使同樣的計算。它使用多項式表示骰子，1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x表示每個值1-6被計數一次，並且它使用多項式乘法來計算不同的組合。這是因爲某些指數（k）的係數是通過求和P_1和P_2中的所有係數來計算的，其指數總和爲k。

E.g.對於兩個骰子我們有：

(1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x) * (x^6 + x^5 + x^4 + x^3 + x^2 + x) = 
(1*1)*x^12 + (1*1 + 1*1)*x^11 + (1*1 + 1*1 + 1*1)*x^11 + ... + (1*1 + 1*1)*x^3 + (1*1)*x^2 

這種方法的計算與「計數」一樣具有相同的複雜度。

由於函數(x^6 + x^5 + x^4 + x^3 + x^2 + x)^n的表達式更簡單(x(x-1)^6/(x-1))^n，因此可以使用派生方法。 (x(x-1)^6/(x-1))^n是一個多項式，我們正在尋找係數x^s（a_s）。 s'th推導的自由係數（在x^0）爲s! * a_k。因此，s'th中的推導是s! * a_k。

所以，我們得導出這個函數s次。它可以使用派生規則來完成，但是我認爲它會比計數方法更加複雜，因爲每個派生產生「更復雜」的功能。這裏是Wolfram Alpha的前三個派生：first,second和third。

一般來說，我更喜歡數數解，而mellamokb給出了很好的方法和解釋。