需求

  • 编程实现斐波那契数列，分别用递归法，数组法。比较实验结果，分析原因。

  • 设计空间复杂度更好的算法，实现斐波那契数列。

  • 编程实现汉诺塔问题
  • 全排列问题（选做）

实现

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<time.h>
using namespace std;
int cnt = 0;//统计循环次数

int fun1(int n ) {
	cnt++;
	if (n == 1) return 1;
	if (n == 2) return 1;
	return fun1(n - 1) + fun1(n - 2);
}

void main() {
	cout <<"fun1(25): "<< fun1(25) << endl;
	cout <<"循环次数: " << cnt << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<time.h>
using namespace std;
int cnt2 = 0;//统计循环次数

int fun2(int n) {
	int *arr;
	arr = new int[n];
	arr[1] = 1;
	arr[2] = 1;
	for (int i = 3; i <=n; i++) {
		arr[i] = arr[i - 2] + arr[i - 1];
		cnt2++;
	}
	return arr[n];
}

void main() {
    
	cout << "fun2(25): " << fun2(25) << endl;
	cout << "循环次数: " << cnt2 << endl;
}
  • fun1递归算法

img

  • fun2数组法

img

  • 结论：数组法大大降低了时间复杂度，但利用了数组，提高了空间复杂度，典型的空间换取时间
  • 因为我们在数组法中其实只要用到arr[n-1]和arr[n-2]，所以我们可以迭代的方式来降低空间数组法的复杂，同时不提高时间复杂度

img

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>
#include<time.h>
using namespace std;
int cnt3 = 0;//统计循环次数

int fun3(int n) {
	int s1, s2;
	s1 = 1;
	s2 = 1;

	if (n == 1 || n == 2) return 1;

	for (int i = 3; i <= n; i++) {
		cnt3++;
		s2 = s1 + s2;
		s1 = s2 - s1;
	}
	return s2;
}

void main() {
    
	cout << "fun3(25): " << fun3(25) << endl;
	cout << "循环次数: " << cnt3 << endl;
}

汉诺塔问题

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
#include<iostream>
using namespace std;


void move(char a, char b) {
	cout << a << "移动到" << b << endl;
}


void hanoi(int n, char a, char b, char c) {
	if (n <= 0) return;

	hanoi(n - 1, a, c, b);
	move(a, b);
	hanoi(n-1,c, b, a);
}


int main() {
	int n;
	cout << "输入初始盘子数：";
	cin >> n;
	cout << "\n模拟过程：" << endl;
	hanoi(n, 'A', 'B', 'C');

	return 0;
}

image-20220427021651899

全排列问题

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
#include<iostream>
using namespace std;
const int N = 100000;
int arr[N],isUse[N];
int n, k;
void dfs(int k) {
	if (k == n) {
		for (int i = 0; i < n; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (!isUse[i]) {
			arr[k] = i;
			isUse[i] = 1;
			dfs(k + 1);
			isUse[i] = 0;
		}
	}

}

int main() {
	cout << "请输入数组个数: ";
	cin >> n;
	dfs(0);
	return 0;
}

image-20220427024928699