算法设计与分析实验报告c++实现(生命游戏、带锁的门、三壶谜题、串匹配问题、交替放置的碟子)

一、实验目的

1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、 编写一个生命游戏：
规则如下：（或者网上找到更详细的规则）
一个人可以有8个邻居；
一个人若只有一个邻居，在下一代会孤独的死去；
若有2或3个邻居，在下一代依然活着；
若有4个或以上邻居，在下一代会因拥挤而死；
死去的人若有3个邻居，在下一代会复活；
所有的死去或复活都在下一代变化时同时发生。
2、 带锁的门：
在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？
3、三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
4、串匹配问题
给定一段文本，在该文本中查找并定位任意给定字符串。
要求：
（1）实现BF算法；（必做）
（2） 实现BF算法的改进算法：KMP算法和BM算法；（选做）
5、交替放置的碟子
我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。

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

实验设备：win10电脑
编程开发工具：Microsoft Visual c++

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

（一）、生命游戏

1、算法分析
规则如下：（或者网上找到更详细的规则）
一个人可以有8个邻居；一个人若只有一个邻居，在下一代会孤独的死去；
若有2或3个邻居，在下一代依然活着；若有4个或以上邻居，在下一代会因拥挤而死；
死去的人若有3个邻居，在下一代会复活；所有的死去或复活都在下一代变化时同时发生。
可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。继续让规处理当前的细胞图，可以得到下一代的细胞图，周而复始。在游戏的进行中，杂乱无序的细胞会逐渐演化出各种精致、有形的结构；这些结构往往有很好的对称性，而且每一代都在变化形状。一些形状已经锁定，不会逐代变化。有时，一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。

2、源代码

// 生命游戏.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <iostream>
#include <windows.h>
using namespace std;
#define NUM_CELL_CUBE_MODEL 5
//定义细胞结构
struct Cell
{bool live; //标志是否存活int  others; //标志周围的存活细胞数
};int _tmain(int argc, _TCHAR* argv[])
{//定义细胞数组Cell cell[NUM_CELL_CUBE_MODEL][NUM_CELL_CUBE_MODEL];//步骤1：初始化，把所有格子的细胞初始化成活的，周围没有其他细胞for (int i = 0; i < NUM_CELL_CUBE_MODEL; i++){for (int j = 0; j < NUM_CELL_CUBE_MODEL; j++){cell[i][j].live = true;cell[i][j].others = 0;}}//初始化值可以自己设定for (int i = 0; i < NUM_CELL_CUBE_MODEL; i++){for (int j = 0; j < NUM_CELL_CUBE_MODEL; j++){cell[i][j].live = false;cell[i][j].others = 0;}}cell[0][2].live = true;cell[1][2].live = true;cell[2][2].live = true;cell[3][2].live = true;cell[4][2].live = true;//步骤2：细胞不断变化while (1){//步骤2.1：遍历所有细胞，进行显示，并统计周围数量for (int i = 0; i < NUM_CELL_CUBE_MODEL; i++){for (int j = 0; j < NUM_CELL_CUBE_MODEL; j++){//步骤2.1.1：每次变化前，先把每个细胞周围死亡数量设为0cell[i][j].others = 0;//步骤2.1.2：每个细胞如果是活的标记★，死的标记☆if (cell[i][j].live){cout << "★  ";}else{cout << "☆  ";}//步骤2.1.3：检测八个方向是否有存活细胞，计算每一个细胞的周围存活数if ((i - 1) >= 0 && (j - 1) >= 0 && cell[i - 1][j - 1].live)cell[i][j].others++;if ((i - 1) >= 0 && cell[i - 1][j].live)cell[i][j].others++;if ((i - 1) >= 0 && (j + 1) < NUM_CELL_CUBE_MODEL && cell[i - 1][j + 1].live)cell[i][j].others++;if ((j - 1) >= 0 && cell[i][j - 1].live)cell[i][j].others++;if ((j + 1) < NUM_CELL_CUBE_MODEL && cell[i][j + 1].live)cell[i][j].others++;if ((i + 1) < NUM_CELL_CUBE_MODEL && (j - 1) >= 0 && cell[i + 1][j - 1].live)cell[i][j].others++;if ((i + 1) < NUM_CELL_CUBE_MODEL && cell[i + 1][j].live)cell[i][j].others++;if ((i + 1) < NUM_CELL_CUBE_MODEL && (j + 1) < NUM_CELL_CUBE_MODEL && cell[i + 1][j + 1].live)cell[i][j].others++;}cout << endl << endl;}//步骤2.2：根据统计数量，重新计算下一刻的存活情况for (int i = 0; i < NUM_CELL_CUBE_MODEL; i++){for (int j = 0; j < NUM_CELL_CUBE_MODEL; j++){//步骤2.2.1：活着的可能死if (cell[i][j].live){switch (cell[i][j].others){case 2:case 3:cell[i][j].live = true; break;default:cell[i][j].live = false; break;}}//步骤2.2.2：死了的可能活else{if (cell[i][j].others == 3){cell[i][j].live = true;}}}}//每1秒刷新一次Sleep(1000);//清楚屏幕函数system("cls");}return 0;
}

（二）、带锁的门

1、门的状态只有两 种，每经过一次，状态就会发生变化。如果一道门经过奇数次，那么结果状态和原始状态就会不一样，而经过偶数次则不会发生变化。因此问题的关键就是找出那些 经过奇数次的门有多少道。很幸运，那些门的编号正好是整数i的完全平方数即1，4，9，16，…，因此只需要找出这样的数字有多少个即可。
如：假设n = 5
0表示门是关着的，1表示门打开的
一 二 三 四 五
一 1 1 1 1 1
二 1 0 1 0 1
三 1 0 0 0 1
四 1 0 0 1 1
五 1 0 0 0 0
可以发现对角线上的数字就是最后门打开的情况，正好是i的平方数

2、源代码

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10000;
int remainder(int n,int i)
{int remainder = 1;remainder = n%i;if(remainder == 0)return 1;
}
int main(int argc, char **argv)
{int n;int remaind = 0;printf("please input a num:\n");scanf("%d",&n);if (n > 10000){printf("your num is too large!please try it again:");scanf("%d",&n);}int door[10000];for(int i = 0;i < 10000;i++){door[i] = -1;}for ( i = 1;i < n+1;i++){for(int j = 1;j < n;j++){remaind = remainder(j,i);if(remaind ==1)door[j] = door[j] * (-1);}}printf("which door is open:\n");for(int k = 1;k < n;k++){if(door[k] > 0)printf("%d ",k);}printf("\n");printf("which door is close:\n");for( k = 1;k < n;k++){if(door[k] < 0)printf("%d ",k);}printf("\n");system("pause");return 0;
}

（三）、三壶谜题

1、算法分析
可以把每次三个水壶中水的量组成一个状态，比如初始状态为008，对应第一个水壶0品脱水，第二个水壶0品脱水，第三个水壶8品脱水。对题目的状态空间图进行广度优先遍历。当表示状态的数字中出现4时，即求出答案。
为了打印出倒水的过程，需要声明一个前置状态保存当前状态由哪个状态转换而来，然后就可以回溯到初始状态，打印出倒水过程。相当于树中的父结点。
可以声明一个map表，保存已有的状态，对已有的状态，就不再向下继续遍历，这样可以节省求解时间。
因为是广度优先遍历，所以第一次解得的答案所需的倒水的次数最少，解为最优解。

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;
}

（四）、串匹配问题

1、 算法分析
蛮力法(brute force method，也称为穷举法或枚举法)是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。但是，用蛮力法设计的算法时间特性往往也是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。
BF算法：
暴力检索法是最好想到的算法，也最好实现，在情况简单的情况下可以直接使用：
首先将原字符串和子串左端对齐，逐一比较；如果第一个字符不能匹配，则子串向后移动一位继续比较；如果第一个字符匹配，则继续比较后续字符，直至全部匹配。

2、 源代码

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
// 蛮力算法
int BF(string ts, string ps) 
{int i = 0; // 主串的位置int j = 0; // 模式串的位置while (i < ts.length() && j < ps.length()){if (ts[i] == ps[j]) { // 当两个字符相同，就比较下一个i++;j++;}else {i = i - j + 1; // 一旦不匹配，i后退j = 0; // j归0}}if (j == ps.length()) {return i - j;}else {return -1;}
}
// KMP算法计算KMP值（Next值）
//当T[i] != P[j]时
//有T[i - j ~i - 1] == P[0 ~j - 1]
//由P[0 ~k - 1] == P[j - k ~j - 1]
//必然：T[i - k ~i - 1] == P[0 ~k - 1]
vector<int> getNext(string ps) 
{vector<int> next;next.push_back(-1);int j = 0;int k = -1;while (j < ps.length() - 1) {if (k == -1 || ps[j] == ps[k]) {++j;next.push_back(++k);}else{k = next[k];}}return next;
}
// KMP算法
int KMP(string ts, string ps)
{int i = 0; // 主串的位置int j = 0; // 模式串的位置vector<int> next = getNext(ps);while (i < ts.length() && j < ps.length()) {if (j == -1 || ts[i] == ps[j]){// 当j为-1时，要移动的是i，当然j也要归0i++;j++;}else{// i不需要回溯了j = next[j]; // j回到指定位置}}if (j == ps.length()){return i - j;}else {return -1;}
}
int _tmain(int argc, _TCHAR* argv[])
{string A, B;cout << "请输入主串:";cin >> A;cout << "请输入要查找的字符串:";cin >> B;//使用蛮力算法求解int nPosition = BF(A, B);//使用KMP算法求解//int nPosition = KMP(A, B);if (nPosition != -1){cout << "在第" << nPosition + 1 << "个位置，找到了子串！\n";}else{cout << "没有找到子串！\n";}system("pause");return 0;
}

（五）、交替放置的碟子

1、 算法分析
2、
首先把问题转化一下，用1表示黑碟子，0表示白碟子，那么目前的顺序是：
1010…1010
结果要求1都放在右边，0都放在左边。这个题目看起来很眼熟。看关键字：交换相邻的碟子，排好顺序。嗯，就是经常出现在面试中的冒泡排序了。
为便于观察，假设目前有6个碟子：101010。使用冒泡排序，第一次迭代，碟子序列变为：010101，交换3次。在进行第二次迭代之前，观察一下。
现在，不仅第一个碟子就位，最后一个也是了，因此第二次迭代只需要对第2到第5个进行排序，巧合的是，碟子[2->5]仍然是10交替出现，不过比上一次少了两个，这样就简单了，可以得到结论：对于2n个碟子，可以使用n次迭代完成，交换的次数分别是：n+(n-1)+…+2+1，即n(n+1)/2。
2、源代码

#include "stdafx.h"
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;
#define  PROBLEM_LARGE 10
#define  ALL_CATE_NUM PROBLEM_LARGE*2
static string arrAllCate[ALL_CATE_NUM];
//交替算法:方法1
void WayChange1()
{int nChangePosition = 0;int nCirCle = 0;for (int i = 0; i < PROBLEM_LARGE; ++i){int nNow = i + 1;do{if (arrAllCate[nNow - 1] != arrAllCate[nNow]){//交换两个相邻元素值string strRange = arrAllCate[nNow - 1];arrAllCate[nNow - 1] = arrAllCate[nNow];arrAllCate[nNow] = strRange;//交换次数加1++nChangePosition;}++nNow;//循环次数加1++nCirCle;} while (nNow < ALL_CATE_NUM);//每一趟的结果都输出出来cout << "第" << i + 1 << "趟结果：";for (int j = 0; j < ALL_CATE_NUM; ++j){cout << arrAllCate[j] << " ";}cout << endl << endl;}cout << "交换次数：" << nChangePosition << endl;cout << "循环次数：" << nCirCle << endl;
}
//交替算法:方法2
void WayChange2()
{int nChangePosition = 0;int nCirCle = 0;for (int i = 0; i < PROBLEM_LARGE;++i){int head = i;int tail = ALL_CATE_NUM - i - 1;do{if (tail - head == 1){string strMid = arrAllCate[head];arrAllCate[head] = arrAllCate[tail];arrAllCate[tail] = strMid;//交换次数加1++nChangePosition;}else{string strRangehead = arrAllCate[head];arrAllCate[head] = arrAllCate[head + 1];arrAllCate[head + 1] = strRangehead;string strRangetail = arrAllCate[tail];arrAllCate[tail] = arrAllCate[tail - 1];arrAllCate[tail - 1] = strRangetail;//交换次数加2nChangePosition +=2;}head += 2;tail -= 2;//循环次数加1++nCirCle;} while (head < tail);//每一趟的结果都输出出来cout << "第" << i + 1 << "趟结果：";for (int j = 0; j < ALL_CATE_NUM; ++j){cout << arrAllCate[j] << " ";}cout << endl << endl;}cout << "交换次数：" << nChangePosition << endl;cout << "循环次数：" << nCirCle << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{// 初始化棋子cout << "初始化棋子如下：";for (int i = 0; i < ALL_CATE_NUM; ++i){int nCount = i + 1;if (nCount % 2 == 0){arrAllCate[i] = "☆";}else{arrAllCate[i] = "★";}cout << arrAllCate[i] << " ";}cout << endl << endl;WayChange1();//WayChange2();system("pause");return 0;
}

五、实验结果及算法复杂度分析

（一）、生命游戏

1、实验结果

2 算法复杂度分析

时间复杂度：$O(4n^2)$

（二）、带锁的门
1、实验结果

2 算法复杂度分析
时间复杂度：$O(n^2+2n)$

（三）、三壶谜题
1、实验结果

2 算法复杂度分析
时间复杂度：$O(n^2)$
（四）、串匹配问题
1、实验结果

2 算法复杂度分析
最坏时间复杂度：$O（m\ast n）$
（五）、交替放置的碟子
1、实验结果

2 算法复杂度分析
时间复杂度：O(n(n+1)/2)

实验小结（包括问题和解决方法、心得体会等）

通过本次实验我对分治算法有了不错的掌握和更深的的了解，对其求解原理也有了实际解决的经验。分治算法就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。同时也对蛮力算法有了进一步的认识，它是一种简单直接地解决问题的方法，在有些情况下处理问题效率更高。