noip讲义2-归纳法.ppt

《noip讲义2-归纳法.ppt》由会员分享，可在线阅读，更多相关《noip讲义2-归纳法.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、归纳法归纳法归纳法是由一系列有限的特殊事例得出一般规律的推理方法。归纳法是由一系列有限的特殊事例得出一般规律的推理方法。例如、求前例如、求前n个奇数的和。个奇数的和。分析：如用分析：如用S(n)表示前表示前n个奇数的和，则个奇数的和，则S(1)=1,S(2)=1+3=4,S(3)=1+3+5=9,S(4)=1+3+5+7=16,S(5)=1+3+5+7+9=25。可以看出，当可以看出，当n取取1，2，3，4，5时，时，S(n)=n2。因此可以因此可以归纳出求前归纳出求前n个奇数的和的一般规律，即个奇数的和的一般规律，即S(n)=n2。上面的归纳法是不完全归纳法，因为由它得到的结论不一上面的归纳

2、法是不完全归纳法，因为由它得到的结论不一定对任意的定对任意的n都都成立成立17世纪著名的德国数学家莱布尼兹曾证明，世纪著名的德国数学家莱布尼兹曾证明，对于所有对于所有的正整数的正整数n，数，数n3-n能被能被3整除，数整除，数n5-n能被能被5整除，数整除，数n7-n能被能被7整除整除，因此他猜测：，因此他猜测：对所有的奇数对所有的奇数k和任意的自然数和任意的自然数n，数，数nk-n能被能被k整除整除。29-2=510不能被不能被9整除整除要证明对所有的要证明对所有的n都成立，就必须使用下面介绍的数学归纳法都成立，就必须使用下面介绍的数学归纳法1、证明当、证明当n取第一个值取第一个值n0时结论

3、正确。时结论正确。2、假设当、假设当n=k时结论成立，证明当时结论成立，证明当n=k+1时结论也成立。时结论也成立。证明：证明：、当、当n=时，左边，右边，此时等式成立。时，左边，右边，此时等式成立。、假设当、假设当n=k时等式成立，即时等式成立，即（k-1)=k2，那么当那么当n=k+1时时（k-1）+2(k+1)-1=k2+2(k+1)-1=k2+2k+1=(k+1)2练习1如图所示：线段如图所示：线段AB上共有上共有10个点（包括两个端点），那么这条线段上个点（包括两个端点），那么这条线段上一共有多少条不同的线段？一共有多少条不同的线段？分析分析:先从先从AB之间只有一个点开始，再逐步增

4、加之间只有一个点开始，再逐步增加AB之间的点数，找出点和线段之之间的点数，找出点和线段之间的规律。间的规律。AB之间只有之间只有1个点：线段有个点：线段有1+2=3条。条。AB之间只有之间只有2个点：线段有个点：线段有1+2+3=6条。条。AB之间只有之间只有3个点：线段有个点：线段有1+2+3+4=10条。条。AB之间只有之间只有4个点：线段有个点：线段有1+2+3+4+5=15条。条。不难发现，当不难发现，当AB之间有之间有8个点时，线段有个点时，线段有1+2+3+4+5+6+7+8+9=45条。条。若再进一步研究可得出这样得规律，线段数若再进一步研究可得出这样得规律，线段数=。教学中要训

5、练学生用不完全归纳法解题教学中要训练学生用不完全归纳法解题练习2在一张四边形纸上共有在一张四边形纸上共有10个点，如果把四边形的顶点算个点，如果把四边形的顶点算在一起，则一共有在一起，则一共有14个点。已知这些点中的任意三个点都不个点。已知这些点中的任意三个点都不在同一直线上。按照下面规定把这张纸片剪成一些三角形：在同一直线上。按照下面规定把这张纸片剪成一些三角形：每个三角形的顶点都是这每个三角形的顶点都是这14个点中的个点中的3个；个；每个三角形内都不再有这些点。每个三角形内都不再有这些点。那么，这张四边形的纸最多可以剪出（那么，这张四边形的纸最多可以剪出（）个三角形。）个三角形。在在10个

6、点中任意取一点，与四边形的四个顶点构成个点中任意取一点，与四边形的四个顶点构成4个三个三角形。再在剩下的角形。再在剩下的9个点中任意取一点，它必定落在某一个三个点中任意取一点，它必定落在某一个三角形中，只能与三角形的三个顶点构成三个三角形，即增加角形中，只能与三角形的三个顶点构成三个三角形，即增加2个三角形。以后各点情况都与此相同，除了第一点增加个三角形。以后各点情况都与此相同，除了第一点增加4个三个三角形外，其余各点都只增加角形外，其余各点都只增加2个三角形。个三角形。所以共可以剪出所以共可以剪出4+(101)2=22（个）三角形。（个）三角形。4+2(n-1)练习练习3将将Ln定义为求在一

7、个平面中用定义为求在一个平面中用n条直线所能确定的最大区条直线所能确定的最大区域数目。例如：当域数目。例如：当n=1时，时，L1=2，进一步考虑，用，进一步考虑，用n条直线，条直线，放在平面上，能确定的最大区域数目放在平面上，能确定的最大区域数目Ln是多少？是多少？1234567891011n=1,L1=2,F(1)=2;n=2,L2=4,F(2)=F(1)+2;n=3,L3=7,F(3)=F(2)+3;n=4,L4=11,F(4)=F(3)+4;n=5,L5=16,F(5)=F(4)+5;可得到递推公式：可得到递推公式：F(n)=F(n-1)+n,F(n)=n+(n-1)+(n-2)+2+F

8、(1)=练习练习4将一张长方形的纸对折，可得到一条折痕，继续对将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到条折痕，那么对折三次后，可得到条折痕，那么对折n次，可得到几条次，可得到几条折痕？折痕？第一次对折第一次对折1条折痕，第二次对折条折痕，第二次对折3条折痕，第三次对条折痕，第三次对折折7条折痕，第四次对折条折痕，第四次对折15条折痕，条折痕，所以我们猜想第所以我们猜想第n次次对折后的折痕条数是对折后的折痕条数是2n-1练习练习5如图如图,第一次把三角形剪去一个角后第一次把三角形剪去

9、一个角后,图中最多有四个角图中最多有四个角,第二次再把新产生的角各剪一刀第二次再把新产生的角各剪一刀,如此下去如此下去,每一次都是每一次都是把新产生的角各剪一刀把新产生的角各剪一刀,则第则第n次剪好后次剪好后,图中最多有多少个图中最多有多少个角角?可知后一次新产生的角的个数是前一次新产生的可知后一次新产生的角的个数是前一次新产生的角的个数的倍，再加上就是后一次产生的角的总角的个数的倍，再加上就是后一次产生的角的总数。因此，剪数。因此，剪n次后，图中最多有角：次后，图中最多有角：2+2n练习练习6下图中把大正方形各边平均分成了下图中把大正方形各边平均分成了5份，此时有份，此时有55个正方个正方形

10、。如果把正方形各边平均分成形。如果把正方形各边平均分成n份，那么得到的正方形总数份，那么得到的正方形总数为多少？为多少？52+42+32+22+12=55n2+(n-1)2+(n-2)2+22+12=1/6n(n+1)(2n+1)练习练习7如图所示，在正六边形如图所示，在正六边形A周围画出周围画出6个同样的正六边形（阴个同样的正六边形（阴影部分），围成第影部分），围成第1圈；在第圈；在第1圈外面再画出圈外面再画出12个同样的正六边个同样的正六边形，围成第形，围成第2圈。按这个方法继续画下去，当画完第圈。按这个方法继续画下去，当画完第10圈时，图圈时，图中共有多少个与中共有多少个与A相同的正六边

11、形？相同的正六边形？第一圈有第一圈有6个正六边形；个正六边形；第二圈有第二圈有62个正六边形；个正六边形；第三圈有第三圈有63个正六边形；个正六边形；第第n圈有圈有6n个正六边形；个正六边形；所以图中共有所以图中共有1+6（1+2+3+4+5+6+7+8+9+10）=331个正六边形。个正六边形。练习练习8在在nn的正方形钉子板上（的正方形钉子板上（n是钉子板每边上的是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的钉子数），求连接任意两个钉子所得到的不同长度的线段种数线段种数.92514练习练习9如图，平面内有公共端点的六条射线如图，平面内有公共端点的六条射线，从射线从射线OA开

12、始按逆时针方向依次在射线上写出数字开始按逆时针方向依次在射线上写出数字1，2，3，4，5，6，7，问：问：2007在哪条射线上？在哪条射线上？练习练习10如图，以等腰三角形如图，以等腰三角形AOB的斜边为直角边向外作第的斜边为直角边向外作第2个等腰直个等腰直角三角形角三角形ABA1，再以等腰直角三角形，再以等腰直角三角形ABA1的斜边为直角边向的斜边为直角边向外作第外作第3个等腰直角三角形个等腰直角三角形A1BB1，如此作下去，若，如此作下去，若OAOB1，则第，则第n个等腰直角三角形的面积个等腰直角三角形的面积Sn_。练习11计算计算13+23+33+43+53+63+73+83+93+10

13、3的值。的值。练习练习12 2000个学生排成一行，依次从左到右编上个学生排成一行，依次从左到右编上12000号，然后从左到右按一、二号，然后从左到右按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的人离开队伍，报数，报一的离开队伍，剩下的人继续按一、二报数，报一的人离开队伍，按按这个规律如此下去，直至当队伍只剩下一人为止。问：最后留下的这个人原来的号这个规律如此下去，直至当队伍只剩下一人为止。问：最后留下的这个人原来的号码是多少？码是多少？分析分析:我们通过前几次留在队伍中的学生的编号找出规律。我们通过前几次留在队伍中的学生的编号找出规律。第一次留下的学生编号是：第一次留下的学生

14、编号是：2，4，6，8，10，；都是都是2的倍数。的倍数。即即21的倍数的倍数第二次留下的学生编号是：第二次留下的学生编号是：4，8，12，16，20，；都是都是4的倍的倍数，即数，即22的倍数的倍数第一次留下的学生编号是：第一次留下的学生编号是：8，16，24，32，40，；都是；都是8的倍的倍数。即数。即23的倍数的倍数由于由于210=10242000211=2048；这样可知，最后留下学生的号码一定是这样可知，最后留下学生的号码一定是1024。练习练习13999999999999的乘积中有多少个数字是奇数？的乘积中有多少个数字是奇数？10个910个9我们可以从最简单的我们可以从最简单的9

15、9的乘积中有几个奇数着手寻找规律。的乘积中有几个奇数着手寻找规律。99=81，有，有1个奇数；个奇数；9999=99（100-1）=9900-99=9801，有，有2个奇数；个奇数；999999=999（1000-1）=999000-999=998001，有，有3个个奇数；奇数；从而可知，从而可知，999999999999的乘积中共有的乘积中共有10个数字是奇个数字是奇数。数。10个910个9练习练习14n*(n+1)-141练习练习15如图如图1，是棱长为，是棱长为a的小正方体，图的小正方体，图2，图，图3由这样的小正由这样的小正方体摆放而成按照这样的方法继续摆放，自上而下分别叫方体摆放而成

16、按照这样的方法继续摆放，自上而下分别叫第一层、第二层、第一层、第二层、第、第n层，第层，第n层的小正方体的个数记层的小正方体的个数记为为sn写出当写出当n=10时，时，s10=().5513610如图，有边长为如图，有边长为1的等边三角形卡片若干张，使用这些的等边三角形卡片若干张，使用这些三角形卡片拼出边长分别是三角形卡片拼出边长分别是2，3，4，的等边三角形（如的等边三角形（如图所示）。根据图形推断，每个等边三角形所用卡片总数图所示）。根据图形推断，每个等边三角形所用卡片总数sn与边长与边长n之间的关系。之间的关系。49162536练习练习16 Hanoi双塔问题双塔问题 给定给定A、B、C

17、三根足够长的细柱，在三根足够长的细柱，在A柱上放有柱上放有2n个中个中 间有孔的圆盘，共有间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）的情形）。现要将这些圆盘移到。现要将这些圆盘移到C柱上，在移动过程中可放在柱上，在移动过程中可放在B柱上暂柱上暂存。要求：存。要求：（1）每次只能移动一个圆盘；）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺三根细柱上的圆盘都要保持上小下大的顺序；序；任务：设任务：设An为为2n个圆盘完成上述任

18、务所需的最少移动次个圆盘完成上述任务所需的最少移动次数，对于输入的数，对于输入的n，输出输出An。输入文件输入文件hanoi.in为一个正整数为一个正整数n，表示表示在在A柱上放有柱上放有2n个圆盘。个圆盘。输出文件输出文件hanoi.out仅一行，包含一个正整数仅一行，包含一个正整数，为完成上为完成上述任务所需的最少移动次数述任务所需的最少移动次数An。【样例样例1】hanoi.inhanoi.out12【样例样例2】hanoi.inhanoi.out26【限制限制】对于对于50%的数据，的数据，1=n=25 对于对于100%的数据，的数据，1=n=200【提示提示】设法建立设法建立An与与

19、An-1的递推关系式。的递推关系式。解题思路解题思路:数学归纳数学归纳+高精度高精度 Hanoi单塔单塔的最少移动步数是的最少移动步数是2 n-1，现在有现在有2层，可以层，可以将将2层看作层看作1层，便回到了单塔的问题上，每移动想象中的层，便回到了单塔的问题上，每移动想象中的“单个单个”盘子需要两步，故盘子需要两步，故Hanoi双塔双塔=Hanoi单塔单塔*2 可得公式：可得公式：f(n)=2 n+1-2 高精度只要编个乘法就可以了，不要忘记最后高精度只要编个乘法就可以了，不要忘记最后-2begin assign(input,hanoi.in);assign(output,hanoi.out

20、);reset(input);rewrite(output);readln(n);ppp(n+1);a1:=a1-2 i:=100;while ai=0 do i:=i-1;for j:=i downto 1 do write(aj);close(input);close(output);end.var n,i,j:integer;a:array1.100 of 0.9;procedure ppp(k:integer);var i,j,w,s:integer;begin a1:=1;初值初值 w:=0;for i:=1 to k do for j:=1 to 100 do begin s:=a

21、j*2+w;aj:=s mod 10;w:=s div 10;end;end;Cantor表表现代数学的著名证明之一是现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的。证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：他是用下面这一张表来证明这一命题的：1/11/21/31/41/5.2/12/22/32/4.3/13/23/3.4/14/2.5/1我们以蛇形给上表的每一项编号。第我们以蛇形给上表的每一项编号。第1项是项是1/1，然后是，然后是1/2，2/1，3/1，2/2.输入输入:整数整数n(1=n=10000000)输出输出:表中的第表中的第N项项样例样例:

22、input:n=7output:1/4分析分析：不难看出，第：不难看出，第K个斜行（个斜行（“/”方向）上每个分数的方向）上每个分数的分子分母之和为分子分母之和为K+1,而表的填充顺序正是依次填写每个斜行，而表的填充顺序正是依次填写每个斜行，因此先算出第因此先算出第N项所在的斜行项所在的斜行K。显然显然K是满足是满足Nkdobeginn:=n-k;k:=k+1;end;先确定在哪一斜行，再分奇偶讨论先确定在哪一斜行，再分奇偶讨论ifkmod2=0thenwriteln(n,/,k+1-n)elsewriteln(k+1-n,/,n);end.计算正方形、长方形个数计算正方形、长方形个数设有一个

23、设有一个N*M方格的棋盘（方格的棋盘（l=N=100,1=M=100），），求出该棋盘求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。中包含有多少个正方形、多少个长方形（不包括正方形）。例如：当例如：当N=2,M=3时时(如下图如下图)正方形的个数有正方形的个数有8个：即边长为个：即边长为1的正方形有的正方形有6个；边长为个；边长为2的正方形有的正方形有2个。个。长方形的个数有长方形的个数有10个：即个：即2*1的长方形有的长方形有4个，个，1*2的长方形有的长方形有3个，个，3*1的长方形有的长方形有2个，个，3*2的长方形有的长方形有1个。个。输入文件输入文件1.in,只有一

24、行，两个整数只有一行，两个整数N和和M.输出文件输出文件1.out,只有一行，为两个整数（中间用空格隔开），分别表只有一行，为两个整数（中间用空格隔开），分别表示所求的正方形的个数与长方形的个数。示所求的正方形的个数与长方形的个数。样例：输入样例：输入23输出输出810对于棋盘中的任意一个正方形而言，只要确定了对于棋盘中的任意一个正方形而言，只要确定了左上角的位置和边长后，该正方形就完全确定了因左上角的位置和边长后，该正方形就完全确定了因此只要此只要穷举穷举除最下面和最右边之外的每个格点，除最下面和最右边之外的每个格点，算出算出以它们作为正方形的左上角位置时边长不同的正方形以它们作为正方形的左

25、上角位置时边长不同的正方形个数，然后累加起来就可得到全部正方形的个数同个数，然后累加起来就可得到全部正方形的个数同样地也可以类似地算出长方形个数（包括正方形）样地也可以类似地算出长方形个数（包括正方形）012301234vari,j,n,m,s:longint;beginreadln(n,m);s:=0;fori:=0ton-1doforj:=0tom-1do枚举可作为正方形左上角的格点枚举可作为正方形左上角的格点ifn-im-jthens:=s+n-ielses:=s+m-j;write(s,);s:=-s;fori:=0ton-1doforj:=0tom-1dos:=s+(n-i)*(m-j);writeln(s);end.以（以（i,j）为左上角为左上角格点的正方形个数格点的正方形个数以（以（i,j）为左上角为左上角格点的长方形个数格点的长方形个数