华南理工大学计算机全英班的算法设计实验
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
本课程为华南理工大学计算机全英班开设，专注于培养学生的算法设计与分析能力。通过实践项目和编程实验，学生能够深入理解并应用各种经典及现代算法解决实际问题。
### 实验1 快速排序算法
#### 1. 引言：快速排序算法介绍
为了对输入数据序列S进行排序，可以按照以下步骤操作：
- 首先选择一个数q，并将序列S划分为三个子序列：所有元素小于q的子序列S1；所有元素等于q的子序列S2；以及所有元素大于q的子序列S3；
- 然后对S1和S3分别使用相同的算法进行递归排序。
#### 2. 实验目的
（1）学习各种排序算法。
（2）理解快速排序与其他排序算法，如插入排序、直接选择排序等之间的区别。
（3）利用高级语言在计算机上模拟这些算法。
（4）用不同的排序方法解决一些实际的排序问题。
#### 3. 实验内容摘要
使用QuickSort算法对由random()函数生成的含有n个元素的数组S进行排序。将结果与插入排序、直接选择等其他排序算法的结果相比较，理解它们之间的差异，并了解在解决问题时如何选择更好的排序方法。
#### 4. 实验要求
（1）程序模板应适用于所有数据类型，如整型、实数和双精度浮点数等。
（2）采用面向对象编程(OOP)的方法编写代码；
（3）将结果与其他算法的结果进行比较，并绘制图表以显示它们之间的差异。
#### 5. 示例C++代码
```cpp
void myquicksort(int* A, int l,int r){
if(l>=r) return ;
int i=l,j=r;
int temp; //用于分割A成S1,S2和S3
//在此处将S分为S1，S2和S3
myquicksort(A,l,i-1); //递归调用左侧部分
myquicksort(A,i+1,r); //递归调用右侧部分
}
```
### 实验2 背包问题的贪心算法求解
#### 引言：贪心算法介绍
（1）假设一个问题可以通过一系列决策来解决。
（2）每次选择局部最优的选择，这些局部最优的选择最终会累积成全局最优解决方案。
#### 2. 实验目的
（1）了解背包问题和0/1背包问题；
（2）学习什么是贪婪选择策略以及如何使用它解决问题；
（3）掌握用贪心算法解决一些优化问题的方法；
（4）将贪心算法与如树搜索等其他方法进行比较。
#### 3. 实验内容
给定一个容量为M的背包和一系列具有重量和收益的商品，尝试使用贪婪法和搜索树法来解决问题。然后将其结果与其他解决方案（例如0/1背包问题）基于相同容量的结果进行对比。
- 给出实例：
- M = 30,
- (P1, P2, P3, P4, P5, P6) = (25, 24, 15, 18, 22, 35)
- (W1, W2, W3, W4, W5, W6) = (12，15，10，8，9，11)
#### 实验要求
（1）程序模板应适用于所有数据类型。
（2）采用面向对象编程的方法编写代码；
（3）使用贪婪方法和搜索树法解决问题，并比较结果。
### 实验3 Prim算法求最小生成树
#### 引言：Prim算法介绍
- 定义：
- G = (V, E) 是一个加权的连通无向图
- 生成树是 S = (V, T)，T ⊆ E，即无向树。
- 最小生成树(MST)是指具有最小总权重的生成树。
- Prim算法步骤：
1. x ∈ V, 让 A = {x}, B = V - {x}.
2. 从A和B间选择边(u,v)∈E使得其权值最轻。
3. 将 (u, v) 加入到树中。更新集合：A = A ∪{v}，B = B - {v}
4. 如果B为空，则停止；否则转至步骤2。
#### 2. 实验目的
（1）理解最小生成树(MST);
（2）学习求解MST的算法，如Prim和Kruskal等；
（3）比较这些不同算法之间的差异。
### 实验4 树搜索算法
#### 引言：树搜索算法介绍
许多问题可以通过树的形式来表示其解决方案，并通过遍历此树找到该问题的答案。
2. 实验目的
（1）理解树搜索方法。
（2）了解某些
全部评论 (0)
