考虑笛卡尔坐标系中的一个点 P(n,n)。机器人必须从原点开始并到达这一点。机器人可以采取的唯一步骤是：
- 1个单位权利
- 1个单位。
机器人到 P 点可以走多少条不同的路径？
是否有到达 P 点的最优路径？（向上和向右的步骤都会产生相同的成本）。
1111 次
3 回答
5
路径总数为
(2n choose n)
因为您必须采取n正确的步骤和n向上的步骤才能在该点结束(n,n)，但是您进行步骤的顺序无关紧要。
所以有2n总的步骤，其中n是正确的并且n是向上的。以方式选择正确步骤的位置，(2n choose n)其余步骤必须是向上步骤。
没有路径比其他路径更好，因为所有路径都使用相同数量的向上和右侧步骤（两者n）。
于 2011-07-16T05:21:47.267 回答
4
滚动查看此 Wikipedia 文章（加泰罗尼亚语编号），直至看到下图。答案就在那里。
因此，路径的总数是
注意：此论坛仅适用于单调路径，不跨越对角线。如果你想允许穿过对角线，它需要稍微改变。为此使用递归:)
希望它有用。
于 2011-07-16T04:54:33.853 回答
2
它必须是 (2n!)/(n!*n!) 。
解释 ：
您必须从 origin(0,0) 到达 (n,n) 假设 v 是垂直向上的 1 个单位，h 是水平向右的 1 个单位。所有的路径看起来像这样 - {vvvhhhvhhhvh.... , vvhhvvhhhvvv...,........)v 和 h 分布在 v 的数量 + h 的数量的长度上，这必须是
n + n = 2n。
现在路径总数将是 2n 个地方的 vs 和 hs 的组合 那将等于
(n+n)!/(n!*n!)
因为 v 和 h 是重复的。如果有像 a 或 b 这样的其他单位，它也会被考虑在内。我认为这不会是一个加泰罗尼亚数字。Rgds，软软的
于 2012-06-26T06:35:34.783 回答