算法设计与分析实验报告c++实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)

一、实验目的

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  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  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 = 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  
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  
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]  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] 
	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
	int mid;
	if(l  
9. 三壶谜题
 
1、算法分析：
可以把每次三个水壶中水量设成一组状态，比如初始状态为008，对应第一个水壶0品脱水，第二个水壶0品脱水，第三个水壶8品脱水。对题目的状态空间图进行广度优先遍历。当表示状态的数字中出现4时，即求出答案。
（1）打印倒水的过程，需要声明一个前置状态保存当前状态由哪个状态转换而来，然后就可以回溯到初始状态，打印出倒水过程。
（2）声明一个map表，保存已有的状态，对已有的状态就不再向下继续遍历。
（3）因为是广度优先遍历，所以第一次得到的答案所需的倒水次数最少，即为最优解。
2、代码实现：
 
#include 
#include 
#include 
#define MaxFirst 3
#define MaxSecond 5
#define MaxThird 8
using namespace std;
class State
{
public:
	int second;
	int num[3];
	State* preState;
        static map 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 State::mapping;
int main()
{
	map states;
	State *start=new State(0,0,8);
	start->init();
	State *state=start;
	State *endState=new State(8,8,8); //只有获得解endState才会改变，赋值全为8为了方便判断是否获得最终解
	vector action; //保存所有状态对象
	action.push_back(*start); //把初始状态先加入队列中
	int n=0;
	do{
		for(int i=0;i
			for(int j=0;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
		state=state-preState;
		cout
	int count = 0;
	bool flag = true; // 用于判断当前轮是否有序 
	int k = 1;
	while (flag) {
		flag = false;
		for (int i = 0; i