一个n*n矩阵从左上角到右下角有几种走法?如何计算?
我想知道不允许斜走和允许斜走这两种情况下的走法数量和计算过程
0000
0000
0000
0000
比如这个矩阵如何计算从左上角元素到右下角元素总共有几种走法?(分别给出包括斜走和不包括斜走的走法数量以及计算过程,一个文盲的纯好奇,不是考试题,求解答)
如果是可以上下左右走, 那么走法数量有无穷多个.
如果只能向下或向右走:
假设, 我们算出走到红格有12种走法, 蓝格有15种走法.
那么绿格有几种走法? 当然是:
(红格的12种走法再走下去) + (蓝格的15种走法再右走) = 27种
如此, 我们可以从左上慢慢往右下算, 得到..
那么, 从左上到右下, 共20种走法.
如果可以走右, 下, 右下 3个方向, 方法也是一样, 只要把某个格的左, 上, 左上的走法数量算出, 并加在一起就是次格的走法数量.
那么, 从左上到右下, 共63种走法.
追问原来如此,非常感谢.
您的图是用什么软件做的?很形象
2013年1月21日21:29:43补充:
如果考虑下左右都可以走的话情况又会怎么样?如何计算?感觉您说的方法可能无法对这个进行套用,因为下左右是允许蛇形向右下角前进的,这样有些格子会有未知数量.
我用excel做的, 再贴进小画家, 图片存档.
别小看这些软件, 他们功能很强大的.
你的规则是可以右, 下, 下左, 下右吧,
依样画葫芦, 每个格只要把左, 上, 上右, 上左的数字加起来, 不会有未知数, 关键是填入的顺序, 由上往下填就不会有未知数.
这里我就不用图片了
1 1 1 1
2 5 8 10
7 22 45 63
29 103 233 341
共341种走法
温馨提示：答案为网友推荐，仅供参考
第1个回答 2013-01-21
如果只能向右或向下, 那么一共要走2(n-1)步, 其中n-1步向右, n-1步向下.
走法总数就是从2(n-1)中取n-1的组合数C(2(n-1),n-1).
如果还可以向右下走. 设有k步向右下走, 则总共要走2(n-1)-k步.
其中n-k-1步向右, n-k-1步向下, k步向右下, 有C(2(n-1)-k,k)·C(2(n-k-1),n-k-1)种走法.
走法总数对k从0到n求和, 为∑{0 ≤ k ≤ n} C(2(n-1)-k,k)·C(2(n-k-1),n-k-1).
结果不确定能否化简.
走法总数就是从2(n-1)中取n-1的组合数C(2(n-1),n-1).
如果还可以向右下走. 设有k步向右下走, 则总共要走2(n-1)-k步.
其中n-k-1步向右, n-k-1步向下, k步向右下, 有C(2(n-1)-k,k)·C(2(n-k-1),n-k-1)种走法.
走法总数对k从0到n求和, 为∑{0 ≤ k ≤ n} C(2(n-1)-k,k)·C(2(n-k-1),n-k-1).
结果不确定能否化简.
第2个回答 2013-01-21
