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

2024-04-14 14:52
文章标签 算法 分析 c++ 实现 设计 问题 放置 游戏 匹配 谜题 生命 实验报告 交替 三壶 带锁 碟子

本文主要是介绍算法设计与分析实验报告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白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。

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

笔记本，Windows10操作系统，Dev-C++

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

1、编写一个生命游戏

(1)问题分析：
解法生命游戏的规则可简化为以下，并使用CASE比对即可使用程式实作：
邻居个数为0、1、4、5、6、7、8时，则该细胞下次状态为死亡。
邻居个数为2时，则该细胞下次状态为复活。
邻居个数为3时，则该细胞下次状态为稳定。
代码是不断生成细胞存活的状态图，首先细胞默认都是死的，活细胞需要你自己一个一个生成，核心代码在neighbors(int，int)函数里面。

(2)算法实现

//需要的头文件以及宏定义，最多8*8个人，存活状态为1，死亡状态为0
#include<stdio.h>
#define MAXROW 8 
#define MAXCOL 8
#define ALIVE 1
#define DEAD 0
//函数声明
int map[MAXROW][MAXCOL], newmap[MAXROW][MAXCOL];
void init();//初始化游戏
int neighbors(int, int);//根据邻居数量判定生命状态
void outputMap()；//输出游戏当代的状态
void copyMap();//复制当代的状态
//主函数
int main()
{int row, col;char ans;init();while (1){outputMap();for (row = 0; row < MAXROW; row++){for (col = 0; col < MAXCOL; col++){switch (neighbors(row, col)){case 0:case 1:case 4:case 5:case 6:case 7:case 8:newmap[row][col] = DEAD;break;case 2:newmap[row][col] = map[row][col];break;case 3:newmap[row][col] = ALIVE;break;}}}copyMap();printf("\nContinue next Generation ? ");getchar();ans = toupper(getchar());if (ans != 'Y')break;}return 0;
}
//生命游戏初始化，由用户输入存活人的坐标x,y，按-1，-1结束
void init()
{int row, col;for (row = 0; row < MAXROW; row++)for (col = 0; col < MAXCOL; col++)map[row][col] = DEAD;puts("Game of life Program");puts("Enter x, y where x, y is living cell");printf("0 <= x <= %d, 0 <= y <= %d\n", MAXROW - 1, MAXCOL - 1);puts("Terminate with x, y = -1, -1");while (1){scanf("%d%d", &row, &col);if (0 <= row && row < MAXROW && 0 <= col && col < MAXCOL)map[row][col] = ALIVE;else if (row ==  - 1 || col ==  - 1)break;elseprintf("(x, y) exceeds map ranage!");}
}//游戏规则制定，根据邻居数量判定人的生命状态，row，col为人的坐标
int neighbors(int row, int col)
{int count = 0, c, r;for (r = row - 1; r <= row + 1; r++)for (c = col - 1; c <= col + 1; c++){if (r < 0 || r >= MAXROW || c < 0 || c >= MAXCOL)continue;if (map[r][c] == ALIVE)count++;}if (map[row][col] == ALIVE)count--;return count;
}
//打印游戏状态，死亡记为“_”，生存记为“*”
void outputMap()
{int row, col;printf("\n\n%20cGame of life cell status\n");for (row = 0; row < MAXROW; row++){printf("\n%20c", ' ');for (col = 0; col < MAXCOL; col++)if (map[row][col] == ALIVE)putchar('*');elseputchar('-');}
}void copyMap()
{int row, col;for (row = 0; row < MAXROW; row++)for (col = 0; col < MAXCOL; col++)map[row][col] = newmap[row][col];
}

2、带锁的门

(1)问题分析：
举例说明：假设n = 5,0表示门是关着的，1表示门是开着的，则模拟上述过程如下：
状态数组下标：1 2 3 4 5
状态数组的值：0 0 0 0 0 ―――＞初始状态
状态数组的值：1 1 1 1 1 ―――＞第一次
状态数组的值：1 0 1 0 1 ―――＞第二次
状态数组的值：1 0 0 0 1 ―――＞第三次
状态数组的值：1 0 0 1 1 ―――＞第四次
状态数组的值：1 0 0 1 0 ―――＞第五次
(2)算法实现

//需要的头文件以及宏定义，N为门数量的最大值
#include <stdio.h>
#define N 1000
//主函数
int main()
{int L[N];int i,j,k;int n;printf("请输入小于1000的整数代表门的总数：");while(1){scanf("%d",&n);if(n<0||n>1000)//验证输入是否在有效范围内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;     
}

3、 三壶谜题

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

4、 串匹配问题

(1) 问题分析
从主串s的pos位置出发，与子串t第一位进行匹配，若相等，接着匹配后一位字符，若不相等，则返回到s前一次匹配位置的后一位，接着与t的起始位进行匹配，直到与t全部匹配成功，则返回在s中开始完全匹配的下标。
简单说这个算法的思想就是匹配失败，就重新从上一次匹配位置的下一位开始匹配。

(2) 算法实现

#include <stdio.h>          //头文件
#include <string.h>        //字符串头文件//BF算法 s是原字符串，t是匹配字符串
int BF(char s[],char t[],int pos)
{int m,n;int i=pos,j=0;          //从0位置开始匹配m=strlen(s);n=strlen(t);             //用m,n表示s,t长度while (i<=m&&j<=n)       //m,n是串长{if (s[i]==t[j]){i++;  j++;        //逐个匹配，成功s++   t++} else{i=i-j+1;       //不成功，s返回到此次循环匹配的初始位置j=0;           //不成功，t返回到0位置}  }if(j>n)return (i-n);          //返回匹配成功的原串中第一个字符的位置  elsereturn 0;}int main(){char s[]="abcdeabcabcde";      //初始定义s串int pos;pos=BF(s,"abcd",0);        //从0位置匹配abcdprintf("pos=%d\n",pos);pos=BF(s,"abcde",pos);    //从上次匹配成功的位置匹配abcdeprintf("pos=%d\n",pos);return 0;
}

5、 交替放置的碟子
(1) 问题分析
输入盘子总数2n，起始状态黑白盘子交替出现，为黑白黑白黑白…定义黑为2，白为1，则初始状态利用数组存储为[2,1,2,1,2,1…]，对数组内的数据进行排序将所有的1放置所有的2之前，输出为[2,2,2,1,1,1…]即可实现。
(2) 算法实现

#include<stdio.h>int main(){int bubble_num,i ;void sortDisplay(int bubble_set[],int length);printf("请输入盘子总数:");	scanf("%d",&bubble_num);printf("\n");int bubble_set[bubble_num];int length = sizeof(bubble_set)/sizeof(bubble_set[0]);for(i=0;i<=(length-2)/2;i++){bubble_set[2*i]=2;bubble_set[2*i+1]=1;}printf("盘子的初始顺序为：\n");	sortDisplay(bubble_set,length);printf("\n");for(i=0;i<length-1;i++){int j; for(j=0;j<length-1-i;j++){if(bubble_set[j+1]<bubble_set[j]){int t=bubble_set[j];bubble_set[j]=bubble_set[j+1];bubble_set[j+1]=t;}}}printf("盘子排序后的顺序为：\n");sortDisplay(bubble_set,length);return 0;
}void sortDisplay(int bubble_set[],int length){int i; for(i=0;i<length;i++){
//			printf("%d ",bubble_set[i]); if(bubble_set[i]==1){printf("白 ");}else{printf("黑 ");;}}printf("\n");
}

五、实验结果及算法复杂度分析
1、编写一个生命游戏

img

2、带锁的门

img

3、三壶谜题

img

4、串匹配

image-20240404122431379

复杂度最坏情况O(M*N)（M,N分别为2个字符串的长度）。
5、交替放置的碟子

image-20240404122751386

这篇关于算法设计与分析实验报告c++实现(生命游戏、带锁的门、三壶谜题、串匹配问题、交替放置的碟子)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/903282。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2