noip讲义4-递推法课件.ppt

《noip讲义4-递推法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递推法所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。可用递推算法求解的题目一般有以下二个特点：1、问题可以划分成多个状态；2、除初始状态外，其它各个状态都可以用固定的递推关系式来表示。在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。采用具体化、特殊化的方法寻找规律平面上n条直线，任两条不平行，任三条不共点，问这n条直线把这平面划分为多少个部分？设这n条直线把这平面划分成Fn个部分。先用具体化特殊化的方法寻找规律

2、，如图所示，易知的前几项分别为这些数字之间的规律性不很明显，较难用不完全归纳法猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系，因为这些图形中，后一个都是由前一个添加一条直线而得到的，添加一条直线便增加若干个区域。一般地，设原来的符合题意的n-1条直线把这平面分成个区域，再增加一条直线l，就变成n条直线，按题设条件，这l必须与原有的n-1条直线各有一个交点,且这n-1个交点及原有的交点互不重合。这n-1个交点把l划分成n个区间，每个区间把所在的原来区域一分为二，所以就相应比原来另增了n个区域，即：这样，我们就找到了一个从Fn-1到Fn的的递推式，再加上已

3、知的初始值F1=2，就可以通过n-1步可重复的简单运算推导出Fn的值。vara,i,n:longint;beginread(n);a:=2;fori:=2tondoa:=a+i;writeln(a);end.在平面内画五条直线和一个圆，最多能把平面分成多少部分？平面上有8个圆，最多能把平面分成几部分？123456Fn=Fn-1+2×(n-1)圆周上两个点将圆周分为两半，在这两点上写上数1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和，如此继续下去，问第6步后，圆周上所有点上的数之和是多少？分析:先可以

4、采用作图尝试寻找规律。第一步：圆周上有两个点，两个数的和是1+1=2；第二步：圆周上有四个点，四个数的和是1+1+2+2=6；增加数之和恰好是第一步圆周上所有数之和的2倍。第三步：圆周上有八个点，八个数的和是1+1+2+2+3+3+3+3=18，增加数之和恰好是第二步数圆周上所有数之和的2倍。第四步：圆周上有十六个点，十六个数的和1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54，增加数之和恰好是第三步数圆周上所有数之和的2倍。……这样我们可以知道，圆周上所有数之和是前一步圆周上所有数之和的3倍。设An为第n步后得出的圆周上所有数之和，则An=

5、3×An－1在 n×n的正方形钉子板上（n是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的线段种数.Fn=Fn-1+n如图1，是棱长为a的小正方体，图2，图3由这样的小正方体摆放而成。按照这样的方法继续摆放，自上而下分别叫第一层、第二层、……、第n层，第n层的小正方体的个数记为sn。请写出求sn的递推公式。13610…如图，有边长为1的等边三角形卡片若干张，使用这些三角形卡片拼出边长分别是2，3，4，…的等边三角形（如图所示）．根据图形推断，写出求每个等边三角形所用卡片总数sn的递推公式．49162536…为庆祝“五·一”国际劳动节，市政府决定在人

6、民广场上增设一排灯花，其设计由以下图形逐步演变而成，其中圆圈代表灯花中的灯泡，n代表第n次演变过程，s代表第n次演变后的灯泡的个数。仔细观察下列演变过程，当n=6时，s=_____。94Sn=2×sn-1+2Sn=3×sn-1-2×sn-2某公共汽车线路上共有15个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？从表中可以看出车上人数最多是56人，所以车上至少要准备56个座位。练习1将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，

7、可得到７条折痕，那么对折n次，可得到几条折痕？Fn=2*Fn-1+1vara,i,n:longint;beginread(n);a:=1;fori:=2tondoa:=2*a+1;writeln(a);end.varf,s,i,n,j:longint;beginread(n);f:=1;fori:=2tondobegins:=1;forj:=1toi-1dos:=s*2;f:=f+s;end;writeln(f);end.Fn=Fn-1+2n-1var{加入高精度运算}a,b:array[1..100]ofinteger;i,j,n:integer;beginr

8、eadln(n);a[1