格路问题_格路是啥意思

格路问题_格路是啥意思格路问题1.格路问题:从(0,0)点出发只能沿x轴或y轴的正方向每步走一个单位,最终走到(m,n)点,有多少条路径?解法很简单,把寻找路径问题转化为求组合问题,一共要走m+n步,其中往x方向m步

格路问题

1.格路问题:

从(0,0)点出发只能沿x轴或y轴的正方向每步走一个单位,最终走到(m,n)点,有多少条路径?

解法很简单,把寻找路径问题转化为求组合问题,一共要走m+n步,其中往x方向m步,y方向n步。
列成式子为 C m + n n C_{m+n}^{n} Cm+nn
(img-uQAmvmJ5-1588173816642)(_v_images/20200428013841214_2994.png)]

2.不能接触对角线的格路问题

假设m>n,(0,0)到(m,n)点且每个点x都大于y,即不接触对角线的格路数。
1)从(1,0)开始的路径才有可能不接触对角线,此时所有情况为 C ( m − 1 ) + n n C_{(m-1)+n}^n C(m1)+nn,代表往x轴需要走m-1步,y轴n步,如下图1红色路径;
2)从(1,0)开始的路径中所有接触对角线的都能对应一条过对角线的路径,即把第一次接触对角线位置之前的路径关于x=y对称即可,此时过对角线数目为 C m + ( n − 1 ) m C_{m+(n-1)}^m Cm+(n1)m, 如下图2的绿色路径;
3)所以不接触对角线的格路数为 C ( m − 1 ) + n n − C m + ( n − 1 ) m = C m + n − 1 n − C m + n − 1 m C_{(m-1)+n}^n-C_{m+(n-1)}^m=C_{m+n-1}^n-C_{m+n-1}^m C(m1)+nnCm+(n1)m=Cm+n1nCm+n1m
在这里插入图片描述
在这里插入图片描述

3.不能过对角线的格路问题

1)从(0,0)开始到(m,n)可以存在不过对角线的格路,所以起点可以使(0,0),此时总路径数 C m + n n C_{m+n}^n Cm+nn
2)不过但可以接触对角线 l 1 l1 l1问题可以把对角线上移一格子变为 l 2 l2 l2,此时等价于不接触 l 2 : y = x + 1 l2:y=x+1 l2:y=x+1;
(0,0)关于 l 2 l2 l2 的对称点为(-1,1),这个时候从(0,0)开始到(m,n)的所有路径都对应从(-1,1)开始到(m,n)的路径,此时接触 l 2 l2 l2 的路径数为 C ( m + 1 ) + ( n − 1 ) n − 1 C_{(m+1)+(n-1)}^{n-1} C(m+1)+(n1)n1

说明
见下图2里的红色与 l 2 l2 l2 的交点是第一次接触 l 2 l2 l2 的地方,把前面的路径关于 l 2 l2 l2 对称过去是(-1,1)为起点,这个时候在x方向需要走(m+1)步,在y方向走(n-1)步,也就是式子里的下标中-1和+1的意思;
这里起点必须是(-1, 1),不能是新原点(-1,0),因为对称过去的路径和原路径是对应的,长度相等,并且每一条与 l 2 l2 l2 相接触的都唯一对应一条这样的路径,见下图2。【或者直接理解成新原点在(-1,1),(m+1)和(n-1)为新的要走的步数,见下图3里的蓝色坐标系。】

3)所以不经过 l 1 l1 l1的路径数为 C m + n n − C ( m + 1 ) + ( n − 1 ) n − 1 = C m + n n − C m + n n − 1 C_{m+n}^n-C_{(m+1)+(n-1)}^{n-1}=C_{m+n}^n-C_{m+n}^{n-1} Cm+nnC(m+1)+(n1)n1=Cm+nnCm+nn1
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.相关问题

1.数目都为N的1和-1如何排列可以满足到任意位置的和大于0?
等价于M=N的不能过对角线问题,可以接触,因为可以是1、-1、1、-1…1、-1.
2.m>n,只能在x和y轴方向走,从(0,0)到(m,n)的路径个数有几条,必须保证在任何时候x方向走的步数大于y方向走的步数?
等价于不接触对角线的格路问题,如果是x方向可以等于y方向步数就是不过对角线的格路问题。

参考:
知乎:https://zhuanlan.zhihu.com/p/
百度百科:https://baike.baidu.com/item/%E6%A0%BC%E8%B7%AF%E9%97%AE%E9%A2%98/?fr=aladdin

今天的文章
格路问题_格路是啥意思分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/61181.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注