5条东西向马路和7条南北向马路组成,现在要从西南角的处沿最短的路线走到东北角出,由于修路,十字路口不能通过,那么共有____种不同走法.本题是最短路线问题.要找出共有多少种不同走法,关键是保证不重也不漏,一般采用标数法.如上图所示,共有120种.另解:本题也可采用排除法.由于不能经过,可以先计算出从到的最短路线有多少条,再去掉其中那些经过的路线数,即得到所求的结果.对于从到的每一条最短路线,需要向右6次,向上4次,共有10次向右或向上;而对于每一条最短路线,如果确定了其中的某6次是向右的,那么剩下的4次只能是向上的,从而该路线也就确定了.这就说明从到的最短路线的条数等于从10次向右或向上里面选择6次向右的种数,为.一般地,对于的方格网,相对的两个顶点之间的最短路线有种.本题中,从到的最短路线共有种;从到的最短路线共有种,从到的最短路线共有种,根据乘法原理,从到且必须经过的最短路线有种,所以,从到且不经过的最短路线有种.(难度等级※※※)如图所示,从A点到B点,如果要求经过C点或D点的最近路线有多少条?1、方格图里两点的最短路径,从位置低的点向位置高的点出发的话,每到一点(如C、D点)只能向前或者向上.2、题问的是经过C点,或者D点;那么A到B点就可以分成两条路径了A--C---B;A---D---B,那么也就可以分成两类.但是需要考虑一个问题——A到B点的最短路径会同时经过C和D点吗?最短路径只能往上往前,经过观察发现C、D不会同时出现在最短路径上了.3、A---C---B,那么C就是必经之点了,就需要用到乘法原理了.A---C,最短路径用标数法标出,同样C---B点用标数法标注,然后相乘A---D---B,同样道理.最后结果是735+420=1155条.如图为一幅街道图,从出发经过十字路口,但不经过走到的不同的最短路线有条.到各点的走法数如图所示.图1 图2所以最短路径有
全文预览
