一种计算结果发生概率的算法

Question

我正在谈论的算法将允许你用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'的人,我很抱歉.因为我不是故意冒犯,但我想说的是我不理解它.但答案可能会留在那里因为我确信有人可能会提出这个问题并理解其背后的数学.

此外,我无法决定我想用哪种方式编写代码.我想我会尝试使用两者,然后决定哪一个我更喜欢在我的小图书馆里查看/使用.

我忘了说的最后一件事是,微积分在五年前大约有四个.我对概率,统计和随机性的理解来自于我自己的学习,通过查看代码/阅读维基百科/阅读书籍.

如果有人好奇是什么引发了这个问题.我有一本书,我推迟阅读的名为The Drunkards Walk,然后一旦我说XKCD 904,我决定是时候终于开始读它了.两天前,当我要睡觉的时候...我曾经思索过如何通过一个简单的算法解决这个问题,并且能够想到一个.

我对代码的编码理解来自于修改其他程序,看到当我破坏某些东西时发生的事情,然后在查看功能构建的文档时尝试自己的事情.我从阅读维基百科(尽可能多的人)中了解大O符号,伪代码是因为它与python非常相似.我自己,不能写伪代码(或说大学里的老师).我不断得到像"让它不像真正的代码使它更像伪代码"的笔记.那件事没有改变.

编辑2:任何搜索此问题的人都很快就想要代码.我把它包括在下面.它是在LGPLv3下许可的,因为我确信这个代码存在闭源等价物.

它应该是相当便携的,因为它完全用c语言编写.如果有人想要用c语言编写的各种语言中的扩展名,那么这样做应该花费很少的精力.我选择"标记"第一个与"Ask 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
*    http://stackoverflow.com/questions/6394120/
*    
*     Copyright 2011-2019, 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, max, amount, desired_results));
}

Answer 1

首先,你不必担心范围是a到b.你可以只减去a*x从y假装范围从去0到b-a.(因为每件物品至少有助于a总和......所以你可以a为每x件物品减去一次.)

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

大约十年前,"问问数学博士"报道了这个问题:

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

他的表述是假设骰子从1到X编号,所以要使用他的答案,你可能想要改变你的范围a-1(而不是a)将它转换成那种形式.

他的推导使用了生成函数,我觉得值得一点解释.这个想法是定义一个多项式f(z),使得系数 on 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)等.

表达式的立方体将为我们提供三个骰子的生成函数; 第四种力量,四个骰子; 等等.

当您以封闭形式编写生成函数,乘以,然后使用二项式定理再次展开它们时,此公式的功能就出现了.我按照Math博士对细节的解释.