算法设计与分析实验报告c++实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)
实验任务1、排序算法目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现8种）并分析算法的时间复杂度。比较各种算法的优劣。2、三壶谜题：有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。3、交替放置的碟子我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…现在要
一、实验目的
1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、排序算法
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现8种）并分析算法的时间复杂度。比较各种算法的优劣。
2、三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
3、交替放置的碟子
我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。
4、带锁的门：
在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？
三、实验设备及编程开发工具
实验设备：Win10电脑
开发工具：Dev-C++
四、 实验过程设计（算法思路及描述，代码设计）
1. 选择排序
- 描述： 一种简单直观的排序算法。它的工作原理是：每次找出第 i 小的元素（也就是 A_{i…n} 中最小的元素）然后将这个元素与数组第 i 个位置上的元素交换。
- 代码实现:
void selection_sort(int* a, int n) {
for (int i = 0; i < n-1; ++i) {
int index = i;
for (int j = i + 1; j < n; ++j)
if (a[index] > a[j])
index = j;
std::swap(a[i], a[index]);
}
}
2. 冒泡排序
- 描述： 一种简单的排序算法。它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序
- 代码实现:
void bubble_sort(int* a, int n) {
bool flag = true; // 用于判断当前轮是否有序
int k = 1;
while (flag) {
flag = false;
for (int i = 0; i < n-1; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
std::swap(a[i], a[i+1]);
}
}
}
}
3. 插入排序
- 描述： 一种简单直观的排序算法。它的工作原理是将待排列元素划分为「已排序」和「未排序」两部分每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置与打扑克类似
- 代码实现:
void insertion_sort(int* a, int n) {
for (int i = 1; i < n; ++i) {
int key = a[i];
int index = i - 1;
while (index >= 0 && a[index] > key) {
a[index + 1] = a[index];
index--;
}
a[index + 1] = key;
}
}
4. 折半插入排序
- 描述：通过二分算法优化性能，在排序元素数量较多时优化的效果比较明显。通过二分查找插入位置
- 代码实现：
void insertion_binary_sort(int* a, int n) {
if (n < 2) return;
for (int i = 1; i < n; ++i) {
int key = a[i];
int index = std::upper_bound(a, a + i, key) - a;
// 使用 std::copy_backward 移动元素
std::copy_backward(a + index, a + i, a + i + 1);
a[index] = key;
}
}
5. 计数排序
- 描述：使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数然后根据数组 C 来将 A 中的元素排到正确的位置。1.计算每个数出现了几次； 2.求出每个数出现次数的 前缀和； 3.利用出现次数的前缀和，从右至左计算每个数的排名。
- 代码实现：
void counting_sort(int* a, int n) {
int w = 0;
for (int i = 0; i < n; ++i) w = max(w, a[i]);
int cnt[w];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i) ++cnt[a[i]];
int j = 0;
for (int i = 0; i < w; i++)
while (cnt[i]--) a[j++] = i;
}
6. 快速排序
- 描述：工作原理是通过 分治 的方式来将一个数组排序。1.将数列划分为两部分（要求保证相对大小关系）； 2.递归到两个子序列中分别进行快速排序； 3.不用合并，因为此时数列已经完全有序。
- 代码实现：
void quick_sort(int* a, int l, int r) {
int i = l, j = r, tmp = a[l];
if(i > j) return;
while(i != j) {
while(a[j] >= tmp && j > i) j--;
while(a[i] <= tmp && j > i) i++;
if(j > i) std::swap(a[i], a[j]);
}
a[l] = a[i];
a[i] = tmp;
quick_sort(a, l, i-1);
quick_sort(a, i+1, r);
}
7. 归并排序
- 描述：归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）就要作为最小值放入 c[k]。
- 代码实现：
void merge(int *a, int * tmp, int l, int mid, int r) {
int i = l, j = mid+1, k = l;
while(i!=mid+1 && j!=r+1) {
if(a[i] > a[j]) tmp[k++] = a[j++];
else tmp[k++] = a[i++];
}
while(i != mid+1) tmp[k++] = a[i++];
while(j != r+1) tmp[k++] = a[j++];
for(i=l; i<=r; i++) a[i] = tmp[i];
}
void merge_sort(int* a, int* tmp, int l, int r) {
int mid;
if(l < r){
mid = l + (r-l) / 2;
merge_sort(a, tmp, l, mid);
merge_sort(a, tmp, mid+1, r);
merge(a, tmp, l, mid, r);
}
}
8. 堆排序
- 描述：首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；以此类推，在第 n-1 次操作后，整个数组就完成了排序。
- 代码实现：
void sift_down(int *a, int start, int end) {
int parent = start;
int child = parent * 2 + 1;
while (child <= end) {
if (child + 1 <= end && a[child] < a[child + 1]) child++;
if (a[parent] >= a[child]) return;
else {
std::swap(a[parent], a[child]);
parent = child;
child = parent * 2 + 1;
}
}
}
void heap_sort(int a[], int n) {
for (int i = (n - 1 - 1) / 2; i >= 0; i--) sift_down(a, i, n - 1);
for (int i = n - 1; i > 0; i--) {
swap(a[0], a[i]);
sift_down(a, 0, i - 1);
}
}
9. 三壶谜题
1、算法分析：
可以把每次三个水壶中水量设成一组状态，比如初始状态为008，对应第一个水壶0品脱水，第二个水壶0品脱水，第三个水壶8品脱水。对题目的状态空间图进行广度优先遍历。当表示状态的数字中出现4时，即求出答案。
（1）打印倒水的过程，需要声明一个前置状态保存当前状态由哪个状态转换而来，然后就可以回溯到初始状态，打印出倒水过程。
（2）声明一个map表，保存已有的状态，对已有的状态就不再向下继续遍历。
（3）因为是广度优先遍历，所以第一次得到的答案所需的倒水次数最少，即为最优解。
2、代码实现：
#include <iostream>
#include <vector>
#include <map>
#define MaxFirst 3
#define MaxSecond 5
#define MaxThird 8
using namespace std;
class State
{
public:
int second;
int num[3];
State* preState;
static map<int,int> mapping;
public:
State(int first,int second,int third)
{
num[0]=first;
num[1]=second;
num[2]=third;
}
void init()
{
mapping[0]=MaxFirst;
mapping[1]=MaxSecond;
mapping[2]=MaxThird;
}
bool canPour(int from,int to)//判断是否可以从from水壶中倒水到to水壶中
{
if(num[from]==0) return false;
if(num[to]==mapping[to]) return false;
else return true;
}
void pour(int from,int to)//倒水过程
{
if(num[from]+num[to]>mapping[to])
{
num[from]=num[from]-(mapping[to]-num[to]);
num[to]=mapping[to];
}
else
{
num[to]=num[to]+num[from];
num[from]=0;
}
}
};
map<int,int> State::mapping;
int main()
{
map<int,int> states;
State *start=new State(0,0,8);
start->init();
State *state=start;
State *endState=new State(8,8,8); //只有获得解endState才会改变，赋值全为8为了方便判断是否获得最终解
vector<State> action; //保存所有状态对象
action.push_back(*start); //把初始状态先加入队列中
int n=0;
do{
for(int i=0;i<3;i++) //双层循环为从i水壶中倒水入j水壶中
{
for(int j=0;j<3;j++)
{
if(i!=j)
{
if(state->canPour(i,j))
{
state->pour(i,j);
if(states[state->num[0]*100+state->num[1]*10+state->num[2]]==0)//如果该状态不在hash表中，即为第一次出现该状态
{
states[state->num[0]*100+state->num[1]*10+state->num[2]]++;
(state->preState)=new State(action[n]);
action.push_back(*state);
if(state->num[0]==4||state->num[1]==4||state->num[2]==4)//获得解
{
endState=state;
i=4;
break;
}
}
}
}
*state=action[n];
}
}
n++;
}while(endState->num[0]==8&&endState->num[1]==8&& n<action.size());
cout<<endState->num[0]<<" "<<endState->num[1]<<" "<<endState->num[2]<<endl;
state=endState;
do
{
state=state->preState;
cout<<state->num[0]<<" "<<state->num[1]<<" "<<state->num[2]<<endl;
}while(state->num[2]!=8);
return 0;
10. 交替放置的碟子
1、算法分析：
将问题进行转化：用1表示黑碟子，0表示白碟子，那么目前的顺序是：1010…1010，结果要求1均放在右边，0放在左边。分析题意，算法思路符合冒泡排序算法：对于2n个碟子，可以使用n次迭代完成，交换的次数为：n+(n-1)+…+2+1，即n(n+1)/2。
2、代码实现：
#include<iostream>
using namespace std;
int bubble_sort(int* a, int n) {
int count = 0;
bool flag = true; // 用于判断当前轮是否有序
int k = 1;
while (flag) {
flag = false;
for (int i = 0; i < n-1; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
std::swap(a[i], a[i+1]);
count++;
}
}
}
return count;
}
int main(){
int saucerNumber;
//输入 数量为 2n 的一排碟子，n 黑 n 白交替放置
cout<<"请输入输入碟子的总数量: ";
cin>> saucerNumber;
cout<<endl;
//定义一个数组,用来存储数据
int saucerArray[saucerNumber];
int count=0; // 记录算法需要执行的换位次数。
// 数组赋值------n 黑 n 白交替放置：黑、白、黑、白、黑、......
for(int i=0;i<saucerNumber-1;i+=2){
saucerArray[i]=1;
saucerArray[i+1]=0;
}
//显示未排序之前的数组元素
cout<<"排序之前的数组元素显示如下:" <<endl;
for(int i=0;i<saucerNumber;i++)
cout<<saucerArray[i]<<" ";
cout<<endl;
//通过互换相邻碟子的位置来实现 黑碟子都放在右边，白碟子都放在左边
//方法思路 (相邻元素为一组,然后分组操作元素互换) ---这个方法的时间复杂度不简便
count = bubble_sort(saucerArray, saucerNumber);
cout<<"排序之后的数组元素显示如下:" <<endl;
for(int i=0;i<saucerNumber;i++)
cout<<saucerArray[i]<<" ";
cout<<endl;
cout<<"需要执行的换位次数为: "<<count<<"次!"<<endl;
return 0;
}
11. 带锁的门
1、算法分析：
从1-n的所有门，要经过n次：经过K次，若k（k<=n）可分解为i*j（i！=j），则第k个门一定会有偶数次开关门的变化，则最后门的状态还是关闭。如k = 18，可以分解成1x18，2x9，3x6，则第1次，2次，3次，6次，9次，18次经过第18号门，均会变化开关门的状态，原来是关门，经过偶数次变化，最终状态还是关门；若k为完全平方数，如1、4、9、16，则第k个门只会有奇数次变化。如k=4，只有1、2、4次经过会变化状态，故最后门是开的。按照如上的分析，我们只需要判断1-n个门中有多少个完全平方数，即可确定门开着的数目。
2、代码实现：
#include <stdio.h>
#define N 100
int main(){
int L[N];
int i,j,k;
int n;
printf("输入门的总数，要求小于100：");
while(1){
scanf("%d",&n);
if(n<0||n>100)
printf("输入错误,请重新输入");
else break;
}
for(i=0;i<n;i++) L[i]=0;
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
if(k%j==0)
L[k-1]=(L[k-1]+1)%2;
for(i=0;i<n;i++)
if(L[i]==1)
printf("第%d号门开着\n",i+1);
printf("\n");
return 0;
}
五、实验结果及算法复杂度分析
（一）、排序算法
（1）选择排序
最好时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n^2)。
（2）冒泡排序
最好时间复杂度为O(n2)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n^2)
（3）插入排序
最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)
（4）折半插入排序
最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)
计数排序
最好时间复杂度为O(n)，最坏时间复杂度为O(n)，平均时间复杂度为O(n)
（6）快速排序
最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(nlogn)
（7）归并排序
最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)
（8）堆排序
最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)
（二）、三壶谜题
1、实验结果
2、算法复杂度分析
时间复杂度：O(n^2)
（三）、交替放置的碟子
1、实验结果
2 算法复杂度分析
时间复杂度：O(n(n+1)/2)
（四）、带锁的门
1、实验结果
2、算法复杂度分析
时间复杂度：O(n^2)
六、实验小结（包括问题和解决方法、心得体会等）
通过这次实验，我对算法设计有了更深的认识。在以前的学习中，我认为代码部分是最困难的，而现在我的观念有了转变。很多的问题是源于生活的，大多算法的规则不会像数学公式一样刻板规矩，我们在学习算法的过程中最先要做的是，学会分析实际问题，形成算法思想。在厘清题意的基础上编写实验代码，编译运行后进行相应的优化改进，在解决问题的过程中逐渐提高自己的逻辑思维能力和编程能力。
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
32
0- 0
已为社区贡献8条内容
所有评论(0)