递归问题：唯一解决方案的情况

Question

出于好奇，我编写了一个程序来计算产生特定得分的Ski Ball角色的不同组合数量。孔有值[0、10、20、30、40、50、100]，这些值被视为枚举值。还有九个球的投掷机会。我将每次投掷处理为递归调用下一次投掷，并在循环遍历每次投掷的值时进行处理：

private static void scoreCalc(int targetScore, int score, int ballNumber)
{
    for(SkiBallHoles hole : SkiBallHoles.values())
    {
        score += hole.getValue();
        ballNumber--;
        if (ballNumber > 0) {
            scoreCalc(targetScore, score, ballNumber);
        }
        if (ballNumber == 0 && score == targetScore) {
            frequency++;
        }
        ballNumber++;
        score -= hole.getValue();
    }
}

这些得分会从主函数中的for循环中被传递到一系列的设置函数中，供该函数使用：

while(score <= 900){
    writer.println(calculateFrequency(score));
    score += 10;
}

private static String calculateFrequency(int targetScore)
{
    frequency = 0;
    scoreCalc(targetScore);
    return targetScore + ": " + frequency;
}

private static void scoreCalc(int targetScore)
{
     scoreCalc(targetScore, 0, BALLCOUNT);
}

---

这种方法的问题在于它没有计算唯一解的数量。例如，0 0 0 0 0 0 0 0 10和10 0 0 0 0 0 0 0 0被算作是不同的组合来产生一个分数，但实际上它们是相同的组合。

我该如何修改我的方法来仅计算唯一解？

谢谢 =)

- jojo008

Answer 1

通过按值对孔进行排序，您可以仅迭代已排序的解决方案（0 0 0 0 0 0 0 0 10，0 0 0 0 0 0 0 10 20等）。

您的解决方案是否遍历相同孔的不同排列？（即对于0 0遍历两次）如果是，则可以将结果除以n！。但是，这种方法会更慢。

- omer681

---

我不知道这是否有帮助，但是这是如何处理洞的值的代码：public enum SkiBallHoles { Hole0 (0), Hole10 (10), Hole20 (20), Hole30 (30), Hole40 (40), Hole50 (50), Hole100 (100); private final int value; SkiBallHoles (int value) { this.value = value; } public int getValue() { return value; } } - jojo008

创建一个值的数组并对其进行排序。向函数添加另一个参数startIndex，并仅从该索引迭代数组。当您递归调用函数时，请使用startIndex = ballNumber调用它。 - omer681

我找到了答案。请看上面。谢谢！ - jojo008

Answer 2

谢谢@omer681，你指引了我正确的方向。

我的修复涉及将枚举类型的Hole值更改为数组中的整数。然后，在递归中，传递了一个'itter'整数，它确定了for循环的起始位置。在递归中，这个数字从for循环继承而来。这样，for循环中的每一步都会限制下面循环的步数。这对于任何数量的球和得分孔都有效。

    private static void scoreCalc(int targetScore, int score, int ballNumber,
    int itter)
{
    for(int i = itter; i < HOLEVALUES.length; i++)
    {
     ...
     if (ballNumber > 0) {
         scoreCalc(targetScore, score, ballNumber, i);
     ...
    }
}

private static void scoreCalc(int targetScore)
{
    scoreCalc(targetScore, 0, BALLCOUNT, 0);
}

- jojo008