java - 用于计算飞镖可能完成情况的递归函数

Question

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

如果你不知道Darts x01游戏的Double Out结束规则，很难理解这个问题......让我尝试解释一下。为简单起见，我暂时将靶心排除在等式之外。

规则:

1) 您有三支飞镖，可以 throw 到 1 号到 20 号的位置

2) 单次击中可以获得单分、双分或三分

例如你可以点击: 单次20=20分或 双 20 = 40 点或 三倍 20 = 60 分

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

4)通常情况下，您从 501 开始， throw 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 将被忽略，并且在修改其他 dart 值之前，一个 dart 会完全递增。

相反，它可以递归地解决，如下所示。 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