-4

我正在做 C++，我想找到最简单的方法来找到给定添加数量的给定答案的总概率。

例如，给定的答案是 5，给定的加法数是 4 (x+x+x+x)。我想找到的总概率是 4：

1) 1 + 1 + 1 + 2 = 5
2) 1 + 1 + 2 + 1 = 5
3) 1 + 2 + 1 + 1 = 5
4) 2 + 1 + 1 + 1 = 5

另一个例子，给定的答案是 6，给定的加法数是 4 (x+x+x+x)。总概率为 10：

1) 1 + 1 + 1 + 3 = 6
2) 1 + 1 + 3 + 1 = 6
3) 1 + 3 + 1 + 1 = 6
4) 3 + 1 + 1 + 1 = 6
5) 1 + 1 + 2 + 2 = 6
6) 1 + 2 + 2 + 1 = 6
7) 2 + 2 + 1 + 1 = 6
8) 2 + 1 + 1 + 2 = 6
9) 2 + 1 + 2 + 1 = 6
10) 1 + 2 + 1 + 2 = 6

我完全不知道从哪里开始

4

3 回答 3

4

这是你的一个开始。

看看这张表

        1   2   3   4   5
      +------------------
1     | 1   0   0   0   0
2     | 1   1   0   0   0
3     | 1   2   1   0   0
4     | 1   3   3   1   0
5     | 1   4   6   4   1

被加数的个数从左到右递增，总行数递增，例如有 3 种方式将 3 个整数（大于 0）相加，总共 4 个（即 1+1+2、1+2+1 , 2+1+1)。

于 2013-07-26T08:48:52.587 回答
0

这不是您要查找的概率number of comibnations，而是.

查看您的示例，我假设您添加的数字数量是固定的（即 4），因此每个数字都大于或等于 1。我们可以在这里做简单的数学运算——让我们从等式两边减去这个数字：

原文：1)1 + 1 + 1 + 2 = 5 减法结果：1)0 + 0 + 0 + 1 = 1

减法完成后，您的问题是与重复问题的组合。

您可以在我提供的链接中找到的公式非常简单。该问题可以使用以下代码解决：

#include <iostream>

unsigned factorial(int n)
{
    if (n == 1) return 1;
    return n * factorial(n-1);
}

unsigned combinationsWithRepetition(int n, int k)
{
    return factorial(n + k - 1) / (factorial(k) * factorial(n - 1));
}

unsigned yourProblem(unsigned numberOfNumbers, unsigned result)
{
    return combinationsWithRepetition(numberOfNumbers, result - numberOfNumbers);
}

int main()
{
    std::cout << yourProblem(4, 5) << std::endl;
    std::cout << yourProblem(4, 6) << std::endl;
    return 0;
}

此外，您可以在在线编译器中查看此代码。

请注意，此代码仅涵盖解决问题的方法，如果您选择使用它，可以对其进行改进（即它不受无效值的保护）。

于 2013-07-26T09:22:19.700 回答
0

通过 4 个加法和一个结果 Y，如果所有数字都是正数且非零且足够小（<100），那么您至少可以轻松地强制执行此操作...只需以 4x 循环遍历所有数字，如果它们总和为 Y 增量排列的数量。缺点是复杂度 O(N^4) 会很慢。

#include <iostream>
using namespace std;

int main()
{
    int y = 6;
    int perm = 0;

    for(int a = 1; a < y; a++)
    for(int b = 1; b < y; b++)
    for(int c = 1; c < y; c++)
    for(int d = 1; d < y; d++)
    {
        if((a+b+c+d)==y)
        {
            cout << a << " + " << b << " + " << c << " + " << d << " = " << y  << endl;
            perm++;
        }
    }
    cout << "number of permutations: " << perm << endl;
}
于 2013-07-26T08:58:48.207 回答