n个筛子的点数

题目:把n个筛子扔到地上,所有筛子朝上一面的点数之和为s,输入n,打印出s的所有可能的值出现的概率。

分析:

方法1:递归。

要求概率,那么我们首先只需要求出每个s出现的次数/(6^n)。怎么求s的次数呢?我们不妨把n个筛子分成2堆,一堆一个筛子,另一堆有n-1个筛子,第1堆筛子出现的情况有:1,2,3,4,...6.(所以在代码中用for),另一堆我们也把它分成2堆,一堆有1个筛子(也有1,2,3,4,5,6中情况),另一堆就有n-2个筛子。直到最后只剩下一个筛子,那么就不能分成两堆,也就停止了。这就是迭代的思想。好了,废话不多说,上代码:

int g_maxNumber = ;                                //筛子最大点数为6
void Problility(int number)
{
if(number<1)
return;
int maxAllNumbers = * number;
int length = maxAllNumbers - number; //数组长度
int *problility = new int[length]; //用来记录筛子和为多少的个数
//初始化每个s的概率都为0
for (int i = number; i < length; i++)
problility[i-number] = ;
findProbility(number, problility); //核心函数,用来计算每个sum的个数,number <=sum<=maxAllNumbers
//所有组合
int total = pow(g_maxNumber, );
//下面计算s为number 到maxAllNumbers 之间分别概率多少
for (int i = number; i <= maxAllNumbers; i++)
{
double ratio = (double)problility[i - number] / total;
printf("和为%d的概率为: %s", i, ratio);
}
}
void findProbility(int number,int *probilities) //number :筛子的个数,也代表点数最小的时候,probilities保存每个sum的个数
{
for (int i = ; i <= g_maxNumber; i++)
findProbility(number, number, i, probilities);
}
/* original 就是筛子的个数,current是当前筛子个数,每次递归current就会-1,sum将
每个筛子的点数累积加起来,pProbilities就是一个数组,记录筛子和为sum的概率 */
void findProbility(int original, int current, int sum, int *pProbilities)
{
//出口
if (current == )
pProbilities[sum - original]++; //之所以-original是因为数组的第0个元素=number开始的,original 就是筛子的个数number //递归:分成两堆,一堆一个筛子,另一堆剩余的筛子
for (int i = ; i <=g_maxNumber;i++)
findProbility(original, current - , sum + i, pProbilities);
}

方法2:

上一篇:剑指Offer 63 股票的最大利润


下一篇:Vue08: 计算属性computed