JC2:递推,递归与分治

递推,递归与分治[待完成]

递推的定义

定义:已知初始值F1,通过递推关系式Fn=g(Fn-1)求出最终结果Fn的递推方式称为顺推法;同理,把已知最终结果为Fn,通过递推关系式Fn-1=g'(Fn)求出初始值F1的递推方式称为倒推法。

模板:

f[0]=0; f[1]=1;

for(int i=1; i<=n; i++) f[i]=f[i-1]+f[i-2];

具体步骤

找到初始状态 找到递推公式 开始循环算

经典问题

抽屉原理 加法原理 乘法原理 容斥原理 卡特兰数

递归

递归算法

设一个未知函数f,用其自身构成的已知函数g来定义:

f(n)=g(n,f(n-1)) n>0

f(0)=a n=0

描述递归定义的函数或求解递归问题的过程称为递归算法

JC2:递推,递归与分治

相关推荐