算法-求n个骰子的点数算法

UI设计界面 UI设计界面 主题:1059 回复:2190

算法-求n个骰子的点数算法

虐人心 发布于 2017-01-25 字数 89 浏览 994 回复 1

把N个骰子扔地上,所有骰子朝上的一面的和为S,输入N,输出S的所有可能的值出现的概率。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(1

归属感 2017-07-18 1 楼

令f(n,s)为骰出n个骰子,和为s的组合数,f(n,s)/pow(6,n) 即为s出现的概率

有f(n,s) = f(n-1,s-1) + f(n-1,s-2) + f(n-1,s-3) + f(n-1,s-4) + f(n-1,s-5) + f(n-1,s-6)

很容易就可以递归求出f(n,s),为避免递归堆栈过深,可自底向上求解

include <iostream>

void calc(int n) {
double cache = new double((n + 1) (n 5 + 1));
memset(cache, 0, (n + 1)
(n 5 + 1) sizeof(double));
cache[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n5; j++)
for (int k = 0; k < 6; k++)
if (j - k >= 0)
cache[i
(n5+1) + j] += cache[(i-1) (n*5+1) + j - k];

double total = 1;
for (int i = 0; i &lt; n; i++) 
    total *= 6;

for (int i = 0; i &lt;= n*5; i++) 
    std::cout &lt;&lt; i + n &lt;&lt; " " &lt;&lt; (cache[n * (n*5+1) + i] / total)  &lt;&lt; std::endl;
delete [] cache;

}

int main() {
calc(10);
return 0;
}