跳台阶问题|斐波那契递归的复杂度问题|整数划分问题

86 阅读 0 评论 57 点赞

我是靠谱客的博主过时西牛，这篇文章主要介绍跳台阶问题|斐波那契递归的复杂度问题|整数划分问题，现在分享给大家，希望可以做个参考。

【问题】

台阶一共有N节，一次可以跳1节或者2节，问有多少次跳法？如果一次可以跳1节、2节或者3节呢？

【分析】

定义f(N)为第几节台阶时候的跳法,那么，

N=1时，f(N)=1;
N=2时, f(N)=2;因为有每次跳一步和一次跳两步两种
当N>2时，如果第一次跳1阶，那么要跳到第N节有，需要将剩下的N-1节跳完，f(N-1);如果第一次跳2阶，那么需要将剩下的N-2节跳完，有f(N-2)种跳法，两种起始跳法互斥，所以由f(N)=f(N-1)+f(N-2)

【代码】

复制代码

1
2
3
4
5
6
7
long long fibonacci_soluction(int N)
{
if(N <=2)
return N;
else
return fibonacci_soluction(N-1)+fibonacci_soluction(N-2);
}

同理，若是一次可以跳1阶、2阶或者3阶，那么

f(N)=1 N=1
f(N)=2 N=2
f(N)=4 N=3
f(N)=f(N-1)+f(N-2)+f(N-3) n>3

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
long long fibonacci_soluction2(int N)
{
if(N == 1)
return 1;
if(N == 2)
return 2;
if(N == 3)
return 4;
else
return fibonacci_soluction2(N-1)+fibonacci_soluction2(N-2)+fibonacci_soluction2(N-3);
}

【思考】菲波那切数列时间空间复杂度

转化成斐波那契数列递归求解，貌似是一个漂亮的解法，但是时间O(2^N)和空间复杂度O(N)不敢恭维，改用递推，时间复杂度为O(N),空间复杂度为O(1)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long fibonacci_soluction_rec(int N)
{
if(N <= 2)
return N;
long long a, b, c;
a = 1, b = 2;
int i;
for (int i = 3; i <= N; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}

但这是实现菲波那切数列最优的方法么？参考 http://www.gocalf.com/blog/calc-fibonacci.html

答案：矩阵法是最快的算法，具体推导见上面的链接用python实现的，用C++实现的http://zhedahht.blog.163.com/blog/static/25411174200722991933440/

最终的代码如下：

/* f[n] 1*f[n-1] + 1* f[n-2] 1 1 f[N-1] | 1 1 |^(N-1) f[1]
----- = --------------- = * =*
f[n-1] 1*f[n-1] + 0* f[n-1] 1 0 f[N-2] | 1 0 | f[0]
转变为求1 1 二维矩阵的N-1次幂的形式
1 0
/ an/2*an/2 n为偶数时
an=
a(n-1)/2*a(n-1)/2 n为奇数时
这样只需logN次就行了

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct matrix_2by2
{
matrix_2by2(long long a_00 = 0,	long long a_01 = 0,	long long a_10 = 0, long long a_11 = 0)
:a00(a_00),a01(a_01),a10(a_10),a11(a_11)//为书写方便，给struct一个构造函数
{
}
long long a00;
long long a01;
long long a10;
long long a11;
};
typedef struct matrix_2by2 matrix_2by2;
matrix_2by2 matrix_2by2_multiple(const matrix_2by2 A, const matrix_2by2 B)
{
return matrix_2by2
(
A.a00*B.a00 + A.a01*B.a10,
A.a00*B.a01 + A.a01*B.a11,
A.a10*B.a00 + A.a11*B.a10,
A.a10*B.a01 + A.a11*B.a11
);
}
matrix_2by2 matrix_pow(int N)
{
assert(N > 0);
matrix_2by2 matrix;
if (N == 1)
{
return matrix_2by2(1, 1, 1, 0);
}
if (N % 2 == 0)
matrix = matrix_2by2_multiple(matrix_pow(N/2), matrix_pow(N/2));
if (N % 2 == 1)
{
matrix = matrix_2by2_multiple(matrix_pow((N-1)/2), matrix_pow((N-1)/2));
matrix = matrix_2by2_multiple(matrix, matrix_2by2(1,1,1,0));
}
return matrix;
}
long long matrix_fabonacci(int N)
{
if(N <=2)
return N;
matrix_2by2 res = matrix_pow(N);
return res.a00;
}

【测试代码】

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <time.h>
#include <iostream>
using namespace std;
int main()
{
time_t begin, end;
begin = clock();
fibonacci_soluction_rec(10000000);
end = clock();
cout<<"使用递推fibonacci(100)用时"<<end-begin<<endl;
begin = clock();
matrix_fabonacci(10000000);
end = clock();
cout<<"使用矩阵fibonacci(100)用时"<<end-begin<<endl;
}

不知为什么，我测试的矩阵方法竟然比递归的方法慢了50多倍！有时间在考虑下~~

【思考】当跳的步数不止三个呢，这就转化为整数规划的问题

详细分析见别人的这篇博文：http://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html

复制代码

1
2
3
4
5
6
7
8
9
10
long long equationCount(int n, int m)
{
assert(m >0 && n>0);
if (m==1 || n==1)
return 1;
if (n <= m)
return 1+equationCount(n, n-1);
if (n > m)
return equationCount(n-m, m)+equationCount(n, m-1);
}

当然，对上述递归算法实际中需要进行优化。（完，断断续续写了三天=_=）