我正在讨论的算法将允许你用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‘的人,我很抱歉。因为我不是有意冒犯,但我只想声明,I不理解它。但答案可能会留在那里,因为我相信有人可能会来回答这个问题,并理解它背后的数学原理。
我也不能决定我想用哪种方式来编码。我想我会尝试使用这两个,然后决定我更喜欢在我的小库中看到/使用哪一个。
我忘了说的最后一件事是,微积分大约是五年前的四次。我对概率、统计和随机性的理解来自于我自己通过查看代码/阅读维基百科/阅读书籍的学习。
如果有人想知道是什么引发了这个问题。我有一本延迟阅读的书,叫做“酒鬼漫步”,然后当我说到XKCD904时,我决定终于可以开始读它了。两天前的晚上,当我要睡觉的时候。我曾考虑过如何通过一个简单的算法来解决这个问题,并能够想到一个。
我对代码的编码理解来自于对其他程序的修补,看到当我破坏某些东西时会发生什么,然后在查看内置函数的文档时尝试我自己的东西。通过阅读维基百科,我确实理解了大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
* 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));
}
发布于 2011-06-18 14:02:38
首先,您不需要担心从a
到b
的范围。你可以从y
中减去a*x
,然后假设范围是从0
到b-a
。(因为每一项至少对总和贡献了a
...因此,您可以为每个x
项减去一次a
。)
其次,请注意,您真正想要做的是计算获得特定金额的方法的数量。概率就是计数除以简单指数(b-a+1)^x
。
这个问题在大约十年前的“问数学博士”中就有报道了:
http://mathforum.org/library/drmath/view/52207.html
他的公式假设骰子的编号是从1到X,所以要使用他的答案,您可能希望将范围按a-1
(而不是a
)移动,以将其转换为这种形式。
他的推导使用了生成函数,我觉得应该稍微解释一下。其思想是定义一个多项式f(z)
,使得z^n
上的系数是滚动n
的路数。例如,对于单个六面冲模,这是生成函数:
z + z^2 + z^3 + z^4 + z^5 + z^6
...because有一种方法可以将每个数字从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博士的解释。
发布于 2011-06-18 14:13:33
假设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和b-a之间。
因此,编写代码来查找f(0, m, n, x)
就足够了。
现在请注意,实现目标的所有方法,比如最后一个数字是c是:
f(0, m, n-1, x-c)
实际上,我们还剩下n-1个数字,并且希望总和是x-c。然后我们有一个递归公式:
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,以获得最终的概率。
发布于 2011-06-18 13:51:38
要获得所有的可能性,您可以制作一个值的映射:
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。
该模式适用于n x n网格,将有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
https://stackoverflow.com/questions/6394120
复制相似问题