算法设计与分析实验报告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;
    else
      printf("(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('*');
      else
        putchar('-');
  }
}
 
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);          //返回匹配成功的原串中第一个字符的位置  
	else
		return 0;

}

int main(){
	char s[]="abcdeabcabcde";      //初始定义s串
	int pos;
	pos=BF(s,"abcd",0);        //从0位置匹配abcd
	printf("pos=%d\n",pos);
	pos=BF(s,"abcde",pos);    //从上次匹配成功的位置匹配abcde
	printf("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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543902.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java多线程学习总结

在Java中&#xff0c;多线程编程是一种重要的编程模型&#xff0c;它允许程序同时执行多个任务&#xff0c;从而提高了程序的执行效率和响应速度。 一、基本概念 进程与线程&#xff1a;进程是系统分配资源的基本单位&#xff0c;它包含了程序执行所需的资源&#xff0c;如代码…

Django第三方功能的使用

Django第三方功能的使用 Django REST framework前言1、Django--Restframework--coreapi版文档BUG:AssertionError: coreapi must be installed for schema support.How to run Django with Uvicorn webserver?2、序列化类 Serializer的使用模型序列化类 ModelSerializer的使用…

2024年阿里云优惠券领取攻略

阿里云作为国内领先的云计算服务提供商&#xff0c;以其稳定、高效、安全的服务赢得了众多用户的青睐。为了吸引用户上云&#xff0c;阿里云经常推出各种优惠活动&#xff0c;其中就包括阿里云优惠券。本文将为大家详细解读2024年阿里云优惠券的领券攻略&#xff0c;帮助大家轻…

DDR3的使用(非AXI4总线)

参考小梅哥视频&#xff1a;https://www.bilibili.com/video/BV1va411c7Dz/?p48&spm_id_frompageDriver&vd_sourceaedd69dc9740e91cdd85c0dfaf25304b 一、DDR3的MIG配置 找到MIG的IP核 AXI4 interface不用勾选 不需要兼容以下的FPGA就不用勾选 选择DDR3 1.1 三…

ARM v8 Cortex R52内核 04 时钟和复位 Clocking and Resets

ARM v8 Cortex R52内核 04 时钟和复位 Clocking and Resets 4.1 Clock and clock enables 时钟和时钟使能 Cortex-R52处理器具有一个单一的时钟&#xff0c;驱动着所有的触发器和RAM。各种输入&#xff0c;包括复位输入&#xff0c;都有同步逻辑使它们可以与处理器时钟异步操…

C语言—实现循序表的增删查改

一.正文 嗨嗨嗨&#xff01;大家好&#xff01;今天我为大家分享的是数据结构知识——顺序表。废话不多数&#xff0c;让我们开始今天的知识分享吧。 二.正文 1.1认识数据结构 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素…

【学习】软件测试人员使用Loadrunner进行性能测试的优势

在软件测试领域&#xff0c;性能测试是一项至关重要的环节&#xff0c;它关乎到软件系统的稳定性和用户体验。而在这其中&#xff0c;Loadrunner作为一款久经考验的性能测试工具&#xff0c;凭借其独特的优势&#xff0c;成为了众多企业和开发者眼中的“得力助手”。 首先&…

踩了一堆坑,终于掌握了postgreSQL主从流的精髓

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…

spring-cloud-alibaba微服务Sentinel

Sentinel 官方网站 sentinel-dashboard-1.8.7.jar包下载地址 在window通过命令行启动&#xff08;java -Dserver.port8080 -Dproject.namesentinel-dashboard -jar sentinel-dashboard-1.8.7.jar&#xff09;&#xff0c;可以通过 -Dserver.port修改控制台的端口 使用的版本最好…

探索ERC20代币:构建您的第一个去中心化应用

下面文章中会涉及到该资源中的代码&#xff0c;如果想要完整版代码可以私信我获取&#x1f339; 文章目录 概要整体架构流程技术名词解释ERC20智能合约web3.js 技术细节ERC20合约部署创建前端界面前端与智能合约互连运行DAPP 小结 概要 在加密货币世界中&#xff0c;ERC20代币…

地球上的七大洲介绍

地球上的七大洲示意图&#xff1a; 1. 亚洲&#xff08;Asia&#xff09;&#xff1a;世界上最大的洲&#xff0c;面积约为44579000平方公里。亚洲地域辽阔&#xff0c;包括从北极圈到赤道的各种气候和地形。它拥有世界上最多的人口&#xff0c;也是世界上一些最古老文明的发源…

【Linux】账号和权限管理

目录 一、用户账号与组账号 二、添加用户账号-useradd 三、修改用户账号的属性-usermod 四、更改用户命令-passwd 五、删除用户账号-userdel 六、添加组账号-groupadd 七、添加删除组成员-gpasswd 八、删除组账号-groupdel 九、查询账号信息-groups、id、finger、w、w…

REINFORCE及进阶算法讲解笔记

REINFORCE 总结 估计VALUE-methods没有在理论上证明收敛&#xff0c;而policy-methods不需要估计value function。 本算法总结了过去的算法&#xff0c;将过去算法作为特例看待&#xff0c;证明了即使是结合函数估计和实际采样的value梯度都可以无偏估计&#xff0c;证明了某种…

Java基础(一)--语法入门

文章目录 第一章、语法入门一、Java简介1、JVM2、Java程序执行过程3、JDK4、JRE5、JDK、JRE和JVM三者关系 二、Java常量与变量1、标识符2、关键字3、保留字4、变量5、数据类型6、常量 三、运算符1、算术运算符2、赋值运算符3、关系运算符4、逻辑运算符5、条件运算符6、运算符的…

Spring5深入浅出篇:Spring自定义类型转换器

Spring5深入浅出篇:Spring自定义类型转换器 类型转换器 首先要知道什么叫做类型转换器 ,我们通过配置的属性值是以字符串的形式为什么在查看对象成员变量时已经变成了int,这就是Spring的内置类型转换器帮我们做了自动类型转换. 作⽤&#xff1a;Spring通过类型转换器把配置⽂件…

Leetcode二十三题:合并K个升序链表【22/1000 python】

“合并K个升序链表”&#xff0c;这是一道中等难度的题目&#xff0c;经常出现在编程面试中。以下是该问题的详细描述、解题步骤、不同算法的比较、代码示例及其分析。 问题描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中…

数据结构书后习题

p17 1&#xff0c; 个人解答&#xff1a; int DeleteMinElem(SqList &L,int &min) {int j 0;if (L.length 0){printf("error!");return 0;}int min L.data[0];for (int i 1; i < L.length; i){if (L.data[i] < min){min L.data[i];j i;}}L.dat…

软考127-上午题-【软件工程】-McCabe度量法

一、McCabe度量法 1-1、定义 McCabe 度量法是通过定义环路复杂度&#xff0c;建立程序复杂性的度量。 它基于一个程序模块的程序图中环路的个数。计算有向图G的环路复杂性的公式为&#xff1a; V(G) m - n 2 闭合区域 1 其中V(G)是有向图 G 中的环路个数&#xff0c;m 是…

【C语言__结构体__复习篇3】

目录 前言 一、结构体基础知识 1.1 结构体的语法形式 1.2 创建结构体变量 1.3 结构体变量的初始化 1.4 点(.)操作符和箭头(->)操作符 二、匿名结构体 三、结构体自引用 四、结构体内存对齐 4.1 内存对齐的规则 4.2 出现结构体内存对齐的原因 4.3 修改默认对齐数 五、结…

8:系统开发基础--8.1:软件工程概述、8.2:软件开发方法 、8.3:软件开发模型、8.4:系统分析

转上一节&#xff1a; http://t.csdnimg.cn/G7lfmhttp://t.csdnimg.cn/G7lfm 课程内容提要&#xff1a; 8&#xff1a;知识点考点详解 8.1&#xff1a;软件工程概述 1.软件的生存周期 2.软件过程改进—CMM Capability Maturity Model能力成熟度模型 3.软件过程改进—CMMI—…