c++ - 以递归方式检查每个橄榄球比分，不重复

Question

为了好玩，我创建了一个算法，根据给定的橄榄球得分(3、5 或 7 分)计算所有可能的组合。我找到了两种方法:第一种是蛮力，3个叠层for循环。另一种是递归。

问题是某些组合会出现多次。我怎样才能避免这种情况？

我的代码:

#include <iostream>
using namespace std;
void computeScore( int score, int nbTryC, int nbTryNC, int nbPenalties );

int main()
{
    int score = 0;
    while (true)
    {
        cout << "Enter score : ";
        cin >> score;
        cout << "---------------" << endl << "SCORE = " << score << endl
                << "---------------" << endl;

        // Recursive call
        computeScore(score, 0, 0, 0);
    }
    return 0;
}

void computeScore( int score, int nbTryC, int nbTryNC, int nbPenalties )
{
    const int tryC = 7;
    const int tryNC = 5;
    const int penalty = 3;

    if (score == 0)
    {
        cout << "* Tries: " << nbTryC << " | Tries NT: " << nbTryNC
                << " | Penal/Drops: " << nbPenalties << endl;
        cout << "---------------" << endl;
    }
    else if (score < penalty)
    {
        // Invalid combination
    }
    else
    {
        computeScore(score - tryC, nbTryC+1, nbTryNC, nbPenalties);
        computeScore(score - tryNC, nbTryC, nbTryNC+1, nbPenalties);
        computeScore(score - penalty, nbTryC, nbTryNC, nbPenalties+1);
    }
}

Answer 1

考虑这一点的一种方法是认识到，只要您有总和，就可以通过对所有值进行排序将其放入某种“规范”形式。例如，给定

20 = 5 + 7 + 3 + 5

你也可以这样写

20 = 7 + 5 + 5 + 3

这为如何解决您的问题提供了几个不同的选项。首先，你总是可以排序并记录你所做的所有总和，永远不会输出相同的总和两次。这样做的问题是，您最终会在多次不同的时间重复生成相同的总和，这是非常低效的。

另一种(更好的)方法是更新递归以稍微不同的方式工作。现在，您的递归通过在每一步始终添加 3、5 和 7 来工作。这就是让一切乱七八糟的原因。另一种方法是考虑添加您要添加​​的所有 7，然后是所有 5，然后是所有 3。换句话说，你的递归会像这样工作:

 Let kValues = {7, 5, 3}

 function RecursivelyMakeTarget(target, values, index) {
      // Here, target is the target to make, values are the number of 7's,
      // 5's, and 3's you've used, and index is the index of the number you're
      // allowed to add.

      // Base case: If we overshot the target, we're done.
      if (target < 0) return;

      // Base case: If we've used each number but didn't make it, we're done.
      if (index == length(kValues)) return;

      // Base case: If we made the target, we're done.
      if (target == 0) print values; return;

      // Otherwise, we have two options:
      // 1. Add the current number into the target.
      // 2. Say that we're done using the current number.

      // Case one
      values[index]++;
      RecursivelyMakeTarget(target - kValues[index], values, index);
      values[index]--;

      // Case two
      RecursivelyMakeTarget(target, values, index + 1);
 }

 function MakeTarget(target) {
      RecursivelyMakeTarget(target, [0, 0, 0], 0);
 }

这里的想法是在添加任何 5 之前添加所有要使用的 7，并在添加任何 3 之前添加任何 5。如果您查看以这种方式制作的递归树的形状，您会发现没有两条路径最终会尝试相同的总和，因为当路径分支时，要么添加了不同的数字，要么递归选择开始使用系列中的下一个数字。因此，每个总和只生成一次，不会重复使用。

此外，上述方法可以扩展到可以添加任意数量的可能值，因此如果橄榄球引入了一个新的值(value) 15 分的 SUPER GOAL，您可以只更新 kValues 数组，一切都会练习就好了。

希望这对您有所帮助!