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
描述递归定义的函数或求解递归问题的过程称为递归算法
相关推荐
steeven 2020-11-10
Tips 2020-10-14
nongfusanquan0 2020-08-18
yedaoxiaodi 2020-07-26
清溪算法君老号 2020-06-27
pengkingli 2020-06-25
yishujixiaoxiao 2020-06-25
清溪算法 2020-06-21
RememberMePlease 2020-06-17
nurvnurv 2020-06-05
SystemArchitect 2020-06-02
码墨 2020-05-29
清溪算法 2020-05-27
choupiaoyi 2020-05-27
清溪算法 2020-05-25
bluewelkin 2020-05-19
dbhllnr 2020-05-15
steeven 2020-05-09
baike 2020-05-09