noip讲义2-归纳法.ppt

归纳法,归纳法是由一系列有限的特殊事例得出一般规律的推理方法。例如、求前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。,上面的归纳法是不完全归纳法，因为由它得到的结论不一定对任意的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时结论正确。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之间只有一个点开始，再逐步增加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条。若再进一步研究可得出这样得规律，线段数=。,教学中要训练学生用不完全归纳法解题,练习2,在一张四边形纸上共有10个点，如果把四边形的顶点算在一起，则一共有14个点。已知这些点中的任意三个点都不在同一直线上。按照下面规定把这张纸片剪成一些三角形：每个三角形的顶点都是这14个点中的3个；每个三角形内都不再有这些点。那么，这张四边形的纸最多可以剪出（）个三角形。,在10个点中任意取一点，与四边形的四个顶点构成4个三角形。再在剩下的9个点中任意取一点，它必定落在某一个三角形中，只能与三角形的三个顶点构成三个三角形，即增加2个三角形。以后各点情况都与此相同，除了第一点增加4个三角形外，其余各点都只增加2个三角形。所以共可以剪出4+(101)2=22（个）三角形。,4+2(n-1),练习3,将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L1=2，进一步考虑，用n条直线，放在平面上，能确定的最大区域数目Ln是多少？,n=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(1)=,练习4,将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到条折痕，那么对折n次，可得到几条折痕？,第一次对折1条折痕，第二次对折3条折痕，第三次对折7条折痕，第四次对折15条折痕，所以我们猜想第n次对折后的折痕条数是2n-1,练习5,如图,第一次把三角形剪去一个角后,图中最多有四个角,第二次再把新产生的角各剪一刀,如此下去,每一次都是把新产生的角各剪一刀,则第n次剪好后,图中最多有多少个角?,可知后一次新产生的角的个数是前一次新产生的角的个数的倍，再加上就是后一次产生的角的总数。因此，剪n次后，图中最多有角：2+2n,练习6,下图中把大正方形各边平均分成了5份，此时有55个正方形。如果把正方形各边平均分成n份，那么得到的正方形总数为多少？,52+42+32+22+12=55,n2+(n-1)2+(n-2)2+22+12=1/6n(n+1)(2n+1),练习7,如图所示，在正六边形A周围画出6个同样的正六边形（阴影部分），围成第1圈；在第1圈外面再画出12个同样的正六边形，围成第2圈。按这个方法继续画下去，当画完第10圈时，图中共有多少个与A相同的正六边形？,第一圈有6个正六边形；第二圈有62个正六边形；第三圈有63个正六边形；第n圈有6n个正六边形；所以图中共有1+6（1+2+3+4+5+6+7+8+9+10）=331个正六边形。,练习8,在nn的正方形钉子板上（n是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的线段种数.,练习9,如图，平面内有公共端点的六条射线，从射线OA开始按逆时针方向依次在射线上写出数字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+103的值。,练习12,2000个学生排成一行，依次从左到右编上12000号，然后从左到右按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的人离开队伍，按这个规律如此下去，直至当队伍只剩下一人为止。问：最后留下的这个人原来的号码是多少？,分析:我们通过前几次留在队伍中的学生的编号找出规律。第一次留下的学生编号是：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。,练习13,999999999999的乘积中有多少个数字是奇数？,练习14,n*(n+1)-1,41,练习15,如图1，是棱长为a的小正方体，图2，图3由这样的小正方体摆放而成按照这样的方法继续摆放，自上而下分别叫第一层、第二层、第n层，第n层的小正方体的个数记为sn写出当n=10时，s10=().,55,13610,如图，有边长为1的等边三角形卡片若干张，使用这些三角形卡片拼出边长分别是2，3，4，的等边三角形（如图所示）。根据图形推断，每个等边三角形所用卡片总数sn与边长n之间的关系。,49162536,练习16,Hanoi双塔问题,给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：（1）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。,输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。【样例1】,【样例2】,【限制】对于50%的数据，1=n=25对于100%的数据，1=n=200【提示】设法建立An与An-1的递推关系式。,解题思路:数学归纳+高精度Hanoi单塔的最少移动步数是2n-1，现在有2层，可以将2层看作1层，便回到了单塔的问题上，每移动想象中的“单个”盘子需要两步，故Hanoi双塔=Hanoi单塔*2可得公式：f(n)=2n+1-2高精度只要编个乘法就可以了，不要忘记最后-2,beginassign(input,hanoi.in);assign(output,hanoi.out);reset(input);rewrite(output);readln(n);ppp(n+1);a1:=a1-2i:=100;whileai=0doi:=i-1;forj:=idownto1dowrite(aj);close(input);close(output);end.,varn,i,j:integer;a:array1.100of0.9;procedureppp(k:integer);vari,j,w,s:integer;begina1:=1;初值w:=0;fori:=1tokdoforj:=1to100dobegins:=aj*2+w;aj:=smod10;w:=sdiv10;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项样例: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.,计算正方形、长方形个数,设有一个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,只有一行，两个整数N和M.输出文件1.out,只有一行，为两个整数（中间用空格隔开），分别表示所求的正方形的个数与长方形的个数。样例：输入23输出810,对于棋盘中的任意一个正方形而言，只要确定了左上角的位置和边长后，该正方形就完全确定了因此只要穷举除最下面和最右边之外的每个格点，算出以它们作为正方形的左上角位置时边长不同的正方形个数，然后累加起来就可得到全部正方形的个数同样地也可以类似地算出长方形个数（包括正方形）,0123,01234,va