本文记录我在学习王道考研教材《数据结构考研复习指导》时，所遇到的各章思考题。仅供参考。
Ch1
题目
求解斐波那契数列
$$
F(n) = \begin{cases}
1, & \text{n = 0,1} \\
F(n-1) + F(n-2), & \text{n > 1}
\end{cases}
$$
有两种常用的算法：递归算法和非递归算法。试分别分析两种算法的时间复杂度。（提示：请结合归纳总结中的两种方法进行解答。）
解答：
两种常用算法：
1.递归算法，时间复杂度为O(2n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<iostream>
using namespace std;
long Fibonacci(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return Fibonacci(n - 1) + Fibonacci(n-2);
}
int main() {
cout << "Enter an integer number:" << endl;
int N;
cin >> N;
cout << Fibonacci(N) << endl;
system("pause");
return 0;
}
|
2.非递归算法，时间复杂度为O(n)
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
| #include<iostream>
using namespace std;
long Fibonacci(int n) {
if (n <= 2)
return 1;
else {
long num1 = 1;
long num2 = 1;
for (int i = 2;i < n - 1;i++) {
num2 = num1 + num2;
num1 = num2 - num1;
}
return num1 + num2;
}
}
int main() {
cout << "Enter an integer number:" << endl;
int N;
cin >> N;
cout << Fibonacci(N) << endl;
system("pause");
return 0;
}
|
参考博客
斐波那契数列两种算法的时间复杂度
3种方法求解斐波那契数列
三种时间复杂度算法求解斐波那契数列
Ch2