资源描述：
《最新noip讲义4递推法课件ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、noip讲义4递推法采用具体化、特殊化的方法寻找规律平面上n条直线，任两条不平行，任三条不共点，问这n条直线把这平面划分为多少个部分？设这n条直线把这平面划分成Fn个部分。先用具体化特殊化的方法寻找规律，如图所示，易知的前几项分别为这些数字之间的规律性不很明显，较难用不完全归纳法猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系，因为这些图形中，后一个都是由前一个添加一条直线而得到的，添加一条直线便增加若干个区域。圆周上两个点将圆周分为两半，在这两点上写上数1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和，如此继续下去，问第6
2、步后，圆周上所有点上的数之和是多少？分析:先可以采用作图尝试寻找规律。第一步：圆周上有两个点，两个数的和是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步后得出的圆周上所有
3、数之和，则An=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…为庆祝“五·一”国际劳动节，市政府决定在人民广场上增设一排
4、灯花，其设计由以下图形逐步演变而成，其中圆圈代表灯花中的灯泡，n代表第n次演变过程，s代表第n次演变后的灯泡的个数。仔细观察下列演变过程，当n=6时，s=_____。94Sn=2×sn-1+2Sn=3×sn-1-2×sn-2某公共汽车线路上共有15个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？从表中可以看出车上人数最多是56人，所以车上至少要准备56个座位。练习1将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到７条折痕，那么对折n次，可得到几条折痕？F
5、n=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;beginreadln(n);a[100]:=1;{n=1时}b[100]:=1;{20=1
6、}fori:=2tondobeginforj:=100downto1dob[j]:=b[j]*2;{递推出2i-1}forj:=100downto2doifb[j]>=10thenbeginb[j-1]:=b[j-1]+b[j]div10;b[j]:=b[j]mod10;end;forj:=100downto1dobegina[j]:=a[j]+b[j];ifa[j]>=10thenbegina[j-1]:=a[j-1]+a[j]div10;a[j]:=a[j]mod10;end;end;end;j:=1;whilea[j]=0doj:=j+1;fori:=jto100dowrite(a[i]
7、);end.练习2如图,第一次把三角形剪去一个角后,图中最多有四个角,第二次再把新产生的角各剪一刀,…,如此下去,每一次都是把新产生的角各剪一刀,则第n次剪好后,图中最多有多少个角?46101834…Fn=Fn-1+2n-1varf,s,i,n,j:longint;beginread(n);f:=4;fori:=2tondobegins:=1;forj:=1toi-1dos:=s*2;f:=f+s
