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

一、实验目的

1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力；

3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、 编写一个生命游戏：

规则如下：（或者网上找到更详细的规则）

一个人可以有8个邻居；

一个人若只有一个邻居，在下一代会孤独的死去；

若有2或3个邻居，在下一代依然活着；

若有4个或以上邻居，在下一代会因拥挤而死；

死去的人若有3个邻居，在下一代会复活；

所有的死去或复活都在下一代变化时同时发生。

2、 带锁的门：

在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？

3、排序算法

目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法，并分析算法的时间复杂度。比较各种算法的优劣。

4、三壶谜题：

有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。

5、交替放置的碟子

我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…

现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。

三、实验设备及编程开发工具

实验设备：Win10 电脑

开发工具：Microsoft Visual C++

四、实验过程设计（算法设计过程）

（一）、生命游戏

1、算法分析：

生命游戏的规则可简化如下：

1.邻居个数为0，1，4，5，6，7，8时则该细胞下次的状态为死亡。

2.邻居个数为2时，则该细胞下次状态为复活。

3.邻居个数为3时，则该细胞下次状态为稳定，运行结果为生成细胞存活的状态图。

4.最初细胞默认都是死亡状态，活细胞需要自己设定生成。

2、代码实现：

#include 
#include 
#include 
#include 
#include 
#define ROWLEN 10//二维空间行数； 
#define COLLEN 10//二维空间列数； 
#define DEAD 0 //死细胞； 
#define ALIVE 1 //活细胞； 
using namespace std;
int cell[ROWLEN][COLLEN];//当前生命细胞的状态；
int celltemp[ROWLEN][COLLEN];//用于判断当前细胞的下一个状态
void initcell() {
	int row,col;
	for(row=0; row
		for(col=0; col
			cell[row][col]=DEAD;
		}
	}
	printf("输入一组活细胞的坐标位置,输入(-1,1)结束\n");
	while(1) {
		printf("输入一个活细胞的坐标位置: ");
		cinrow>>col;
		if(0
			cell[row][col]=ALIVE;
		} else if(row==-1||col==-1) {
			break;
		} else {
			printf("输入坐标超过范围。\n");
		}
	}
	}
int LinSum(int row,int col) {
	int count=0,c,r;
	for(r=row-1; r
		for(c=col-1; c
			if(r
				continue;
			}
			if(cell[r][c]==ALIVE) {
				count++;
			}
		}
	}
	if(cell[row][col]==ALIVE) {
		count--;
	}
	return count;
}
void OutCell() {
	int row,col;
	printf("\n细胞状态\n");
	for(col=0; col
	}
	cout
		for(col=0; col
			switch(cell[row][col]) {
				case ALIVE:
					printf("●");//活细胞；
					break;
				case DEAD:
					printf("○");//死细胞；
					break;
				default:
					;
			}
		}
			printf("\n");}
void cellfun() {
	int row,col,sum;
	int count=0;
	for(row=0; row
		for(col=0; col
			switch(LinSum(row,col)) { //四周活细胞适量；
				case 2:
					celltemp[row][col]=cell[row][col];//保持细胞原样；
					break;
				case 3:
					celltemp[row][col]=ALIVE;//复活；
					break;
				default://死了；
					celltemp[row][col]=DEAD;
			}
		}
	}
	for(row=0; row
		for(col=0; col
			cell[row][col]=celltemp[row][col];
		}
	}
	for(row=0; row
		for(col=0; col
			if(cell[row][col]==ALIVE) { //如果是活细胞；
				count++;//累计或细胞数量；
			}
				}
	}
	sum=count;
	OutCell() ;//显示当前细胞状态；
	printf("当前状态下，一共有%d个活细胞。\n",sum);
}
int main() {
	char again;
	printf("生命游戏!\n") ;
	initcell();						//初始化
	OutCell();						//输出初始细胞状态；
	printf("按任意键开始游戏,进行细胞转换。\n");
	getch() ;
S1:
	cellfun();
S2:
	printf("\n继续生成下一次细胞状态(y/n)?");
	fflush(stdin);
	cinagain;
	if(again=='y'||again=='Y') {
		goto S1;
	} else if(again=='n'||again=='N') {
		goto S3;
	} else {
		printf("输入错误，请重新输入!\n");
		goto S2;
	}
S3:
	printf("游戏结束!\n");
	return 0;
}

int L[N];
int i,j,k;
int n;
printf("输入门的总数，要求小于100：");
while(1)
{
 scanf("%d",&n);
 if(n
if(L[i]==1)
printf("第%d号门开着\n",i+1);
}
printf("\n");
return 0; 
}

public:
	int second;
	int num[3];
	State* preState;
        static map
		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
	map
		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 n,num=0;
		printf("输入碟子的总数量:");
	    scanf("%d",&n);
       
		int sum[100];
		// 将所有碟子存放在一个数组里,设白碟子值为1，黑碟子值为2，
		//初始排序为：21212121……
		//换位后排序为 11112222……
		 
		for(int i=0;i
			sum[2*i]=2;
			sum[2*i+1]=1;
		}
        printf("碟子的初始状态如下:\n");
		 //输出碟子的初始排序 
		for(i=0;i
			printf(sum[i]+" ");
			if(sum[i]==1)
			{
				printf("白 ");
			}
			else
			{
				printf("黑 ");
			}
		}
		printf("\n");
		//进行排序
		for(i=0;i
			for(int j=0;j
				if(sum[j+1]
					int t=sum[j];
					sum[j]=sum[j+1];
					sum[j+1]=t;
					num++;
				}
			}
		}
		printf("排序后的顺序为:\n");
		for(i=0;i
			printf(sum[i]+" ");
			if(sum[i]==1)
			{
				printf("白 ");
			}
			else
			{
				printf("黑 ");
			}
		}
       printf("\n一共换位了%d次",num);
       printf("\n");
    return 0;
}