递推算法Python＆C＋

今天学习到了递推算法，下面是我对递推算法的知识总结，包含一些例题及分析，语言使用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