freedom501999@gmail.com
(帥氣魔方生)
學校
:
不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 ：
2019-05-30 22:56:25
這題可以使用動態規畫法，方法如下 :
1. 宣告一個存放答案的陣列 PointSum [ 21 ] [ 121 ]，其中 21 代表骰子從 1 到 20 個，121 代表點數和最少是 1 最多是 120
2. 找出骰子與點數和的規律
設一函數 f ( n , sum ) 代表 n 個骰子點數和為 sum 的組合數 ( 即本題所求 )
從機率理論可知，一次丟 n 個骰子，與一個一個丟骰子丟了 n 個，是不會影響結果的
所以這裡我們考慮 n 個骰子，可以先考慮 n-1 個骰子的組合數
n 個骰子點數和 sum = n-1 個骰子的點數和 + 最後一個骰子點數 ( 1~6 其中之一 )
假設最後一個骰子丟到 1 點，那麼 f ( n , sum ) = f ( n - 1 , sum - 1 )
同理，假設丟到 2 點，f ( n , sum ) = f ( n - 1 , sum - 2 )
而因為骰子點數可能為 1 ~ 6，所以 f ( n , sum ) 就等於 n - 1 個骰子點數和為 sum - i 的總和 ( i = 1 ~ 6 )
也就是 f ( n , sum ) = f ( n - 1 , sum - 1 ) + f ( n - 1 , sum - 2 ) + f ( n - 1 , sum - 3 ) + f ( n - 1 , sum - 4 ) + f ( n - 1 , sum - 5 ) + f ( n - 1 , sum - 6 )
規律就是如此
3. 使用迴圈或遞迴，即可輕鬆解題
allllllan123456
(God of Computer Science)
學校
:
國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
這題可以使用動態規畫法，方法如下 :
1. 宣告一個存放答案的陣列 PointSum [ 21 ] [ 121 ]，其中 21 代表骰子從 1 到 20 個，121 代表點數和最少是 1 最多是 120
2. 找出骰子與點數和的規律
設一函數 f ( n , sum ) 代表 n 個骰子點數和為 sum 的組合數 ( 即本題所求 )
從機率理論可知，一次丟 n 個骰子，與一個一個丟骰子丟了 n 個，是不會影響結果的
所以這裡我們考慮 n 個骰子，可以先考慮 n-1 個骰子的組合數
n 個骰子點數和 sum = n-1 個骰子的點數和 + 最後一個骰子點數 ( 1~6 其中之一 )
假設最後一個骰子丟到 1 點，那麼 f ( n , sum ) = f ( n - 1 , sum - 1 )
同理，假設丟到 2 點，f ( n , sum ) = f ( n - 1 , sum - 2 )
而因為骰子點數可能為 1 ~ 6，所以 f ( n , sum ) 就等於 n - 1 個骰子點數和為 sum - i 的總和 ( i = 1 ~ 6 )
也就是 f ( n , sum ) = f ( n - 1 , sum - 1 ) + f ( n - 1 , sum - 2 ) + f ( n - 1 , sum - 3 ) + f ( n - 1 , sum - 4 ) + f ( n - 1 , sum - 5 ) + f ( n - 1 , sum - 6 )
規律就是如此
3. 使用迴圈或遞迴，即可輕鬆解題
Good solution！