第七篇博客——递归与分治
递归策略
汉诺塔
在普通的汉诺塔中func(n)=2*func(n-1)+1,但是如果只允许一次只能移到相邻的杆子上只能func(n)=3*func(n-1)+1
分治法
将问题分解成数个小问题,分别解决多个小问题然后再将其相加起来就可以获得总共的结果。
斐波那契数列
int fibonacci(int n){ if(n==1||n==0) return 0; else return fibonacci(n-1)+fibonacci(n-2); }
在普通的汉诺塔中func(n)=2*func(n-1)+1,但是如果只允许一次只能移到相邻的杆子上只能func(n)=3*func(n-1)+1
将问题分解成数个小问题,分别解决多个小问题然后再将其相加起来就可以获得总共的结果。
int fibonacci(int n){ if(n==1||n==0) return 0; else return fibonacci(n-1)+fibonacci(n-2); }