基本算法2-递推法实例
86页1、递推法,所谓递推,是指从已知的初始条件出发,依据某种递推关系,逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简后确定。 可用递推算法求解的题目一般有以下二个特点: 1、问题可以划分成多个状态; 2、除初始状态外,其它各个状态都可以用固定的递推关系式来表示。 在我们实际解题中,题目不会直接给出递推关系式,而是需要通过分析各种状态,找出递推关系式。,采用具体化、特殊化的方法寻找规律,平面上n条直线,任两条不平行,任三条不共点,问这n条直线把这平面划分为多少个部分?,设这n条直线把这平面划分成Fn个部分。 先用具体化特殊化的方法寻找规律,如图所示,易知的前几项分别为,这些数字之间的规律性不很明显, 较难用不完全归纳法猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系,因为这些图形中,后一个都是由前一个添加一条直线而得到的,添加一条直线便增加若干个区域。,一般地,设原来的符合题意的n-1条直线把这平面分成 个区域,再增加一条直线l,就变成n条直线,按题设条件,这l必须与原有的n-1条直线各有一个交点, 且这n-1个交点及原有的交点互不重合
2、。这n-1个交点把l划分成n个区间,每个区间把所在的原来区域一分为二,所以就相应比原来另增了n个区域,即: 这样,我们就找到了一个从Fn-1到Fn的的递推式,再加上已知的初始值F1=2,就可以通过n-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步后,圆周上所有点上的数之和是多少?,分析:先可以采用作图尝试寻找规律。,第一步:圆周上有两个点,两个数的和是1+1=2; 第二步:圆周上有四个点,四个数的和是1+1+2+2=6;增加数之和恰好是第一步圆周上所有数之和的2倍。 第三步:圆周上有八个点,八个数的和是1+
3、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是钉子板每边上的钉子数),求连接任意两个钉子所得到的不同长度的线段种数.,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,为庆祝“五一”国际劳动节,市政府决定在人民广场上增设一排灯花,其设计由以下图形逐步演变而成,其中圆圈代表灯花
4、中的灯泡,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:longint; 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.,F
《基本算法2-递推法实例》由会员小**分享,可在线阅读,更多相关《基本算法2-递推法实例》请在金锄头文库上搜索。
2020年高考真题——理科综合(全国卷Ⅲ)+Word版含答案
2021年绝味鸭脖策划书
2021年熟食店创业方案
2021年熟食店开店策划
2021年卤菜店创业计划书
2021年周黑鸭网络营销策划方案
东大21年1月考试《现代设计方法》考核作业
谈我国行政管理效率的现状及其改观对策(论文)
单证员考试-备考辅导-复习资料:无贸易背景信用证案分析.docx
土木工程毕业生答辩自述.docx
建筑学毕业后工作状态真实写照.doc
C#代码规范(湖南大学).doc
xx区食药监局2019年工作总结及2020年工作计划
2019年中医院药物维持治疗门诊工人先锋号先进事迹
2019年度xx乡镇林长制工作总结
2019年性艾科工作计划书
2019年人才服务局全国扶贫日活动开展情况总结
关于组工信息选题的几点思考
摘了穷帽子 有了新模样
2019年某集团公司基层党支部书记培训班心得体会
2024-01-31 15页
2024-01-31 21页
2024-01-31 37页
2024-01-31 30页
2024-01-31 22页
2024-01-31 48页
2024-01-31 32页
2024-01-31 40页
2024-01-31 31页
2024-01-31 20页