排序专题-走路问题

问题引入

如图所示某个城市有7条南北走向的街道，5条东西走向的街道。则从A点走到B点最短的走法有______种方法．

77c6a7efce1b9d16c058e1e3f0deb48f8d546490.jpg

问题解答

已经最佳的路线是要走7步向东和5步向北，问题就变成了在12步中如何分配这7步向东和5步向北。我们先在12步中分配7步向东，再在剩下的5步中分配5步向北。那么路径加起来一共就是。也是可以的。

例子

（16全国高考）小明从街道的E处出发，先到F处与小红会合，再一起到位于G处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为多少？

zyb_ff72efdba317cbf4ceecbf6702262792.jpg

解答：先考虑E-F的路径，思考的方式和上一个问题一样，E到F最少需要走4步，其中2步向东，2步向北：。F-G的路径最少要走3步，其中2步向东，1步向北：。E-F-G的路线是一个问题的分步，所以最后的答案是*。

例子

有15根火柴，如果规定每次取2根或3根，那么取完这堆火柴共有 ___ 种不同取法．

解答：先分类，把这个问题分为3类情况。取掉这些火柴一共有3重方法，分别是每次取2根取6次，每次取3根取1次。或者，每次取2根取3次，每次取3根取3次。或者，每次都取3根取5次。

每类情况都有哪些步骤呢？如果是第一类情况，一共有=7。第二类情况，一共有=20。第三类情况，=1。加起来一共28种取法。