算法题

1、递归与分治

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

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

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

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

• 1、将原问题分解为n个规模较小的子问题，各子问题间独立存在，并且与原问题形式相同
• 2、递归的解决各个子问题
• 3、将各个子问题的解合并得到原问题的解