-1

我不知道如何开始。

让我们想象一个 5x5 的正方形。

机器人从左上角开始，然后在右下角开始。

我们想让一个机器人从左上角的开始方块到右下角的结束方块。

在每个方格，机器人只有两个动作之一：

它可能向右走一格，也可能向下一格。

编写一个程序来确定有多少种方法可以做到这一点？换句话说，从“开始”到“结束”有多少条路径，每一步的移动都像上面那样受到限制？

4

1 回答 1

0

这由递归树遍历表示。您可以编写一个递归方法来执行此操作，例如：

traverse_moves，获取棋盘状态（在本例中为机器人所在的位置）并返回一个整数

计算你可以采取的下一步行动 - 从 0 到 2 总数。如果为 0，则返回整数1。如果为 1 或 2，则为每个有效移动创建棋盘状态并使用您创建的状态调用此方法，将所有调用的返回值相加并返回您得到的总和。

例如，对于 2x2 板，创建机器人位于左上角的状态。这个状态有两种可能的移动，所以它会用机器人左下角和机器人右上角来调用自己。这些状态中的每一个都有一个可能的移动，并且会用右下角的机器人来称呼自己。遍历树的这两个“叶子”都将返回 1，这些 1 将被返回并传播并总结递归，从而为您提供 2 作为正确答案。

Caller
  | 2
  TL calls itself with BL and TR
/ 1 \ 1
BL  TR call themselves with BR, their only valid move
| 1  | 1
BR   BR return 1s each for being leaf nodes, the 1s are returned and summed

编辑：伪代码

int traverseMoves(BoardState state)
{

    List<BoardState> nextMoves = possibleMovesFrom(state);
    if (nextMoves.Length == 0)
    {
        return 1;
    }

    int returnValue = 0;
    foreach (BoardState move in nextMoves)
    {
        returnValue += traverseMoves(move);
    }
    return returnValue;
}
于 2013-04-17T00:59:49.170 回答