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

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 语言编写的任何一种语言的扩展，那么应该花费很少的精力来做到这一点。我选择“标记”第一个链接到“询问数学博士”的答案作为答案，因为它是我用于此问题的实现。

第一个文件的名称是“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 的范围。您只需从 y 中减去 a*x 即可，并假设范围从 0 到 ba。 （因为每个项目至少对总和贡献 a...因此您可以为每个 x 项目减去该 a 一次。 ）

其次，请注意，您真正想要做的是计算获得特定总和的方法的数量。概率就是该计数除以简单指数 (b-a+1)^x。

大约十年前，“问数学博士”就涵盖了这个问题：

链接

他的公式是假设骰子编号从 1 到 X，因此要使用他的答案，您可能想要改变您的range 通过 a-1 （而不是 a）将其转换为该形式。

他的推导使用了生成函数，我认为值得对此进行一些解释。这个想法是定义一个多项式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

注意我们如何直接读取组合的数量 ：获得 2 的 1 种方法 (1*z^2)、获得 7 的 6 种方法 (6*z^7) 等。

系数 该表达式将为我们提供生成三个骰子的函数；第四次方，四个骰子；等等。

当您以闭合形式编写生成函数、相乘，然后使用 二项式定理。细节我听从 Math 博士的解释。

Answer 2

假设 f(a, b, n, x) 表示可以在 a 和 b 之间选择 n 个数字的方法数，总和为 x。

然后注意：

f(a, b, n, x) = f(0, b-a, n, x-n*a)

确实，只要用一种方法求出 x 的和，然后将 n 个数字中的每一个减去 a，那么总和将变为 x - n*a 并且每个数字都将是0 到 ba 之间。

因此，编写代码来查找 f(0, m, n, x) 就足够了。

现在请注意，实现目标的所有方法（使最后一个数字为 c）是：

f(0, m, n-1, x-c)

事实上，我们还剩下 n-1 个数字，并且希望总和为 xc。
然后我们有一个递归公式：

f(0,m,n,x) = f(0,m,n-1,x) + f(0,m,n-1,x-1) + ... + f(0,m,n-1,x-m)

其中右侧的被加数对应于最后一个数字等于 0, 1, ..., m

现在您可以使用递归来实现该公式，但这会太慢。

然而，有一个叫做记忆递归的技巧，即保存函数的结果，这样就不必再次计算它（对于相同的参数）。

记忆递归的复杂度为 O(m * n)，因为这是您需要计算和保存的不同输入参数的数量。

计算出计数后，您需要除以可能性总数，即 (m+1)*n 以获得最终概率。

Answer 3

数论、统计学和组合学让你相信，要得出事件概率的数值——你必须知道两件事：

• 可能结果的数量，
• 总结果集中 有多少等于结果。 y' 是您要寻找的概率值。

用伪代码：

numPossibleOutcomes = calcNumOutcomes(x, a, b);
numSpecificOutcomes = calcSpecificOutcome(y);
probabilityOfOutcome = numSpecificOutcomes / numPossibleOutcomes;

然后只需编写上面的两个函数，这应该很容易。

Answer 4

为了获得所有可能性，您可以制作值映射：

for (i=a to b) {
 for (j=a to b) {
  map.put(i+j, 1+map.get(i+j))
 }
}

为了更有效地计算总和，您可以使用以下模式
6 个 7、5 个 6、4 个 5、3 个 4、2 个 3、1 个 2。

该模式适用于 nxn 网格，将有 n (n+1) 个，总和大于或小于 1 的可能性较小。

这将计算可能性，例如，Count(6, 1/2/3/4/5/6) 将给出骰子总和的可能性。

import math
def Count(poss,sumto):
  return poss - math.fabs(sumto-(poss+1));

编辑：在 C 中，这将是：

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

int count(int poss, int sumto)
{
  return poss - abs(sumto-(poss+1));
}

int main(int argc, char** argv) {
    printf("With two dice,\n");
    int i;
    for (i=1; i<= 13; i++)
    {
        printf("%d ways to sum to %d\n",count(6,i),i);
    }
    return (EXIT_SUCCESS);
}

给出：

With two dice,
0 ways to sum to 1
1 ways to sum to 2
2 ways to sum to 3
3 ways to sum to 4
4 ways to sum to 5
5 ways to sum to 6
6 ways to sum to 7
5 ways to sum to 8
4 ways to sum to 9
3 ways to sum to 10
2 ways to sum to 11
1 ways to sum to 12
0 ways to sum to 13