0

这是一个典型的公平游戏。两名玩家轮流挑选标有从 1 到 n 的棍子，只要 1 号棍子被选中，游戏就结束。规则很简单：玩家A倒数到5并选择对应的棒子；PlayerA数到2并选择对应的棒。该程序试图找到一个初始点，以便最后选择 1 号棒。

我尝试遍历列表并找到哪个初始位置会给出令人满意的结果，但似乎返回值不正确。代码有什么问题？？

fun play(stick) = 
let 
    val stick_list = n_list(stick) 
    (*n_list(8) will generate an int list [1,2,3,4,5,6,7,8]*)

    fun playerA(x::nil, n) = x
      | playerA(stick_list, n) = 
            let 
                val pos = (n + (5 mod size(stick_list))) mod size(stick_list)
            in
                playerB(delete(stick_list, pos), pos)
            end
    and playerB(x::nil, n) = x
      | playerB(stick_list, n) = 
            let 
                val pos = (n + (~2 mod size(stick_list))) mod size(stick_list)
            in
                playerA(delete(stick_list, pos), pos)
            end
    fun search(n) = if playerA(stick_list, n - 1) = 1 then n + 1 else search(n - 1)
in
    search(stick - 1)
end;
4

1 回答 1

0

以下是一些建议：

  • n_list很容易实现为List.tabulate (stick, fn i => i + 1).
  • 使用length而不是size在处理列表时使用。

  • 考虑记住剩余的棒数，因此不需要重新计算长度。例如

    fun play nSticks = 
    let val allSticks = List.tabulate (nSticks, fn i => i + 1)

        fun playerA ([stick], _, n) = stick
          | playerA (sticks, sticksLeft, n) =
            let val pos = (n + (5 mod sticksLeft)) mod sticksLeft
            in
              playerB (delete (sticks, pos), sticksLeft - 1, pos)
            end
        ...

  • 除非这是一个相互递归的练习，否则如果将两个播放器功能合二为一，似乎可以避免大量重复自己，例如通过

    datatype Player = PlayerA | PlayerB
fun player (_, stick::_, 0) = stick
  | player (player, sticks, sticksLeft, pos) = ...
    let val (newPos, otherPlayer) =
            case player of
                PlayerA => ((n + 5) mod sticksLeft, PlayerB)
              | PlayerB => ((sticksLeft + n - 2) mod sticksLeft, PlayerA)
        val newSticks = delete (sticks, pos)
    in player (otherPlayer, newSticks, sticksLeft - 1, newPos) end
于 2015-11-09T17:39:04.833 回答