NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 22 题

（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有 $7$ 条南北向的纵街，$5$ 条东西向的横街。现要从西南角的 A 走到东北角的 B ，最短的走法共有多少种？___________ 

这道题考的是组合数学里的网格最短路径计数。拿到题别急着套公式，先数清‘段数’：7条纵街夹出6段南北路，5条横街夹出4段东西路，一共要走10步（6右4下），再从10步里选4步向下（或6步向右）用组合数算即可。

最容易掉进的坑是直接把‘7条纵街’当成要走7步，其实7条线之间只有6个间隔，同理5条横街对应4段路。还有人会混淆选哪一项：总步数10里选4步向下是对的，但有人会误算成C(10,5)=252，那是把横街数直接当步数了。另外计算组合数时别把阶乘约分搞错，C(10,4)=210是标准结果，记住选较小的k计算更简便。

考点与概念\n\n这道题考查的是组合数学中的网格最短路径计数。核心概念很简单：在一个矩形网格中，从左下角走到右上角，如果只允许向右或向上走，那么最短路径的步数是固定的——必须走完所有的横向段和纵向段，不能绕路。方案数就是在这固定的总步数里，选择哪几步是横向（或纵向）的走法数量，用组合数$C(n,k)$表示。\n\n## 命题视角\n\n命题人特别喜欢在这种规整的网格图里挖坑。他们不会直接告诉你“要走6步向右、4步向上”，而是给你“7条南北向纵街、5条东西向横街”这种描述。很多学生看到“7条”就下意识认为要走7步，看到“5条”就认为走5步，结果把组合数算成了$C(10,5)=252$，完全偏离正确答案。命题人就是在考察你是否真正理解了“线段数”和“间隔数”的区别：$n$条平行线之间只有$n-1$个间隔，也就是对应$n-1$步。\n\n## 思考心法\n\n拿到题先别动笔算组合数，第一步是数段数：\n- 南北向有7条纵街，它们把东西方向分成了6段，所以必须走6步向右（或向上，取决于你定义的坐标系，这里统一说“横向段”）；\n- 东西向有5条横街，它们把南北方向分成了4段，所以必须走4步纵向。\n\n总步数自然就是6+4=10步。既然每一步只能选“向右”或“向上”，而总共要向右6次、向上4次，那么问题就转化为：在10步的序列里，选哪4步是向上的（或者选哪6步是向右的）。\n\n这就是组合数的定义：从$n$个不同元素中选取$k$个元素的方案数$C(n,k)$。这里$n=10$，$k=4$（选4步向上），所以答案是$C(10,4)$。\n\n## 具体计算\n\n$C(10,4) = \\dfrac{10!}{4!\\,6!} = \\dfrac{10\\times9\\times8\\times7}{4\\times3\\times2\\times1} = \\dfrac{5040}{24} = 210$。\n\n也可以写成$C(10,6)$，结果一样，只是计算时选较小的$k$（这里是4）更不容易出错。\n\n## 避坑指南\n\n- 别把“条数”当“步数”：7条纵街≠7步，而是6步；5条横街≠5步，而是4步。这是本题最大的陷阱。\n- 选错组合数的$k$：总步数是10，横向段数是6，纵向段数是4。你可以选4步纵向（$C(10,4)$）或者选6步横向（$C(10,6)$），两者相等。但千万别选5，那是把横街数直接当步数了，会算成252。\n- 计算阶乘时约分要细心：$10!/(4!6!)$分子分母都有公共因子，约掉后剩下$10\\times9\\times8\\times7 / 24$，别漏掉任何一个数。\n\n## 考频与趋势\n\n根据我手头的题库数据，计数原理（包含组合数、排列数、网格路径等）在NOIP系列考试中非常高频：题库共收录了36道相关真题，覆盖2007年到2025年的全部考试级别。具体逐年分布为：2007年4题、2008年2题、2009年1题、2010年2题、2019年6题、2020年4题、2021年3题、2022年1题、2023年3题、2024年5题、2025年5题。从分赛事看，CSP提高级考了14题，CSP入门级13题，NOIP普及组初赛5题，NOIP提高组初赛4题。\n\n可以看出，这类题目在近年（2019-2025）明显增多，尤其是普及组和入门级，说明命题人越来越喜欢用这种“看似简单实则易错”的网格计数题来区分学生。它不依赖编程技巧，纯粹考察数学建模和组合推理能力，是初赛中的经典必考点。\n\n## 预测\n\n基于上述高频数据和近年趋势，未来几年（2026-2028）在NOIP普及组初赛或CSP入门级中，网格最短路径计数几乎可以肯定还会以填空题或选择题形式出现。命题人可能会换一种表述方式，比如给出一个非矩形的网格（带障碍、可折返一次等），或者把“最短路径”改成“恰好走某步数的路径”，但核心依然是组合数的灵活运用。只要记住“线段数减一等于步数”这个关键点，就能稳稳拿下这类题。\n\n答案：210。