利用递推思想解决计数问题

我们经常碰到有些计数问题看似排列组合应用题 ,但其复杂的情形常令人无从下手 ,若从元素的递增考虑 ,建立递推数列往往能迎刃而解 .例 1　有一楼梯共 10级 ,如果规定每步只能跨上一级或二级 ,要走上 10级 ,共有多少种走法 ?解　设上n级楼梯共有an 种走法 ,当n= 1时 ,一级楼梯只有 1种走法 ,a1 =1;当n= 2时 ,两级楼梯共有两种走法 ,a2 =2 ,n 1级楼梯的走法分两种情况 :第一种情况 :走完前n级楼梯有an 种走法 ,走第n 1级楼梯只有 1种走法 ;第二种情况 :走完前n-1级楼梯有an - 1种走法 ,第n级楼梯与第n 1级楼梯一步走 ,也是一种走法 .由分类…     

建立递推数列求解一类计数问题

排列组合中经常会碰到一类特殊的计数问题,看似排列组合应用题,但其复杂的情形常令人无从下手.若能根据题目特点建立递推数列则问题往往能迎刃而解.例1 有一楼梯共10级,如果规定每步只能跨上一级或二级,要走上这10级楼梯,共有多少种走法?解:设上 n 级共有 a_n 种走法,当 n=1时,一级楼梯只有1种走法,a_1=1;当 n=2时,两     

从走楼梯引出斐氏数列组合等式的一个模型解释

问题:某楼梯共有n级,每步只能跨1级或2级,走完该楼梯共有多少种不同的走法?     

用斐波那契数列解决一类组合数求和问题

高中数学教材课外阅读中有一个问题: 问题1 现要上一个10级的楼梯,可1步走 1级或1步走2级,问共有多少种走法? 解:分以下几种情况考虑:     

递推数列“亮剑”排列组合与概率

一、上楼梯问题 例1．有一楼梯共10级,若每次只能跨上一级或二级,要上第10级,共有多少种走法？（只要有一步不同就认为是不同的走法）     

暮然回首 灯火阑珊——善用逆向思维,实现思维突破

<正>一、对两道试题的分析与认识试题1登楼梯时规定,每次只能跨上1级或2级台阶,今欲登上10级楼梯,则不同走法的总数为_.分析这是一道2015年北大自招数学试题.正向思维,从第一级开始思考,由于每一次可以跨上1级或2级台阶,过程比较复杂,很难数清楚有多少走法;逆向思考,从最后一级思考,设走上n级楼梯有a_n种方法,则有a_1=1,a_2=2,注意到每一步只能上1级或2级     

递推法解排列组合问题

[例1] 走上10级的阶梯,每步可一级或两级,问有多少种不同的走法? 解法1 按每种走法中一步上两级的步数k(k=0,1,2,3,4,5)分成6类,走上10级阶梯的步数是10-k,这一类的走法数是C_(10-k)~k。由加法原理,不同走法总数为 N=C_10~0+C_9~1+C_8~2+C_7~2+C_6~4+C_5~5=89。下面是递推法。解法2 设走上n级阶梯的走法有a_n种,易知a_1=1,a_2=2,当n>2时,若第一步上一级则有a_(n-1)种走法,第一步上两级则有a_(n-2)种走法,故a_n=a_(n-1)+a_(n-2)(n≥3)。于是当阶梯级数n=1,2,…,10时,走法数依次是 1,2,3,5,8,13,21,34,55,89。即a_(10)=89。注意到解法2中的数列{a_n}就是菲波那奇数列,它的通项公式为     

一道组合应用题的探究

习题有一台阶共10级,每次可跨上1级台阶或2级台阶,那么6步走到顶,共有多少种不同的走法?分析根据题目分析,10级台阶6步走到顶,那么必须是4步2级台阶、2步1级台阶这样才能     

一个问题引发的思考

有一楼梯共10级,如果规定每步只能跨上一级或两级,要上到第10级,共有多少种不同走法?对此,文1给出了四种解法.笔者读后受     

一杯水

从我的教室,到四楼水房;通常有2种走法：如果从教室前门的楼梯上去,要走22级台阶,经过3间教室,拐2个弯。     

网格不反向路径走法的简单计算

关于网格不反路径走法问题 ,文 ( 1)中给出了一个公式 ,但过程太繁 ,本文给出一种简单的方法 .例　某城市道路均为横纵方向的 ,如图 ,从M处到N处 ,只能向东或向北 ,共有多少种走法 ?解　标 1处的结点有一种走法 ,标 2处的结点有 2种走法 ,即 1+ 1=2 ,标 3处的结点有三种走法 ,即 1+ 2 =3,… ,标 10处的结点有 4 + 6 =10种走法 ,这个过程很象杨辉三角的构成规律 ,N处结点的走法有 15+ 2 0 =35种走法 .利用这种填法 ,很繁多的格也会很快填完网格不反向路径走法的简单计算$上海市奉贤中学!201400@王志和[1]　王彤、赵常红.网格不反向路径种数…     

电路——一个电子的通路

人教版高中数学第二册(下A)(以下简称“课本”)第80页有这样一个问题———“如图1,从甲地到乙地,可以乘火车,也可以乘汽车,一天中,火车有3班,汽车有2班,那么一天中,乘坐这些交通工具从甲地到乙地共有多少种不同的走法?”图1给出的答案是:“共有3 2=5种不同的走法·”并由此引出了分类计数原理·这是很正确的·因为“从甲地到乙地的走法”是指“一个人从甲地到乙地的走法”·“一些人乘火车1,另一些人乘汽车1”不能算作第6种走法·课本第83页习题10·1的第4题是———“如图2,一条电路从A处到B处接通时,可以有多少条不同的线路?”文[1]认…     

排列组合的两个性质及应用

性质1把m个a和n个b排成一列,共有Cmm n种排法.证明这个问题就是把m个a和n个b放入m n个格子,先选m个格子放入a,余下的格子都放b,故有Cmm 1种放法。例1某人走10级台阶,每步走1级或2级,7步走完,共有多少种不同的走法?解由已知可知,此人必须走3步2级和4步1级,这就相当于把3个2和4个     

世博楼梯问题

为了践行上海世博会节能环保的理念,在参观世博会场馆时,小张选择走楼梯而不是乘电梯。他不时还一跨两级,对一段只有3级的楼梯,小张有3种不同的走法：一级、一级、一级;一跨、一级;一级、一跨（见图）。     

发现联系,体会美妙——巧用“杨辉三角”解一类竞赛题

题目(重庆市2002年初中数学竞赛试题(初一))如图1,从A点到B点(只从左向右,从上到下)共有()种不同的走法.(A)24(B)20(C)16(D)12如果根据要求一种一种地去数,既麻烦又容易出错,而利用“杨辉三角”则很容易得到解决,现介绍如下:以A点为起点,按照题目的要求,渐次地寻找到达每一个点的不同走法的种数,并在相应的位置上记录下来,如图2所示.(1)从A点到C点的不同走法只有1种,A→C,记作C(1),同理得D(1),E(1),F(1).(2)从A点到G点的不同走法只有2种:分别是A→C→G,A→D→G,记作G(2).(3)从A点到H点的不同走法共有3种,分别是A→C→E→H,A→C…     

网格不反向路径种数的计算公式

1　问题的提出( 1)网格不反向路径种数问题散见于各种资料中 ,但都是些具体的数值计算 ,笔者尚未见到对这一问题的一般性解答 本文旨在就该一般性问题给出解决的思路方法及计算的公式 ( 2 )具体问题 :①如图 1,在某个城市中 ,Ｍ、Ｎ两地之间有整齐的道路网 ,若规定只能向东或北两个方向沿图中矩形的边前进 ,则从Ｍ到Ｎ不同走法共有 (　　 ) Ａ 2 5种　　Ｂ 15种Ｃ 13种　　Ｄ 10种②如图 2 ,某区有 7条南北向街道 ,5条东西向街道 图中从Ａ到Ｂ的最短走法有多少种 ?图 1　　　　　　　　图 2( 3)一般问题 :将上题中的“7”、“5”分别换…     

上楼的问题(1)——让符号说话

问题有人要上楼,此人每步能向上走1阶或2阶,如果楼梯有6阶,他有几种不同的走法? 分析与解此人上楼最多走6步(这时每步上1阶),最少走3步(这时每步上2阶),当然,还可以走5步(其中有1步上2阶),也可以走4步(其中有2步每步上2阶).再没有其他的走法了.因此,可以根据此人上楼的步数分     

数出不同的走法

<正>公园里有两处景点,如下图,图中的线表示道路,绿色表示草地,蓝色表示人工湖。如果从A点出发后不能再返回A点,那么你能数出从A点到B点各有多少种走法吗？要想既不重复又不遗漏地数出从A点到B点的所有走法,我们可以采取画线标注的方法来数。图1中,我们可以发现从A点直接到B点（不经过C点）有两种走法;经过C点,则有2×2=4 （种）走法。所以,图1中从A点直接到B点,一共有2+4=6 （种）走法,见图3。     

有理数自测题（B）

一、填空题(每题5分,计35分)图11.若m,n互为相反数,则m-5+n=;的绝对值等于3.2.图1是“家乐超市”中“柔顺牌”洗发水的价格标签,请你在横线上填写它的原价.3.从数-6,1,-3,5,-2中任取三个数相乘,则其最小的积是.4.平方等于94的数为,的立方等于-27.5.绝对值小于5的所有整数有个,它们的积为.6.点A在数轴上距原点3个单位长度,且位于原点左侧,若将A向右移动4个单位长度,再向左移动1个单位长度,此时点A所表示的数是.7.小明同学在上楼梯时发现:若只有一个台阶时,有一种走法;若有二个台阶时,可以一阶一阶地上,或者一步上二个台阶,共有两种走法;如…     

关于《一道排列组合题的解法探讨》的补遗——递推法在排列组合解题中的应用

《数学通报》1997年第7期刊载的《一道排列组合题的解法探讨》一文中,研讨了下列一排列组合题:有一楼共10级,如果规定每次只能跨上一级或两级,要上第10级,共有多少种不同的走法?该文对此题给出了四种解法(插空法、排坐法、盒子法、公式法),读后深得教益,但笔者感到,这几种解法都要分六类考虑,比较烦杂,在进一步探讨解法时,笔者又发现一种较为简捷特别的方法——递推法,写出来供读者参考,也算是对上述一文的补遗.