资源描述：
《归纳法、递推法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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。可以看出，当1，2，3，4，5时，S(n)=n2。现在可以归纳出求前n个奇数的和的一般规律，即S(n)=n2。上面的归纳法是不完全归纳法，因为由它得到的结论不一定对任意的n都成立．要证明对所有的n都成立，就必须使用下面介绍的数学归纳法．1、证明当n取第一个值n0时结论正确。2、假设当n=k时结论成立，证明当n=k+1时结论也成立。证明：１、当n=１
2、时，左边＝１，右边＝１，等式成立。２、假设当n=k时等式成立，即１＋３＋５＋…＋（２k-1)=k2，那么１＋３＋５＋…＋（２k-1）+[2(k+1)-1]=k2+2(k+1)-1=k2+2k+1=(k+1)2例1、Hanoi双塔问题07年复赛试题给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：（1）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务：设An为2n个圆盘完成上述任务所需的
3、最少移动次数，对于输入的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与An-1的递推关系式。解题思路:数学归纳+高精度Hanoi单塔的最少移动步数是2n-1，现在有2层，可以将2层看作1层，便回到了单塔的问题上，每移动想象中的“单个”盘子需要两步，故Hanoi双塔=Hanoi
4、单塔*2可得公式：f(n)=2n+1-2高精度只要编个乘法就可以了，不要忘记最后-2beginassign(input,'hanoi.in');assign(output,'hanoi.out');reset(input);rewrite(output);readln(n);ppp(n+1);ifa[1]>=2thena[1]:=a[1]-2elsebegina[1]:=a[1]+8;a[2]:=a[2]-1;end;i:=100;whilea[i]=0doi:=i-1;forj:=idownto1dowrite(a[j]);close(input);close(output);end.va
5、rn,i,j:integer;a:array[1..100]of0..9;procedureppp(k:integer);vari,j,w,s:integer;begina[1]:=1;w:=0;fori:=1tokdo{循环K次}forj:=1to100dobegins:=a[j]*2+w;a[j]:=smod10;w:=sdiv10;end;end;例2、乘火车(98年复赛试题)火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的
6、人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有n个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问第x站开出时车上的人数是多少？输入文件chc.in：一行四个整数a，n，m和x（中间用空格隔开）输出文件chc.out：一行一个整数（从x站开出时车上的人数）样例:chc.in46324chc.out18分析:典型的数学题为了找规律，我们建立一个表:站号123456开车时人数num[]aa2a2a+b3a+2b4a+4b上车人数in[]aba+ba+2b2a+3b3a+5b
7、下车人数out[]0bba+ba+2b2a+3b规律出来了，设第k(k>=3)站时上车人数为f[k-2]*a+f[k-1]*b(f[k]={1,1,2,3,5,8,13,21..}为fibonacci数列)num[k]=a+in[2]-out[2]+in[3]-out[3]...+in[k]-out[k]而in[2]=out[3],in[3]=out[4]...故num[k]=a-out[2]+in[k]=a
