标数法与牛顿台阶问题关于“标数法”先来看两个最简单的例子 例1 ：从A到B的最短路径有多少条？ffil楚香凝解析：从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】楚香凝解析：标数法，共15种，选D例2：从A地到B地的道路如图所示，所有转弯均为直角，问如果要以最短距离从A地 到达B地，有多少种不同的走法可以选择？ 【黑龙江2015】A.14 B.15 C.18 D.21楚香凝解析：标数法，共15种，选B例3：下图为某大厦走火通道逃离路线。
某大厦集中所有的人员开展火灾逃生演习，从 入口 A点出发，要沿某几条线段才到出口 F点逃离中，同一个点或同一线段只能经过1 次假设所有逃离路线都是安全的，则不同的逃离路线最多有（ ）种广州2015】楚香凝解析：此题与标数法的区别在于，可以往上和斜上走，所以标数法不再适用，需 分类计算；A—D，之后有四种；A—B—D，之后有三种；A—B—C，之后有三种；共10种， 选C牛顿台阶问题（斐波那契递推数列）例1：十阶楼梯，小张每次只能走一阶或者两阶，请问走完此楼梯共有多少种方法?A.55B.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、5、8、13、21、34、55、89，选 D解法三：分类计算；走五次两阶、共五步，有1种；走四次两阶、共六步，选出四步来走两阶，有C （6 4） =15种；走三次两阶、共七步，选出三步来走两阶，有c （7 3） =35种; 走两次两阶、共八步，选出两步来走两阶，有C（8 2）=28种;走一次两阶、共九步，选出一步来走两阶，有C（9 1）=9种； 走0次两阶，有1种；共 1+15+35+28+9+1=89 种，选 D拓展：十阶楼梯，小张每次只能走一阶或者两阶或者三阶，请问走完此楼梯共有多少种 方法？A.89 B.169 C.230 D.274楚香凝解析：到达第十阶的情况数=（到达第九阶的情况数）+（到达第八阶的情况数） + （到达第七阶的情况数），以此类推…到达某阶的情况数等于前面三个数之和（前三项通过 列举得到），由此可得斐波那契递推数列如下：阶梯数: 1 2 3 4 5 6 7 8 9 10方法数: 1 2 4 7 13 24 44 81 149 274例2：小璐有8元钱，她准备从明天起，用这8元钱每天买一个冰激淋或者一包果冻吃。
冰激淋1元一个，果冻2元一包请问小璐花完这8元钱一共有多少种方法？ 【广东2003】A.21 B.34 C.55 D.89楚香凝解析：八元钱看作八个台阶，买个冰激凌相当于走一步、买包果冻相当于走两步，台阶数 1 2 3 4 5 6 7 8方法数 1 2 3 5 8 13 21 34方法数对应斐波那契数列，选B例3：兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来如 果现在给你一对幼兔，所有兔都不死，那么一年后可以繁殖多少对兔子？（假设每对兔子都 为雌雄各一只） 【吉林2008】A.144 B.233 C.286 D.315楚香凝解析：假设刚出生的兔子，一个月后长成大兔子、两个月及以后的每个月可以生 一对小兔子；小兔子的来源只有一种：大兔子生出小兔子；大兔子的来源有两种：小兔子经 过一个月变成大兔子、原来的大兔子依然是大兔子；可得下表月份数出生123 456 7 8 9 10 11 12小兔子对数1011 23大兔子对数0112 35兔子总对数1123 5813 21 34 55 89 144 233可得兔子总数为斐波那契数列，选B从本质分析，兔子总对数=（当月大兔子对数） +（当月小兔子对数），当月大兔子对数= 上个月的小兔子对数+上个月的大兔子对数=上个月兔子总对数；同理，当月小兔子数=上个 月的大兔子数=上上个月总兔子对数，所以兔子总对数=（上个月兔子总对数） +（上上个月 总兔子对数）。
例4：如图所示为两排蜂房，一只蜜蜂从左下角的1号蜂房到8号蜂房，假设只向右方（正右或右上或右下）爬行，则不同的走法有（ ） 【安徽2011】楚香凝解析：斐波那契数列；从1号出发，到达编号数 5 2 6 3 7 4 8对应方法数 1 2 3 5 8 13 21 ,选C从本质分析，到达7号的前一步有两类情况：【从3号往右上过来】或者【从6号往右 过来】，所以到达7号的情况数=【到达3号的情况数】+【到达6号的情况数】斐波那契数对于求一些标准格子图形的最短路径数，除了标数，还可以利用排列组合例5：从一个3X4的方格中的一个顶点A到顶点B的最短路线有几条？A.28 B.30 C.32 D.35楚香凝解析：往右走4步、往上走3步，总共7步，相当于从7步里选出3步往上走 即可，C (7 3) =35 种例6：从一个6X4的方格中的一个顶点A到顶点B、且不经过C点的最短路线有几条?A.96 B.100 C.120 D.195楚香凝解析：A-B的总情况数减去必经过C的情况数（先A-C,然后C-B）即可, C（10 4）-C（6 2）*C（4 2）=120 种，选 C巩固练习题：（有一定难度）例1：十阶楼梯，小张每次只能走一阶或者三阶，请问走完此楼梯共有多少种方法？A.32 B.40 C.46 D.28楚香凝解析：到达第十阶的情况数=（到达第九阶的情况数）+ （到达第七阶的情况数）, 以此类推…到达某阶的情况数等于【前面挨着的第一个数】与【前面挨着的第三个数】之和 （前三项通过列举得到），由此可得斐波那契递推数列如下：阶梯数：1 2 3 4 5 6 7 8 9 10方法数： 1 1 2 3 4 6 9 13 19 28 ,选 D例2： 一条小河宽6米,一只青蛙向前跳一次可以跳0.5米或1米，这只青蛙从河的一 岸跳到对岸共有多少种跳法？A.74 B.92 C.168 D.233楚香凝解析：相当于总共有12级台阶，每次可以走一步或两步，阶梯数： 1 2 3 4 5 6 7 8 9 10 11 12方法数： 1 2 3 5 8 13 21 34 55 89 144 233，选D例3：余梅今年4岁，爱吃泡泡糖，她现有10颗完全相同的泡泡糖，妈妈只允许她每 次吃一颗或两颗，则她共有（）种不同的组合方法吃完这些泡泡糖。
【陕西2015】A.72 B. 89 C.95 D.107 E.112 F.124 G.136 H.144楚香凝解析：牛顿台阶问题，本质斐波那契递推数列；台阶数 1 2 3 4 5 6 7 8 9 10方法数 1 2 3 5 8 13 21 34 55 89 ,选 B例4：如图所示为三排蜂房，一只蜜蜂从左下角的蜂房到右下角的蜂房，假设只向右方 （正右或右上或右下）爬行，则不同的走法有（ ）种？例：5:从一个4X4的方格中的一个顶点A到顶点D,必须经过B点且不能经过C点 的最短路线有几条？■115A.12 B.15 C.18 D.24楚香凝解析：C（4 2）*[C（4 2）-C（3 2）]=18 条，选 C对本类问题做进一步拓展例1：十阶楼梯，小张每次只能走一阶或者两阶，若不能经过第7阶，走完此楼梯共有 多少种方法？A.21 B.26 C.54 D.89楚香凝解析：解法一：牛顿台阶问题，本质斐波那契递推数列;台阶数 1 2 3 4 5 6 7 8 9 10方法数 1 2 3 5 8 13 0 13 13 26 ，共 26 种，选 B解法二：分步，1-6阶有13种，然后直接到达第八阶，还剩下两阶有2种，共13*2=26 种，选B例2：十阶楼梯，小张每次只能走一阶或者两阶，若必须经过第7阶，走完此楼梯共有多少种方法？A.42 B.54 C.63 D.72楚香凝解析：解法一：牛顿台阶问题，本质斐波那契递推数列；台阶数 1 2 3 4 5 6 7 8 9 10方法数 1 2 3 5 8 13 21 21 42 63 ，共63种。
解法二：分步，1-7阶有21种，还剩下三阶有3种，共21*3=63种，选C例3 ：由1、3、4组成的各位数字和为9的多位数共有多少个？（可以只用1种或2种 数字）A.20 B.25 C.30 D.40楚香凝解析：分类讨论方法不再详述 转化为台阶问题，总共九级台阶，每次可以走一步、三步或四步台阶数 1 2 3 4 5 6 7 8 9方法数 1 1 2 4 6 9 15 25 40 ，共40种，选D例4 ：有1 5枚棋子，每次可以取出1-4个，但每次取过后剩下的不能是3或4的倍数， 有多少种取法？A.33 B.42 C.60 D.78楚香凝解析：树形图标数的方法不再详述转化为台阶问题，共15个台阶，其中3的倍数或4的倍数阶不能到达比如到达第七阶的情况数=（到达第六阶的情况数）+（到达第五阶的情况数）+（到达 第四阶的情况数）+（到达第三阶的情况数），其中有些情况数为 0；取出数：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15剩余数：14 13 12 11 10 9 8 7 6 5 4 3 2 1 0方法数：1 2 0 4 7 0 0 11 0 11 0 0 11 22 33 ,选 A例5：20枚硬币分若干次取完，每次取完后不能留下3的倍数，有多少种取法？A.4200 B.5672 C.7564 D.8192楚香凝解析：转化为台阶问题，取完后剩余数为19-1，其中第18、15、12、9、6、3 阶不能到达，还剩下19-6=13个台阶，每个台阶到达与否都有2种选择，共213=8192种，选 D。