算法中常用数学知识 _斐波那契数列

想一边学习一边整理，大家有碰到的可以在评论中补充。
1. 斐波那契数列
斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）。在算法中，假如一个复杂的过程中发现存在斐波那契数列式的规律，往往可以考虑用递归解决。

文章插图
2. 简单快速幂
【算法中常用数学知识】

文章插图

文章插图
Java实现代码如下，注意程序的鲁棒性：

```public static double Power(double base,int exponent){double result=1;boolean isPositive;if (exponent==0)return 1;if (exponent>0)isPositive = true;else{isPositive = false;exponent = -exponent;if(base==0)throw new RuntimeException("分母不能为0"); }while(exponent!=0){if((exponent&1)==1){result*=base;}exponent=exponent>>1;base*=base;}return isPositive?result:1/result;}```

3.二叉树相关