首页 > 代码库 > n个筛子的点数
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; //筛子最大点数为6void Problility(int number){
if(number<1)
return; int maxAllNumbers = 6 * number; int length = maxAllNumbers - number; //数组长度 int *problility = new int[length]; //用来记录筛子和为多少的个数 //初始化每个s的概率都为0 for (int i = number; i < length; i++) problility[i-number] = 0; findProbility(number, problility); //核心函数,用来计算每个sum的个数,number <=sum<=maxAllNumbers //所有组合 int total = pow(g_maxNumber, 6); //下面计算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 = 1; 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 == 1) pProbilities[sum - original]++; //之所以-original是因为数组的第0个元素=number开始的,original 就是筛子的个数number //递归:分成两堆,一堆一个筛子,另一堆剩余的筛子 for (int i = 1; i <=g_maxNumber;i++) findProbility(original, current - 1, sum + i, pProbilities);}
方法2:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。