今天学习到了递推算法,下面是我对递推算法的知识总结,包含一些例题及分析,语言使用C++和Python,但掌握算法精髓后用其他语言也可以实现
递推算法
从已知的初始条件出发,依据某种递推关系,逐次推出所要求的各中间结果及最后结果
一般能用递推算法求解的题目具有如下特点:
问题可以划分成多个状态
除初始状态外,其他各状态均可用固定推导关系式来表示的特点
递推的两种形式:
顺推法:由条件推出结果
逆推法:由结果推出条件
递推关系式
简单来说就是定义中的“某种递推关系”的数学公式,这一点在下面的实例中有所体现
解决递推问题的一般步骤
1.建立递推关系式2.确定边界条件3.递推求解
实例:斐波那契数列
问题:一个数列的第0项为1,第一项为1,以后每一项都是前两项的和,求斐波那契数列第n项
分析:在计算斐波那契数列的每一项时都可以有前两项推出,可得递推关系式Fn=G(Fn-1,Fn-2)从初始条件开始,按照关系式递推,求出结果
C++代码
Python代码
另一个实例:题目数量
N名同学争做计算题,规定做完一道才能做第二道,比赛后统计发现:第一位同学做了总数的一半多1道,第二位同学做了余下的一半多2道,第三位同学做了再余下的一半多3道,以此类推,第N-1位同学做了余下的一半多N-1道,最后一位同学做了N道,求题目总数
分析:第N位同学数量为做时题目剩余数量为N第N-1位为(N+N-1)*2N-2位为((N+N-1)*2+N-2)*2由此可得边界条件为F1=N关系式为Fn-1=(Fn+N-1)*2
C++代码
Python代码
其实递推算法和昨天的递归算法还是有很大的相似之处的,算法的本质都在于一步步地推导,而解决问题的根本就在于理解题目,并找出其中的联系
That's all~~~
PS:本来还想再写一些题目的,但时间已经不早了,而我明天还有一整天的课,所以。。。就这样吧
PPS:明天继续[奋斗][奋斗]
Smart的小程序:
小编Smart
领取专属 10元无门槛券
私享最新 技术干货