标数法与牛顿台阶问题.pdf

标数法与牛顿台阶问题 关于“标数法” ，先来看两个最简单的例子。 例 1：从 A 到 B 的最短路径有多少条？ 楚香凝解析：从 A 到 C 有一种路径，所以在 C 点标记个“ 1”；从 A 到 D 有一种路径， 所以在 D 点也标记一个 1；到 B 点有两类情况，可以从 C过来，也可以从 D 过来，所以到达 B 点的情况数 = （到达C 点的情况数） + （到达D 点的情况数） ，所以在 B 点标记 1+1= “2 ”。 例 2 ：从 A 到 B 的最短路径有多少条？ 楚香凝解析：从 A 到 C 有一种路径，所以在 C 点标记个“ 1”；从 A 到 D 有一种路径， 所以在 D 点也标记一个 1；到 E 点有两类情况，可以从 C过来，也可以从 D过来，所以在 E 点标记 1+1= “2”；从 A 到 F 有一种路径，所以在 F 点标记个“ 1”；到 B 点有两类情况，可 以从 F 过来，也可以从 E 过来，所以在 B 点标记 1+2= “3 ”。 注意：标数法适用的前提条件为“ 最短路径 ”，更通俗来讲，即不能走“回 头路”。 下面来看近几年出现过的三道真题。 例 1：A、B、C 三地的地图如下图所示，其中 A 在 C 正北， B 在 C 正东，连线处为道路。 如要从 A 地到达 B 地，且途中只能向南、东和东南方向行进，有多少种不同的走法： 【山东 2014】 A.9B.11C.13D.15 楚香凝解析：标数法，共 15 种，选 D 例 2 ：从 A 地到 B 地的道路如图所示，所有转弯均为直角，问如果要以最短距离从 A 地 到达 B 地，有多少种不同的走法可以选择？【黑龙江 2015 】 A.14 B.15 C.18 D.21 楚香凝解析：标数法，共 15 种，选 B 例 3 ：下图为某大厦走火通道逃离路线。某大厦集中所有的人员开展火灾逃生演习，从 入口 A 点出发，要沿某几条线段才到出口 F 点。逃离中，同一个点或同一线段只能经过 1 次。假设所有逃离路线都是安全的，则不同的逃离路线最多有（）种。 【广州 2015】 A.8 B.9 C.10 D.11 楚香凝解析：此题与标数法的区别在于， 可以往上和斜上走， 所以标数法不再适用，需 分类计算； A→ D，之后有四种； A→ B→ D，之后有三种； A→ B→C，之后有三种；共 10 种， 选 C 牛顿台阶问题（斐波那契递推数列） 例 1：十阶楼梯，小张每次只能走一阶或者两阶，请问走完此楼梯共有多少种方法？ A.55 B.67 C.74 D.89 楚香凝解析： 解法一：列举找规律； 阶梯数 : 1 2 3 4 5 6 7 8 9 10 方法数 : 1 2 3 5 8 13 21 34 55 89 走到 1 阶只有 1 种方法； 走到 2 阶有 2 种 （1+1 或直接上 2 阶）；走到 3 阶有 3 种 （1+1+1 或 1+2 或 2+1）, 依次类推，选 D 解法二：到达第十阶的前一步只有两类情况： 【从第九阶迈一步上来】或者【从第八阶 迈两步上来】 ，所以到达第十阶的情况数 = （到达第九阶的情况数） + （到达第八阶的情况数） ， 以此类推，到达某阶的情况数等于前面两个数之和（前两项通过列举得到） ，由此可得斐波 那契递推数列 1、2、3