大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
第一第二的数都是1，后面的数都是前两个数的和。其实也可以用递归实现。
class Solution {public: int Fibonacci(int n) { int f1, f2, f3; f1 = f2 = f3 = 1; if(!n) return 0; for(int i = 3; i <= n; i++) { f3 = f1 + f2; f1 = f2; f2 = f3; } return f3; }}; 二、跳台阶 题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
算法思想其实当前的台阶的跳法就是前面一阶的跳法与前面两阶的跳法之和。递归容易实现些。
class Solution {public: int jumpFloor(int number) { if(number == 1) return 1; if(number == 2) return 2; return jumpFloor(number-1) + jumpFloor(number - 2); }}; 三、变态跳台阶 题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
算法描述这个题要找到青蛙跳上n阶台阶用的次数的规律，一次最多次数是n次，最少是1次。其余次数可以将台阶分段处理计算。例如6阶台阶跳三次就分成三段。次数就为C5 2。将所有次数的跳法相加即为答案。
class Solution {public: int jumpFloorII(int number) { int time = 1;for(int i = 2; i <= number; i++) { time += Ays(i - 1, number - 1) / Ays(i - 1, i - 1); } return time; } long Ays(int i, int n) { long tmp = n; for(int j = n - 1; j > n - i; j--) { tmp *= j; } return tmp; }}; 四、矩阵覆盖 题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
算法思路？？？？待解决，碰巧对了
class Solution {public: int rectCover(int number) { if(!number) return 0;if(number == 1) return 1; if(number == 2) return 2; return rectCover(number - 1) + rectCover(number - 2); }}; 五、二进制中1的个数 题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
算法描述这题就是二进制的操作了，将整数和1进行与操作并向又移位就可以判断出1的个数。重点是负数的补码是原码的反码加1，符号位不变，最重要的是负数的移位操作中负数的符号位1是不会移动的。
class Solution {public: int NumberOf1(int n) { int i = 0; if(n < 0) { n = n ^ INT_MAX + 1; i++; } while(n) { if(n & 1) i++; n = n >> 1; } return i; }}; 六、数值的整数次方 题目描述给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
算法思路这题主要要考虑乘方的一些特殊情况，base=0、exponent=0、exponent<0。exponent大于0就乘就行了。
class Solution {public: double Power(double base, int exponent) { double tmp = 1; int exp = exponent; if(exponent == 0) return 1; if(base == 0) return 0; if(exponent < 0) exp = -exponent; for(int i = 0; i < exp; i++) { tmp *= base; } if(exponent < 0) return 1 / tmp; else return tmp; }};