java - 计算飞镖可能完成的递归函数

Question

我正在尝试用 Java 编写一个递归函数，以确定如何完成飞镖游戏。基本上，您最多有 3 个飞镖，然后您必须以双飞镖结束。

如果不知道Double Out finishing的Darts x01游戏的规则，很难理解这道题...让我试着解释一下。为简单起见，我暂时将牛眼排除在等式之外。

规则:

1) 你有 3 支飞镖，可以从 1 到 20 throw

2) 单击可以有单分、双分或三分

例如你可以打:单人 20 = 20 分或双 20 = 40 点或三重 20 = 60 分

3) 在一个回合中，您最多可以获得 180 分(3x 三重 20 = 3*60 = 180)。任何高于 180 的东西都是不可能的。这并不意味着低于 180 是可能的。例如 179，也是不可能的，因为下一个最好的分数是 triple20+triple20+triple19 = 167

4) 通常，你从 501 开始，投 3 次飞镖，直到你正好剩下 0 分。

5) 现在，在 Double Out 中，要求最后一个飞镖命中一个 Double

例如如果您还剩 180 分，则无法完成，因为您的最后一镖必须是双镖。所以最大值(忽略靶心)= triple20 + triple20 + double20 = 160如果你的分数是 16，你可以简单地通过击中双 8 来完成使用 1 镖。再比如，如果你的分数是61，你可以打triple17 + double5 (= 51 + 10)

当前代码

无论如何，下面是我目前所拥有的。我知道这远非我所需要的，但无论我尝试什么，我总是被卡住。也许有人可以分享他对另一种方法的想法

private class Score{
    int number;    // the actual number, can be 1...20
    int amount;    // multiplier, can be 1, 2 or 3
    public Score(int number, int amount){
        this.number = number;    // the actual number, can be 1...20
        this.amount = amount;    // multiplier, can be 1, 2 or 3
    }
    public int value()
    {
        return number * amount;   // the actual score
    }

    public void increment()
    {
        if(this.amount == 0)
            this.amount = 1;

        this.number++;
        if(this.number >= 20)
        {
            this.number = 0;
            this.amount++;

            if(this.amount >= 3)
                 this.amount = 3;
        }
    }
}

public ArrayList<Score> canFinish(int desired, ArrayList<Score> score){

        // If this is the case -> we have bingo
        if(eval(score) == desired) return score;

        // this is impossible -> return null
        if(eval(score) > 170) return null;

        // I can't figure out this part!!
        Score dart3 = score.remove(2);
        Score dart2 = score.remove(1);

        if(dart2.eval() < 60){
            dart2.increment();
        }
        else if(dart3.eval() < 60){
            dart3.increment();
        }

        score.add(dart2);
        score.add(dart3);

        return canFinish(desired, score);
}

public int eval(ArrayList<Score> scores)
{
    int total = 0;
    for(Score score : scores){
        total += score.value();
    }
    return total;
}

我只想调用:

ArrayList<Score> dartsNeeded = new ArrayList<Score>();
dartsNeeded.add(new Score(16, 2));   // Add my favourite double
dartsNeeded.add(new Score(0, 0));
dartsNeeded.add(new Score(0, 0));

// and call the function
dartsNeeded = canFinish(66, dartsNeeded);

// In this example the returned values would be:
// [[16,2],[17,2],[0,0]] -> 2*16 + 2*17 + 0*0 = 66
// So I can finish, by throwing Double 17 + Double 16

因此，如果无法完成，该函数将返回 null，但如果有任何可能的完成，我会收到带有 3 个飞镖的 ArrayList，我需要获得我想要的分数...

简短摘要

问题是上面的代码只能帮助找到 1 个飞镖，但不能找到两个飞镖的组合。所以 canFinish(66, darts) 有效 -> 但 canFinish(120, darts) 给出了 StackOverflow 异常。对于 120，我希望得到诸如 triple20、double14、double16 或任何其他有效组合之类的东西。

Answer 1

如果记录 canFinish 尝试的分数，您可以看到错过了很多可能性。值 20 将被忽略，一个省在修改其他省值之前完全递增。

相反，它可以递归地解决，如下所示。 canFinish(desired, score) 返回可以添加到 score 中的飞镖的任意组合，以给出 desired 的总数。用您知道的飞镖列表或任何空列表来调用它以查找任何可能性。

canFinish(desired, score)
    if darts sum to desired, return desired
    if there are fewer than 3 darts in score
        for each possible value of a dart (if it's the last dart, check for a double)
            add dart to score
            if canFinish(desired, score) != null
                return canFinish(desired, score)
            end
            remove dart from score
        end
    end
    return null
end