algorithm - （Hackerrank）（石头游戏）如果条件不明，我怎么能找到答案

Question

https://www.hackerrank.com/challenges/game-of-stones-1/problem

石头游戏。

两名玩家叫牌P1，P2正在玩一个起始数量的棋子的游戏。玩家 1 总是先玩，两个玩家轮流移动。游戏规则如下：

一次移动，玩家可以从棋盘上移走 2、3 或 5 个棋子。如果玩家无法移动，则该玩家输掉游戏。给定棋子的起始数量，找到并打印获胜者的姓名。P1 名为First，P2名为Second。每个玩家都以最佳方式进行游戏，这意味着如果存在获胜的动作，他们将不会做出导致他们输掉游戏的动作。

例如，如果n = 4，P1可以进行以下动作：

P1移除 2 颗石头，留下 2。P2然后移除 2 颗石头并获胜。 P1移除 3 块石头，留下 1。P2不能移动并输掉。 P1将进行第二次比赛并赢得比赛。

功能说明

在下面的编辑器中完成 gameOfStones 功能。它应该返回一个字符串，First 或 Second。

gameOfStones 具有以下参数：

n：一个整数，表示开始的石头数量

输入格式

第一行包含一个整数，即测试用例的数量。接下来的每一行都包含一个整数，即测试用例中的石头数。

约束

1<= n,t <= 100

输出格式

在每个测试用例的新行上，如果第一个玩家是获胜者，则打印 First。否则打印第二个。

我的问题

在此链接中的文档中，玩家每回合可以拿 2、3 或 5 个石头。

但是，如果每种情况下石头的数量和条件的数量不同，我该如何编写代码？

例如。案例1，玩家可以拿2、3或5个石头，案例2，玩家可以拿2、4、7、9个石头。

和代码将通过这两种情况。

输入案例 1：

3  //total conditions of stones can take
2 3 5 //player can take 2, 3 or 5 stones
8 // Number of cases of number of starting stones
1
2
3
4
5
6
7
10

案例二：

4  //total conditions of stones can take
2 3 7 9 //players can take 2, 3,7 or 9 stones
5 // Number of cases of number of starting stones
5
6
7
10
15

代码将通过这两种情况。我应该如何编写满足这种情况的编码？

标签： algorithmgame-theory

Answer 1

我用 Swift 写了你的新问题的解决方案。如果您不熟悉它，希望它与您使用的语言足够相似以便有用。

这是一般情况的解决方案。

// This is an internal function that also takes a dictionary of results so that
// it can remember solutions it has already found
func game(n: Int, conditions: [Int], result: inout [Int : String]) -> String {

    // Have we seen this answer before?  If so, just return it
    if let answer = result[n] {
        return answer
    }

    if n < conditions.min()! {
        // I can't move because the number of stones left is fewer than
        // I'm allowed to take
        result[n] = "Second" // to speed up the solution, remember this result
        return "Second"
    } else if conditions.contains(n) {
        // I can take all of the stones, so I win
        result[n] = "First"  // to speed up the solution, remember this result
        return "First"
    } else {
        // Try taking each of the stones I'm allowed to take, and see
        // if that causes my opponent to lose
        for take in conditions {
            let leave = n - take

            // If the number of stones I leave causes the opponent to lose, I win
            if leave > 0 && game(n: leave, conditions: conditions, result: &result) == "Second" {
                result[n] = "First" // to speed up the solution, remember this result
                return "First"
            }
        }
    }
    
    // No way for me to win, so I come in second.
    result[n] = "Second"  // to speed up the solution, remember this result
    return "Second"
}

// Generate a dictionary to store already generated answers, and call the
// internal recursive routine
func gameOfStones(n: Int, conditions: [Int]) -> String {
    var result = [Int : String]()
    
    return game(n: n, conditions: conditions, result: &result)
}

print(gameOfStones(n: 4, conditions: [2, 3, 5]))   // "First"
print(gameOfStones(n: 6, conditions: [3, 7, 13]))  // "Second"