斐波那契数列是在学编程期间最先接触的到的知识，也是思维拓展比较多的一个知识点，很重要。
我的理解
斐波那契数列，常用的有递归，但是对于数据大的数字，那么它的运行时间便比较长，因为是大O了。所以要用平常的for循环的方式进行传统的赋值，这个样子是O(n)。
这里写的都是比较简单的题目，内部也有很深的东西可以探索。
第一题：斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
对于这个题，一开始老师讲的是结合递归，最经典的应该就是兔子生一窝兔子的题。但是，递归对于时间消耗很大。
递归写的
int Fibonacci1(int n) {
if (n <= 2 && n > 0) {
return 1;
}else if(n == 0){
return 0;
}else{
return Fibonacci1(n-1)+Fibonacci1(n-2);
}
}
普通思路for循环写的
int Fibonacci(int n) {
int a1 = 0, a2 = 1;
if (n == 0) {
return 0;
}else if(n == 1){
return 1;
}else{
for (int i = 1; i < n; i++) {
int temp = a2 + a1;
a1 = a2;
a2 = temp;
}
return a2;
}
}
第二题：跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
1阶——1种 1
2阶——2种 1 2
3阶——3种 111 12 21
4阶——5种 1111 112 211 22
5阶——8种 11111 1112 1211 2111 1121 122 212 221
在这里就不写公式了，很好就推出来了。
递归
int jumpFloor1(int number) {
if(number == 1){
return 1;
}else if (number == 2){
return 2;
}else{
return jumpFloor1(number-1)+jumpFloor1(number-2);
}
}
for循环
int jumpFloor(int number) {
int a1 = 1;
int a2 = 2;
if(number == 1){
return 1;
}else if (number == 2){
return 2;
}else{
for (int i = 2; i < number; i++) {
int temp = a1+a2;
a1 = a2;
a2 = temp;
}
return a2;
}
}
第三题：变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
1阶——1种 1
2阶——2种 11 2
3阶——4种 111 12 21
4阶——8种 1111 112 121 211 22 31 13 4
5阶——16种 11111 11112 1121 1211 2111 122 212 221 32 23 41 14 5
递归
int jumpFloorII1(int number) {
int a1 = 0, a2 = 1;
if (number == 0) {
return a1;
}else if (number == 1){
return a2;
}else{
return jumpFloorII1(number-1)*2;
}
}
for循环
int jumpFloorII(int number) {
int a1 = 0, a2 = 1;
if (number == 0) {
return a1;
}else if (number == 1){
return a2;
}else{
for (int i = 1; i < number; i++) {
int temp = a2*2;
a2 = temp;
}
return a2;
}
}
这里还有一个发散思维，就是利用二进制，通过左位移来做
int jumpFloorII2(int number) {
return 1<<--number;
}
举例说明
例如给的值是3，运算符顺序是先--然后<<。
所以：1二进制是0001，左位移2，就是低位左移2位，为0100，值为十进制的4。
同理来个5，0001，左位移4，为0001 0000，算一算，是0，2，4，8，16，高位为1，换算成10进制为16，正确。。。
