计算结果总和的概率的算法

前端之家收集整理的这篇文章主要介绍了计算结果总和的概率的算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我正在谈论使用的算法将允许您使用x个项目,每个项目的范围为a到b,结果为y.我想有一个算法,当被提供与所描述的值将输出它发生的可能性.

例如,对于两个死亡.因为我已经知道了(因为可能的结果太低).它能够告诉你每个可能性.

设置将是这样的. x = 2 a = 1 b = 6.如果你想知道有机会得到一个2.然后它只是吐出1/36(或它的浮点值).如果你把7作为总和,那就告诉你6.

所以我的问题是,有没有一种简单的方法来实现这样的事情通过已经写的算法.或者,必须通过每个项目的每一次迭代来获得每个值的组合总数.

确切的公式也将给你组合,使每个值从1-12.

所以它会给你一个分布数组,每个索引的每一个组合.如果是0-12.那么0将有0,1将具有0,并且2将具有1.

我觉得这是其他人已经和想要使用的问题的类型,并且已经完成了算法.如果任何人有一个简单的方法来做到这一点,只需循环遍历每一个可能的价值将是真棒.

我不知道为什么我想要解决这个问题,但是由于某种原因,我只是想要解决这个问题.而且由于我一直在谷歌搜索,并且使用wolfram alpha,以及自己尝试.我认为现在是失败并问社区的时候了.

我想要的算法是在c,或者PHP(即使我宁愿不是因为它慢了很多). c的原因只是因为我想要原始速度,我不想要处理类或对象.

代码或C是显示算法的最佳方法.

编辑:

此外,如果我以他的名义冒犯了’b’的人,因为有关数学的事情我很抱歉.既然我不是冒犯,而是想说出我不明白的意思.但答案可以留在那里,因为我确信有人会来这个问题,并且理解背后的数学.

另外我也不能决定我想编码的方式.我想我会尝试使用两者,然后决定哪一个我喜欢更多看到/使用我的小图书馆里面.

我忘了说最后一句话是五年前的演算大概是四次.我对概率,统计学和随机性的理解来自我自己的学习,通过查看代码/阅读维基百科/阅读书.

如果有人好奇,引发了这个问题.我有一本书,我正在放弃阅读叫做醉酒之路,然后一旦我说XKCD 904,我决定现在是时候终于找到阅读它了.然后两个晚上,当我要睡觉的时候,我已经考虑过如何通过一个简单的算法来解决这个问题,并且能够想到一个.

我对代码的编码理解来自于修改其他程序,看到发生了什么,当我打破了一些东西,然后尝试我自己的东西,同时查看文档的功能的构建.通过阅读维基百科(尽可能多的),我明白了大O符号,伪代码是因为它与python类似.我自己,不能写伪代码(或说老师在大学里).我不断收到“像使真正的代码更像伪代码”这样的笔记.那事情没有改变.

编辑2:发现任何搜索这个问题的人都很快就想要代码.我把它放在下面它是根据LGPLv3许可的,因为我确信存在这个代码的封闭源代码.

它应该是相当便携,因为它完全写在c.如果一个人想要用c中的任何一种语言进行扩展,那么这样做是很少的.我选择“标记”第一个链接到“Ask Dr. Math”作为答案,因为它是我用于这个问题的实现.

第一个文件名称是“sum_probability.c”

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

/*!
*    file_name: sum_probability.c
*    
*    Set of functions to calculate the probabilty of n number of items adding up to s
*    with sides x. The question that this program relates to can be found at the url of
*    https://stackoverflow.com/questions/6394120/
*    
*     Copyright 2011,Macarthur Inbody
*    
*   This program is free software: you can redistribute it and/or modify
*   it under the terms of the Lesser GNU General Public License as published by
*   the Free Software Foundation,either version 3 of the License,or
*   (at your option) any later version.
*
*   This program is distributed in the hope that it will be useful,*   but WITHOUT ANY WARRANTY; without even the implied warranty of
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*   GNU General Public License for more details.
*
*   You should have received a copy of the Lesser GNU General Public License
*   along with this program.  If not,see <http://www.gnu.org/licenses/lgpl-3.0.html>.
*     
*   2011-06-20 06:03:57 PM -0400
*    
*   These functions work by any input that is provided. For a function demonstrating it.
*   Please look at the second source file at the post of the question on stack overflow.
*   It also includes an answer for implenting it using recursion if that is your favored
*   way of doing it. I personally do not feel comfortable working with recursion so that is
*   why I went with the implementation that I have included.
*
*/

/*
* The following functions implement falling factorials so that we can
* do binomial coefficients more quickly.
* Via the following formula.
*
*   K
*  PROD    (n-(k-i))/i
*   i=1;
*
*/

//unsigned int return
unsigned int m_product_c( int k,int n){
    int i=1;
    float result=1;
    for(i=1;i<=k;++i){
        result=((n-(k-i))/i)*result;
    }
    return result;
}

//float return
float m_product_cf(float n,float k){
    int i=1;
    float result=1;
    for(i=1;i<=k;++i){
        result=((n-(k-i))/i)*result;
    }
    return result;
}


/*
* The following functions calculates the probability of n items with x sides
* that add up to a value of s. The formula for this is included below.
*
* The formula comes from. http://mathforum.org/library/drmath/view/52207.html
*
*s=sum
*n=number of items
*x=sides
*(s-n)/x
* SUM  (-1)^k * C(n,k) * C(s-x*k-1,n-1)
* k=0
*
*/

float chance_calc_single(float min,float max,float amount,float desired_result){
    float range=(max-min)+1;
    float series=ceil((desired_result-amount)/range);
    float i;
    --amount;
    float chances=0.0;
    for(i=0;i<=series;++i){
        chances=pow((-1),i)*m_product_cf(amount,i)*m_product_cf(desired_result-(range*i)-1,amount)+chances;
    }
    return chances;
}

这里是显示执行的文件,就像我在前一个文件中所说的那样.

#include "sum_probability.c"

/*
* 
* file_name:test.c
*
* Function showing off the algorithms working. User provides input via a cli
* And it will give you the final result.
*
*/
int main(void){
        int amount,min,max,desired_results;
        printf("%s","Please enter the amount of items.\n");
        scanf("%i",&amount);
        printf("%s","Please enter the minimum value allowed.\n");
        scanf("%i",&min);
        printf("%s","Please enter the maximum value allowed.\n");
        scanf("%i",&max);
        printf("%s","Please enter the value you wish to have them add up to. \n");
        scanf("%i",&desired_results);
        printf("The total chances for %i is %f.\n",desired_results,chance_calc_single(min,amount,desired_results));
}

解决方法

首先,您不需要担心从a到b的范围.您可以从y中减去* x,并假定范围从0到b-a. (因为每个项目至少贡献一个总和…所以你可以减去每一个x项目一次).

其次,请注意,您真正想要做的是计算实现特定金额的方法数量.概率只是该计数除以简单指数(b-a 1)^ x.

这个问题在十年前被“数学博士”所涵盖:

http://mathforum.org/library/drmath/view/52207.html

他的配方假设骰子从1到X,所以使用他的答案,你可能想要将你的范围改为a-1(而不是一个)将其转换成这种形式.

他的派生使用生成功能,我觉得应该有一点解释.这个想法是定义多项式f(z),使得z ^ n上的系数是滚动方式n的数量.例如,对于单个6面模具,这是生成函数

z + z^2 + z^3 + z^4 + z^5 + z^6

…因为有一种方法来滚动每个数字从1到6,零的方式滚动任何其他.

现在,如果对于两组骰子有两个生成函数g(z)和h(z),那么这些集合的并集的生成函数只是g和h的乘积. (盯着“乘法两项多项式”操作一段时间才能说服自己这是真的)例如,对于两个骰子,我们可以将上述表达式平方得到:

z^2 + 2z^3 + 3z^4 +4z^5 + 5z^6 + 6z^7 + 5z^8 + 4z^9 + 3z^10 + 2z^11 + z^12

注意我们如何直接读取系数的组合数:1种获得2(1 * z ^ 2)的方法,6种获得7(6 * z ^ 7)的方法等.

表达式的立方体将给予我们三个骰子的生成函数;第四个权力,四个骰子;等等.

当您以封闭的形式,多次编写生成函数,然后再次使用Binomial Theorem扩展它们时,这个表达式的力量就会发生.我推荐Math博士的解释.

原文链接:https://www.f2er.com/c/112809.html

猜你在找的C&C++相关文章