算法设计与分析4.1 迷宫问题 栈与队列解法、打印矩阵、三壶问题、蛮力匹配

1.ROSE矩阵

实现:

img

使用算法2

分析: 每半圈元素值的增长规律变换一次
设增量为t,每半圈变换一次t <— -t .
设矩阵边长为i,每半圈的元素个数是2*(i-1)个,hc为记数变量,则1≤hc<=2i-1,前1/4圈是1≤hc<=i-1,后1/4是i≤hc<=2i-2,若hc%i==0,则前1/4圈结果为0,后1/4结果为1,可表示为:index <— hc/i, hc <— hc+1。

计算模型:

设s[1]为矩阵行下标,s[0]为矩阵列下标。s数组下标为index。

t为下标增量,初值为-1,矩阵元素k∈[1,n*n].

1.index<- hc/i+1

2.hc<- hc+1

3.hc∈[1,2*i-1]

4.s[index]<-s[index]+t

5.a[s[1],s[0]]<- k , k<- k+1

6.当hc>2*i-1,i<- i-1 ,t<- -t

代码:

void rose(int n)
{
	int s[2];
	int a[n][n];
	int k=1,i=n,t=1;
	s[0]=-1,s[1]=0;
	while(k<=n*n)
	{
		for(int hc=1;hc<=2*i-1;++hc)
		{
			int index=hc/(i+1);
			s[index]+=t;
			a[s[1]][s[0]]=k;
			++k;
		}
		i--;
		t=-t;
	}
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			cout<<a[i][j]<<"\t";
		}
		cout<<endl;
	}
}

在这里插入图片描述

2.迷宫

在这里插入图片描述

最优路径?

可以使用栈或队列完成。

定义:

int M [ 10 ] [ 10 ] [10][10] [10][10]={
1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,1,1,1,1,0,1,0,1,
1,0,0,0,0,1,0,1,0,1,
1,0,1,0,0,0,0,1,0,1,
1,0,1,0,1,1,0,1,0,1,
1,0,1,0,0,0,0,1,1,1,
1,0,1,0,0,1,0,0,0,1,
1,0,1,1,1,1,1,1,0,1,
1,1,1,1,1,1,1,1,1,1,} ;

//状态定义 :
// M [ x ] [ y ] [x][y] [x][y]为0:通路 ,为1:墙 , 为2:死路 , 为3:已走过

int fx[]={-1,1,0,0};
int fy[]={0,0,-1,1};
typedef struct p
{
	int x,y;
	struct p* next;
}point;

1).若使用栈:

主要代码:

void bfs()
{
	stack<point*>s;
	point *head=new point,*p;
	int x=1,y=1;
	head->x=x;
	head->y=y; 
	head->next=NULL;
	M[x][y]=3;
	s.push(head);
	int flag=0;
	while(!s.empty() )
	{
		p=s.top();
		s.pop();
		//cout<<"front:"<<p->x<<" "<<p->y<<endl;
		for(int i=0;i<4;++i)
		{
			y=p->y+fy[i];
			x=p->x+fx[i];
			if(M[x][y]==0)
			{
				//cout<<x<<" "<<y<<endl; 
				M[x][y]=3;
				point * newp=new point;
				newp->x=x;
				newp->y=y;
				newp->next=p;
				s.push(newp);
				if(x==8 && y==8)
				{
					flag=1;
					break;
				} 
			}
		}
		if(flag)break;} 
​	p=s.top();while(p){
​		cout<<"("<<p->x<<","<<p->y<<")"<<"  ";
​		p=p->next;}

}

具体实现:

在这里插入图片描述

使用栈可以完成查找,但因其后入先出的特性,在程序实现中,优先对左上方的节点进行查找,针对此迷宫而言会产生一些不必要的路径。

所以若想最短时间得到最优路径可以使用队列。

2).队列实现:队列由于其先入先出的特点,每次都对右下方的点进行率先遍历,故更容易找到最优路径。

使用链表存储。

主要代码实现:

void bfs()
{
	m[x][y]=3;
	p=new po;
	p->x=x;
	p->y=y;
	p->pre=NULL;
	q.push(p);
	while(!q.empty() )
	{
		po * p1=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			po* pnew=new po;
			pnew->pre=NULL; 
			pnew->x =p1->x + fx[i];
			pnew->y = p1->y+ fy[i];
			if(m[pnew->x][pnew->y] ==0 )
			{
				m[pnew->x][pnew->y]=3;
				pnew->pre=p1;
				q.push(pnew);
			}
			if(pnew->x==8 && pnew->y==8)
				return;
		} 
	}

} 

实现:
在这里插入图片描述

使用队列来实现,其时间为使用栈实现的一半左右。

3.三壶问题

在这里插入图片描述

BFS思想 穷举+回溯.

代码实现:

逐步模拟三个壶的倒水状态

typedef struct node
{
	int x,y,z;
	struct node * pre;
}node;
queue<node*>q;
node *p2;
node *p3;
set<int> cha;
bool is(node *p)
{
	if(p->x==4||p->y==4||p->z==4)
		return true;
	else 	return false;
}
void out(node *p)
{
	cout<<"("<<p->x<<","<<p->y<<","<<p->z<<")"<<endl;
}
void BFS()
{
	node *p=new node;
	p->x=8;p->y=0;p->z=0;
	p->pre=NULL;
	q.push(p);
	while(!q.empty())
	{
		node *p1=q.front();
		if(is(p1))	return;
		int x=p1->x;
		int y=p1->y;
		int z=p1->z;
		q.pop();
		if(cha.find(x*100+y*10+z)!=cha.end())  //没有任何一组状态使用此公式得到的计算结果是相同的,故用此来判别状态是否已被遍历 
			continue;
		else	cha.insert(x*100+y*10+z);
		if(x>0&&y<5)
		{
			p3=new node;
			if(x+y>5)
			{
				p3->x=x+y-5;
				p3->y=5;
			}
			else
			{
				p3->x=0;
				p3->y=x+y;
			}
			p3->z=z;
			p3->pre=p1;
			q.push(p3);
			if(is(p3))	return;
		}
		if(x>0&&z<3)
		{
			p3=new node;
			if(x+z>3)
			{
				p3->x=x+z-3;
				p3->z=3;
			}
			else
			{
				p3->x=0;
				p3->z=x+z;
			}
			p3->y=y;
			p3->pre=p1;
			q.push(p3);
			if(is(p3))	return;
		}
		if(y>0)
		{
			p3=new node;
			p3->x=x+y;
			p3->y=0;
			p3->z=z;
			p3->pre=p1;
			q.push(p3);
			if(is(p3))	return;
		}
		if(z>0)
		{
			p3=new node;
			p3->x=x+z;
			p3->z=0;
			p3->y=y;
			p3->pre=p1;
			q.push(p3);
			if(is(p3))	return;
		}
		if(y>0&&z<3)
		{
			p3=new node;
			if(y+z>3)
			{
				p3->y=y+z-3;
				p3->z=3;
			}
			else
			{
				p3->y=0;
				p3->z=y+z;
			}
			p3->x=x;
			p3->pre=p1;
			q.push(p3);
			if(is(p3))	return;
		}
		if(z>0&&y<5)
		{
			p3=new node;
			if(y+z>5)
			{
				p3->z=y+z-5;
				p3->y=5;
			}
			else
			{
				p3->z=0;
				p3->y=y+z;
			}
			p3->x=x;
			p3->pre=p1;
			q.push(p3);
			if(is(p3))	return;			
		}
	}
}

在这里插入图片描述

在这里插入图片描述

4.蛮力匹配

有A B两个字符串 ,长度为n和m

则其最差情况下:首先让A从第一个字符与B的各个字符进行比较,耗时m,A中共n个字符

耗时:O((n-m-1)*m)

5.相当于全排列,则共需 T(n)=O( (n-1)! )时间

6.经计算:15!=1307674368000

16!=20922789888000

18!=6402373705728000

19!=121645100408832000

1小时 运算:3.6* 1 0 13 10^{13} 1013次 16个城市

24小时 运算8.64* 1 0 14 10^{14} 1014次 17个城市

1年运算3.1536* 1 0 17 10^{17} 1017次 19个城市

100年运算3.1536* 1 0 19 10^{19} 1019​次 20个城市

  1. BFS时间复杂度分析

使用邻接表完成

对于 G 令 vexnum=n 即节点数量为n 对于邻接表:共e条边

则其所需时间共分为两部分,n个节点需要O(n)的复杂度,

而邻接表需O(e)的复杂度~ 总时间复杂度为O(n+e).

8.背包问题

1)时间复杂度

单纯通过穷举法,则:对于n个物品,会有 2 n − 1 2^{n-1} 2n1种解 时间复杂度为 O ( 2 n ) O(2^{n}) O(2n)

2)改进

动规

int main()
{
    int N, V;
    cin >> N >> V;
    vector<int> v(N + 1), w(N + 1), f(V + 1);
    for(int i = 1; i <= N; ++i)
        cin >> v[i] >> w[i];
    for(int i = 1; i <= N; ++i)
        for(int j = V; j >= v[i]; --j)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << *max_element(f.begin(), f.end());
    return 0;
}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

时间复杂度: O ( N ∗ V ) O(N*V) O(NV)

贪心

对物品的: 价值/物品体积 进行排序,逐个判断其体积是否能被装下

int G()
{
  float temp=0;
  float result=0;
  float c1=8; 
for(int i=0;i<4;i++)
{
  for(i=0;i<4;i++)
  {
  if(temp<sortBest[i])
    temp=sortBest[i];
  }
  //cout<<"max(sortBest)="<<temp<<endl;
  for(i=0;i<4;i++)
  {
  if (temp==sortBest[i])
  sortBest[i]=0; 
  if (w[i]<=c1)
  result=result+v[i];
  c1=c1-w[i]; 
  }
}

在这里插入图片描述

时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

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

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

相关文章

ChatGLM2-6B的部署步骤_A3

ChatGLM2-6B 下载地址 一、VisualGLM-6B环境安装 1、硬件配置 操作系统&#xff1a;Ubuntu_64&#xff08;ubuntu22.04.3&#xff09; GPU&#xff1a;4050 显存&#xff1a;16G 2、配置环境 建议最好自己新建一个conda环境 conda create -n chatglm2 python3.8pip …

【go项目01_学习记录day01】

博客系统 1 vscode开发go项目插件推荐1.1 CtrlShiftP&#xff08;俗称万能键&#xff09; &#xff1a;打开命令面板。在打开的输入框内&#xff0c;可以输入任何命令。1.2 开发时&#xff0c;我们需要经常查阅 Go 语言官方文档&#xff0c;可惜因国内访问外网不稳定&#xff0…

STM32开启停止模式,用外部中断唤醒程序运行

今天学习了一下STM32的停止模式&#xff0c;停止模式下&#xff0c;所有外设的时钟和CPU的电源都会被关闭&#xff0c;所以会很省电&#xff0c;打破这种停止模式的方式就是外部中断可以唤醒停止模式。要想实现这个功能&#xff0c;其实设置很简单的&#xff0c;总共就需要两步…

《C语言深度解剖》(10):数组指针、指针数组和数组指针数组

&#x1f921;博客主页&#xff1a;醉竺 &#x1f970;本文专栏&#xff1a;《C语言深度解剖》《精通C指针》 &#x1f63b;欢迎关注&#xff1a;感谢大家的点赞评论关注&#xff0c;祝您学有所成&#xff01; ✨✨&#x1f49c;&#x1f49b;想要学习更多C语言深度解剖点击专栏…

情感类ppt素材

小清新手绘插画风毕业季毕业相册同学录画册纪念册PPT下载 - 觅知网这是一张关于清新毕业相册的PPT模板&#xff0c;清新风格设计&#xff0c;加上风为装饰元素&#xff0c;包含毕业相册、毕业季、毕业、同学、纪念等主题内容&#xff0c;也可用作毕业相册PPT、毕业季PPT、毕业P…

陪诊小程序:温情陪伴,就医无忧

在快节奏的现代生活中&#xff0c;健康问题时常困扰着我们。每当身体出现不适&#xff0c;前往医院就诊便成为了一项必要的任务。然而&#xff0c;面对陌生的医院环境、繁琐的就诊流程&#xff0c;许多人往往会感到无助和困惑。此时&#xff0c;一款贴心的陪诊小程序便显得尤为…

国内首个图计算平台团体标准发布,创邻科技参与编撰

2024年&#xff0c;由中国通信标准协会批准的团体标准《大数据 图计算平台技术要求与测试方法》&#xff08;编号&#xff1a;T/CCSA 470—2023&#xff09;&#xff08;下称&#xff1a;标准&#xff09;正式实施。该标准于1月4日在全国团体标准信息平台&#xff08;https://w…

AI系列:大语言模型的RAG(检索增强生成)技术(上)

前言 大型语言模型&#xff08;LLM&#xff09;虽然在生成文本方面表现出色&#xff0c;但仍然存在一些局限性&#xff1a;数据是静态的&#xff0c;而且缺乏垂直细分领域的知识。为了克服这些限制&#xff0c;有时候会进行进一步的模型训练和微调。在实际应用中&#xff0c;我…

在Android中,如何通过Kotlin协程处理多个API调用

在Android中&#xff0c;如何通过Kotlin协程处理多个API调用 在Android开发中&#xff0c;如何使用Kotlin协程处理多个API调用的示例呢&#xff1f;假设我们已经对Kotlin协程有了一定的了解&#xff0c;包括定义、简单用例和示例等。现在&#xff0c;让我们来看一些真实的Andr…

如何下载钉钉群直播回放:完整步骤解析

在当今快节奏的商业和教育环境中&#xff0c;钉钉群直播已经成为了沟通和学习的重要工具。直播结束后&#xff0c;很多观众都希望回顾内容&#xff0c;但却不知如何开始。如果你错过了实时直播&#xff0c;或者只是想再次观看精彩的演讲和讨论&#xff0c;那么下载钉钉群直播回…

常见的数据结构,附带图解

概述 数据结构是指计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 常见数据结构&#xff1a;栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树... 栈 后进先出、先进后出 队列 先进先出&#xff0c;后进后出 数组 查询速度快…

Spark01 —— Spark基础

文章目录 Spark01 —— Spark基础一、为什么选择Spark&#xff1f;1.1 MapReduce编程模型的局限性1.2 Spark与MR的区别1.3 版本1.4 优势1.5 Spark其他知识1、多种运行模式2、技术栈3、spark-shell&#xff1a;Spark自带的交互式工具4、Spark服务 二、Spark的基础配置三、Spark实…

【蓝桥杯省赛真题42】python独立海域 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

目录 python独立海域 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python独立海域 第十三届蓝桥杯青少年组python省赛真题 一、题目要求 &…

【Java--数据结构】链表经典OJ题详解(下)

前言 上一篇 欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 前言 链表分割 链表的回文结构 相交链表 环形链表 链表分割 编写代码&#xff0c;以给定值x为基准将链表分割成两部分&#xff0c;所有小于x的结点排在…

品深茶的抗癌效果怎么样?

茶叶中的一些成分&#xff0c;如茶多酚、儿茶素等&#xff0c;具有抗氧化和抗炎作用&#xff0c;这些作用在一定程度上可以抑制癌细胞的生长和扩散。 然而&#xff0c;这些成分在茶叶中的含量和生物利用率会受到多种因素的影响&#xff0c;如茶叶的品种、制作工艺、饮茶方式等…

【Redis 开发】Lua语言

Lua Lua语法 Lua语法 Lua是一种小巧的脚本语言&#xff0c;底层用C语言实现&#xff0c;为了嵌入式应用程序中 官网&#xff1a;https://www.lua.org/ 创建lua文件 touch hello.lua 运行lua文件 lua hello.lua 输出语句 print("Hello World!")数据类型 可以通过t…

idea常用知识点随记

idea常用知识点随记 1. 打开idea隐藏的commit窗口2. idea中拉取Git分支代码3. idea提示代码报错&#xff0c;项目编译没有报错4. idea中实体类自动生成序列号5. idea隐藏当前分支未commit代码6. idea拉取新建分支的方法 1. 打开idea隐藏的commit窗口 idea左上角File→Settings…

java连锁美业收银系统源码-美业SaaS系统【微信小程序端】功能及应用场景介绍

博弈美业管理系统源码 连锁多门店美业收银系统源码 多门店管理 / 会员管理 / 预约管理 / 排班管理 / 商品管理 / 促销活动 PC管理后台、手机APP、iPad APP、微信小程序 &#xff08; 需要系统演示视频可联系观看 &#xff09; ▶ 顾客微信小程序端&#xff1a; 场景名称 场…

React配置@别名路径配置

1. 背景知识 路径解析配置&#xff08;webpack&#xff09;&#xff0c;把 / 解析为 src/路径联想配置&#xff08;VsCode&#xff09;&#xff0c;VsCode 在输入 / 时&#xff0c;自动联想出来对应的 src/下的子级目录 2. 路径解析配置 配置步骤&#xff1a; 安装craco npm …

利用Seaborn实现高级统计图表—python可视化

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 利用 Seaborn 实现高级统计图表 在数据可视化领域&#xff0c;Seaborn 是 Python 中一个备…