常用算法笔记 > 递归与分治
递归和分治思想

递归算法:直接或者间接不断反复调用自身来达到解决问题的方法。这就要求原始问题可以分解成相同问题的子问题。

示例:阶乘、斐波纳契数列、汉诺塔问题

 

斐波纳契数列:又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F1=1,F2=1,Fn=F(n-1)+F(n-2)(n>2,n∈N*))。

 

分治算法:待解决复杂的问题能够简化为几个若干个小规模相同的问题,然后逐步划分,达到易于解决的程度。

1、将原问题分解为n个规模较小的子问题,各子问题间独立存在,并且与原问题形式相同

2、递归的解决各个子问题

3、将各个子问题的解合并得到原问题的解

 

示例:棋盘覆盖、找出伪币、求最值

 

棋盘覆盖:在一个(2^k)*(2^k)个方格组成的棋盘上,有一个特殊方格与其他方格不同,称为特殊方格,称这样的棋盘为一个特殊棋盘。要求对棋盘的其余部分用L型方块填满