《基本算法2-递推法实例》由会员分享，可在线阅读，更多相关《基本算法2-递推法实例（86页珍藏版）》请在金锄头文库上搜索。
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的的递推式，再加上已知的初始值F1=2，就可以通过n-
3、1步可重复的简单运算推导出Fn的值。,var a,i,n:longint; begin read(n); a:=2; for i:=2 to n do a:=a+i; writeln(a); end.,在平面内画五条直线和一个圆，最多能把平面分成多少部分？,平面上有8个圆，最多能把平面分成几部分？,1,2,3,4,5,6,Fn=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=3An1,在 nn的正方形钉子板上（n是
5、钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的线段种数.,Fn=Fn-1+n,如图1，是棱长为a的小正方体，图2，图3由这样的小正方体摆放而成。按照这样的方法继续摆放，自上而下分别叫第一层、第二层、第n层，第n层的小正方体的个数记为sn。请写出求sn的递推公式。,1 3 6 10,如图，有边长为1的等边三角形卡片若干张，使用这些三角形卡片拼出边长分别是2，3，4，的等边三角形（如图所示）根据图形推断，写出求每个等边三角形所用卡片总数sn的递推公式,4 9 16 25 36,为庆祝“五一”国际劳动节，市政府决定在人民广场上增设一排灯花，其设计由以下图形逐步演变而成，其中圆圈代表灯花
6、中的灯泡，n代表第n次演变过程，s代表第n次演变后的灯泡的个数。仔细观察下列演变过程，当n=6时，s=_。,94,Sn=2sn-1+2,Sn=3sn-1-2sn-2,某公共汽车线路上共有15个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？,从表中可以看出车上人数最多是56人，所以车上至少要准备56个座位。,练习1,将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到条折痕，那么对折n次，可得到几条折痕？,Fn=2*Fn-1+1,var a,i,n:longi
7、nt; begin read(n); a:=1; for i:=2 to n do a:=2*a+1; writeln(a); end.,var f,s,i,n,j:longint; begin read(n); f:=1; for i:=2 to n do begin s:=1; for j:=1 to i-1 do s:=s*2; f:=f+s; end; writeln(f); end.,Fn=Fn-1+2n-1,var加入高精度运算 a,b:array1100 of integer; i,j,n:integer; begin readln(n); a100:=1 ;n=1时 b100:
8、=1;20=1 for i:= 2 to n do begin for j:= 100 downto 1 do bj:=bj*2;递推出2i-1 for j:= 100 downto 2 do if bj=10 then begin bj-1:=bj-1+bj div 10 ; bj:=bj mod 10; end; for j:= 100 downto 1 do begin aj:=aj+bj; if aj=10 then begin aj-1:=aj-1+aj div 10 ; aj:=aj mod 10; end; end; end; j:=1; while aj=0 do j:=j+1
9、; for i:= j to 100 do write(ai) ; end.,练习2,如图,第一次把三角形剪去一个角后,图中最多有四个角,第二次再把新产生的角各剪一刀,如此下去,每一次都是把新产生的角各剪一刀,则第n次剪好后,图中最多有多少个角?,4 6 10 18 34,Fn=Fn-1+2n-1,var f,s,i,n,j:longint; begin read(n); f:=4; for i:=2 to n do begin s:=1; for j:=1 to i-1 do s:=s*2; f:=f+s; end; writeln(f); end.,var a,b:array1100 of
10、 longint; i,j,n:longint; begin readln(n); a100:=4 ; b100:=1; for i:= 2 to n do begin for j:= 100 downto 1 do bj:=bj*2; for j:= 100 downto 2 do if bj=10 then begin bj-1:=bj-1+bj div 10 ; bj:=bj mod 10; end; for j:= 100 downto 1 do begin aj:=aj+bj; if aj=10 then begin aj-1:=aj-1+aj div 10 ; aj:=aj mod
11、 10; end; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 100 do write(ai) ; end.,练习3,下图中把大正方形各边平均分成了5份，此时有55个正方形。如果把正方形各边平均分成n份，那么得到的正方形总数为多少？,52+42+32+22+12=55,n2+(n-1)2+(n-2)2+22+1,Fn=Fn-1+n2,var a,i,n:longint; begin read(n); a:=1; for i:=2 to n do a:=a+i*i; writeln(a); end.,Var 加入高精度运算 a:arra
12、y125 of longint; i,j,k,x,n:longint; begin readln(n); a25:=1;n=1时 for i:= 2 to n do begin x:=i*i; for j:= 25 downto 1 do begin aj:=aj+x mod 10; if aj=10 then begin aj:=aj-10 ; aj-1:=aj-1+1; end; x:=x div 10; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 25 do write(ai); end.,练习4,如图，由等圆组成的一组图中，第1
13、个图由1个圆组成，第2个图由7个圆组成，第3个图由19个圆组成，按照这样的规律排列下去，则第9个图形由_个圆组成。,217,可得递推公式: Fn= Fn-1+6*（n1）,var a,i,n:longint; begin read(n); a:=1; for i:=2 to n do a:=a+6*(i-1); writeln(a); end.,var 加入高精度运算 a:array150 of longint; i,j,k,x,n:longint; begin readln(n); a50:=1; for i:= 2 to n do begin x:=(i-1)*6; for j:= 50
14、downto 1 do begin x:=x+aj; aj:=x mod 10 ; x:=x div 10; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 50 do write(ai); end.,练习5,已知三角形ABC的面积为10，延长边BC到点D，使BC=CD，延长边CA到点E，使CA=AE，延长边AB到点F，使AB=BF，连结DE,EF,FD,得到三角形DEF,并记图中阴影部分面积为S1,此时我们称三角形ABC向外扩展了一次.求经过N次扩展后图中阴影部分的面积Sn.,Fn=7*Fn-1 ( Fn为第n次扩展后整个三角形的面积 )
15、 F0=10 Sn=Fn-Fn-1,const max=100; var f1,f2,s:array1max of longint; i,j,k,l,n:longint; begin readln(n); f1max:=0 ; f1max-1:=1; F0=10 for i:= 1 to n do begin f2:=f1; k:=0; 7 for j:= max downto 1 do begin k:=k+f1j*7; f1j:=k mod 10; k:=k div 10; end; end;,for i:= max downto 1 do 相减 begin if f1if2i then begin f1i:=f1i+10; f1i-1:=f1i-1-1; end; si:=f1i-f2i; end; j:=1; while sj=0 do j:=j+1; for i:= j to max do write(si) ; end.,Hanoi双塔问题,给定A、B、C三根足够长的细柱，在A柱上放有2n个中 间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将
