智星论坛(IQSTAR BBS)
 
打印

棋盘(有点难度)!

棋盘(有点难度)!

在平面直角坐标系范围内,用k步由(0,0)点走到(m,n)点,k>=m+n,问有多少种走法?

TOP

按照什么规则走?

TOP

是不是只能上下左右移动?那么结果就是在k-m-n为偶数时才有解:
Sum{k!/[(m+x)!(n+y)!x!y!]; x>=0,y>=0,x+y=(k-m-n)/2}
0.54364331210052407755147385529445

TOP

因为k>=m+n,设k=m+n+2A(A=0,1,2,3,......)
当A=0时很容易,而A>0时就太难了。
好读书不好读书 好读书不好读书

TOP

首先只能判断m+n>0;
其次,需要有走的规则,否则假设m>2,n>2的情况下,可以循环(0,0),(0,1),(1,0),(1,1)四个点N圈,
然后到达(m,n)点,k则为无穷大。
请楼主将题目出的严密一些。
如果定向移动,且步幅为1,则参照3楼duz兄帖子内容。
---Am back. Buddies, how r u doing?---

TOP

m,n皆大于零,k确定的,只能上下左右定向移动,且步幅为1

TOP

请duz兄解释一下式子由来

TOP

每步移动都是上下左右,我们可以分别用字母UDLR来代替,
那么每个合法的移动都将构成一个长度为k的序列(UDLR构成),
这个序列中,U比D多n,R比L多m
如果记UDLR的数目分别为udlr,那么
u=d+n,
r=l+m
u+d+l+r=k
也就是
2(d+l)=k-(m+n)
对于每个满足这个方程的d和l,我们都可以求出对应的u,r
比如
d=0, l=(k-(m+n))/2, u=n, r=(k-(m+n))/2+m
d=1, l=(k-(m+n))/2-1, u=n+1, r=(k-(m+n))/2+m-1
...
而对于每一种知道了u,d,l,r的情况,U,D,L,R序列的数目(它们所在位置可能不同)
是(u+d+l+r)!/(u!d!r!l!)
0.54364331210052407755147385529445

TOP

当前时区 GMT+8, 现在时间是 2008-12-5 23:28

Processed in 0.055104 second(s), 8 queries, Gzip enabled.


Skin By Wing