1、
题目:
问题描述:在某操作系统中打开了 N 个窗口,每个窗口都是一个矩形区域。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。现在我们希望你写一个程序模拟点击窗口的过程
算法思想:
由于在某一次点开的网页所在的层数我们是不知道的,因此这道题并不方便采用栈或者队列,由于这里涉及到了较多的删除,插入操作,所以最终我决定采用链表来处理这道题,我用了一个链表来进行网页的存储,链表里面包含了网页的层数和位置信息,然后我们来用遍历的方式来判断点击的网页,如果找到了点击的网页,那么我们就将这个网页先从链表中拆下来,然后插入到头节点后面,如果点击的位置没有对应的网页,那么我们就输出IGNORED。
当然我们的输出没有阳按照老师的样例程序进行,因为考虑到,我们在输入信息时,需要一些提示性信息,比如,"请输入网页数量N,和操作次数M: ","请依次输入x1,y1,x2,y2: \n"等等。
我们算法的空间复杂度为:O(n),因为取决于我们所输入的网页的数量n,我们算法的时间复杂度为:O(mn),因为每一次操作都需要遍历这个链表,一共有m次操作,那么最坏的情况就是每一次都是需要完全遍历,那么就是需要比较次mn,因此们算法的时间复杂度为:O(mn)
运行结果:
结果分析:
结果是正确的,除了我的输出结果有一些提示性信息以外,都和老师的要求是吻合的,当然这些提示性信息并不影响。
附源程序:
#include "stdlib.h"
#include "math.h"
#include "stdio.h"
typedef struct node
{
int x1;
int y1;
int x2;
int y2;
int num; //网页的编号
struct node *next;
}LI;
void Get_page(LI *T,int x,int y); //输入链表T,鼠标点击位置x,y得到应该的网页编号,并且改变他的位置
main()
{
LI *A,*q;
int x1,x2,y1,y2; //给网页赋值
int N,M,i; //N为网页数量,M为操作次数,i用来生成N个网页以及遍历所有鼠标点击位置
int x,y; //鼠标点击的位置
A = (LI*)malloc(sizeof(LI));
A->next = NULL;
printf("请输入网页数量N,和操作次数M: ");
scanf("%d%d",&N,&M);
for(i = 1;i <= N; i++)
{
q = (LI*)malloc(sizeof(LI));
printf("请依次输入x1,y1,x2,y2: \n");
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>=x2)
{
printf("x2要比x1大!\n");
exit(0);
}
else if(y1>=y2)
{
printf("y2要比y1大!\n");
exit(0);
}
else
{
printf(" \"上方是编号为%d的窗口\"\n",i);
q->x1 = x1;
q->x2 = x2;
q->y1 = y1;
q->y2 = y2;
q->num = i;
}
q->next = A->next;
A->next = q;
}
for(i = 1;i <=M ;i++)
{
printf("请输入鼠标点击位置x,y: ");
scanf("%d%d",&x,&y);
Get_page(A,x,y);
}
}
void Get_page(LI *T,int x,int y)
{
LI *p,*p1;
LI *q;
p1 = T;
p = p1->next;
while(p)
{
if((x >= p->x1 )&&(x <= p->x2 )&&(y >= p->y1 )&&(y <= p->y2 ))
{
printf("%d\n",p->num);
q = p;
p1->next = p->next;
q->next = T->next;
T->next = q;
break;
}
else
{
p1 = p;
p = p->next;
}
}
if(p == NULL)
printf("IGNORED");
}
2、
题目:
利用栈模拟实现N个盘子的汉诺塔问题(非递归算法实现)
算法思想:
1、将1号盘子按照顺时针顺序从当前栈移动到下一个栈(从当前站pop,然后push进下一个栈),sum++,如果sum已经等于,结束;
2、观察没有1号盘子的那两个栈
-如果其中一个为空,那么将另一个非空栈的栈顶盘子移动到这个空栈 上;
-如果两个都不,那么看谁的栈顶的盘子比较小把小盘子移动到栈顶盘子较大的那个栈上;
-之后,sum++,如果sum已经达到数量,结束.否则继续执行第1步
总的思路很简单,就是按照老师ppt上面给的思路写就行了,因为有了老师的思路,所以没有什么难度。空间复杂度为:O(n),取决于汉诺塔中圆盘的数量,算法的时间复杂度为:O(2的n次方),因为我们需要对其中的圆盘进行次2^n-1的移动。
运行结果:
N = 2;
N = 3
N = 4
结果分析:
结构运行非常正确,而且在不是很大的前提下,我们速度还是可以的,但是由于我们的算法的时间复杂度为:,所以当较大时,算法还是比较慢的。
附源程序:
void hanio(ST *T,int n)//移动盘子的时候要输出将几号盘子从哪儿移动到了哪儿
{
int sum=0,k=pow(2,n)-1,i=0;
while(1)
{
sum++;
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[i%3]),T[i].name,T[(i+1)%3].name);
push(&T[(i+1)%3],pop(&T[i]));
i = (i+1)%3;
if (sum==k)
break;
sum++;
if (isempty(&T[(i+1)%3]))
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+2)%3]),T[(i+2)%3].name,T[(i+1)%3].name);
push(&T[(i+1)%3],pop(&T[(i+2)%3]));
}
else if (isempty(&T[(i+2)%3]))
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+1)%3]),T[(i+1)%3].name,T[(i+2)%3].name);
push(&T[(i+2)%3],pop(&T[(i+1)%3]));
}
else if (gettop(&T[(i+1)%3])<gettop(&T[(i+2)%3]))
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+1)%3]),T[(i+1)%3].name,T[(i+2)%3].name);
push(&T[(i+2)%3],pop(&T[(i+1)%3]));
}
else
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+2)%3]),T[(i+2)%3].name,T[(i+1)%3].name);
push(&T[(i+1)%3],pop(&T[(i+2)%3]));
}
}
}
题目:(关于迷宫四个情况判断的写法是在王铭宇同学的帮助下写出来的,因为在写这道题的时候还没有讲队列和这种题目的思路,所以询问了他人,但是现在我可以自己独立写出来了)
根据给定的迷宫入口和出口位置,利用队列,输出迷宫中的所有最短路径,以及路径长度(路径中包含的点的数量)
算法思想:
我用队列来寻找最短路径,我的队列中存储点的坐标,以及该队列的头部和尾部,让后开始从初始位置开始走,他有四个方向可以选择,我们就把可行的都存到队列中去,然后找出最先到达目标位置的,然后我们之前用了一共数组来存储每一步的上一步的标号,我们只需要遍历一下这个数组就可以得到我们的最短路径了。由于我们需要存储我们的位置坐标,而他们的数量由点的个数来确定,所以我们的空间复杂度为:O(n2),我们的时间复杂度为:O(n2),因为可能会遍历迷宫中所有的点。
运行结果:
结果分析:
运行结果是正确的,就是我们的最短路径,我所采用的算法可以找到这条最短路径,但是存在一共问题,就是如果最短路径不唯一,那么我们如何找到所有的最短路径呢,我想我们可以用栈来解决,由于这道题要求是队列,所以就不往下考虑了。
附源代码:
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define start_x 1//入口行号
#define start_y 1//入口列号
#define end_x 8//出口行号
#define end_y 8//出口列号
#define N 100
int mg[10][10]={
{
1,1,1,1,1,1,1,1,1,1},
{
1,0,0,1,0,0,0,1,0,1},
{
1,0,0,1,0,0,0,1,0,1},
{
1,0,0,0,0,1,1,0,0,1},
{
1,0,1,1,1,0,0,0,0,1},
{
1,0,0,0,1,0,0,0,0,1},
{
1,0,1,0,0,0,1,0,0,1},
{
1,0,1,1,1,0,1,1,0,1},
{
1,1,0,0,0,0,0,0,0,1},
{
1,1,1,1,1,1,1,1,1,1},
};//用二维数组表示迷宫,“0”表示该点可行,“1”表示该点不可行
typedef struct queue
{
int x[N],y[N];
int front;
int rear;
}MG;
void initial(MG *M); //初始化队列MG
void Queue(MG *M);
void Push(MG *M,int i,int j); //入队操作
void show(int a[],int b[],int n);
int main()
{
MG M; //队列
initial(&M);
Queue(&M);
}
void initial(MG *M)
{
M->x[0]=start_x;
M->y[0]=start_y;
M->front=0;
M->rear=M->front+1;
mg[start_x][start_y]=1;
}
void Push(MG *M,int i,int j)
{
if(M->front==(M->rear+1))
{
printf("队列已经满了,不能再插入数据!");
exit(0);
}
M->x[M->rear]=i;
M->y[M->rear]=j;
M->rear++;
}
void Queue(MG *M)
{
int i,j,i1,j1; //i,j来遍历整个迷宫;i1,j1用来判断行走的四个方向
int next,step=-1,active=0;
int save_x[N],save_y[N]; //保存路径
for(i=start_x,j=start_y;i!=end_x || j!=end_y;)
{
if(step==-1 || active!=0)
M->front=M->rear; //第一步和上一步寻找到可行点时更新队头元素
active=0;
if(save_x[step]!=i || save_y[step]!=j) //当此时的路径与上一步的路径不一样时保存路径
{
step++;
save_x[step]=i;
save_y[step]=j;
}
else //否则说明上一步路径出错,删除上一步的路径
step--;
for(next=0;next<4;next++)
{
switch(next)
{
case 0: //向前
i1=i;
j1=j+1;
break;
case 1: //向后
i1=i;
j1=j-1;
break;
case 2: //向上
j1=j;
i1=i-1;
break;
case 3: //向下
j1=j;
i1=i+1;
break;
}
if(mg[i1][j1]==0) //某个方向可行时将其加入队列
{
Push(M,i1,j1);
mg[i1][j1]=1;
active=1;
}
}
if(active==1) //若有可行方向则选取最后一个可行方向前进
{
i=M->x[(M->rear)-1];
j=M->y[(M->rear)-1];
}
else //未找到可行方向就将队头回溯到上一条路径
{
M->front--;
i=M->x[M->front];
j=M->y[M->front];
}
}
step++;
save_x[step]=end_x; //最后将出口加入队列
save_y[step]=end_y;
step++;
show(save_x,save_y,step);
}
void show(int a[],int b[],int n)
{
int i;
printf("走出迷宫的最短路径为:\n");
for(i=0;i<n;i++)
{
printf("(%d,%d) ",a[i],b[i]);
if(i<n-1)
printf("-->");
}
printf("\n结点数为%d",n);
printf("\n\n");
}
文章浏览阅读3.2k次。本文研究全球与中国市场分布式光纤传感器的发展现状及未来发展趋势,分别从生产和消费的角度分析分布式光纤传感器的主要生产地区、主要消费地区以及主要的生产商。重点分析全球与中国市场的主要厂商产品特点、产品规格、不同规格产品的价格、产量、产值及全球和中国市场主要生产商的市场份额。主要生产商包括:FISO TechnologiesBrugg KabelSensor HighwayOmnisensAFL GlobalQinetiQ GroupLockheed MartinOSENSA Innovati_预计2026年中国分布式传感器市场规模有多大
文章浏览阅读1.1k次,点赞2次,收藏12次。常用组合逻辑电路结构——为IC设计的延时估计铺垫学习目的:估计模块间的delay,确保写的代码的timing 综合能给到多少HZ,以满足需求!_基4布斯算法代码
文章浏览阅读3.3k次,点赞3次,收藏5次。OpenAI Manager助手(基于SpringBoot和Vue)_chatgpt网页版
文章浏览阅读2.2k次。USACO自1992年举办,到目前为止已经举办了27届,目的是为了帮助美国信息学国家队选拔IOI的队员,目前逐渐发展为全球热门的线上赛事,成为美国大学申请条件下,含金量相当高的官方竞赛。USACO的比赛成绩可以助力计算机专业留学,越来越多的学生进入了康奈尔,麻省理工,普林斯顿,哈佛和耶鲁等大学,这些同学的共同点是他们都参加了美国计算机科学竞赛(USACO),并且取得过非常好的成绩。适合参赛人群USACO适合国内在读学生有意向申请美国大学的或者想锻炼自己编程能力的同学,高三学生也可以参加12月的第_usaco可以多次提交吗
文章浏览阅读394次。1.1 存储程序1.2 创建存储过程1.3 创建自定义函数1.3.1 示例1.4 自定义函数和存储过程的区别1.5 变量的使用1.6 定义条件和处理程序1.6.1 定义条件1.6.1.1 示例1.6.2 定义处理程序1.6.2.1 示例1.7 光标的使用1.7.1 声明光标1.7.2 打开光标1.7.3 使用光标1.7.4 关闭光标1.8 流程控制的使用1.8.1 IF语句1.8.2 CASE语句1.8.3 LOOP语句1.8.4 LEAVE语句1.8.5 ITERATE语句1.8.6 REPEAT语句。_mysql自定义函数和存储过程
文章浏览阅读188次。半导体二极管——集成电路最小组成单元。_本征半导体电流为0
文章浏览阅读2.8k次,点赞3次,收藏18次。游戏水面特效实现方式太多。咱们这边介绍的是一最简单的UV动画(无顶点位移),整个mesh由4个顶点构成。实现了水面效果(左图),不动代码稍微修改下参数和贴图可以实现岩浆效果(右图)。有要思路是1,uv按时间去做正弦波移动2,在1的基础上加个凹凸图混合uv3,在1、2的基础上加个水流方向4,加上对雾效的支持,如没必要请自行删除雾效代码(把包含fog的几行代码删除)S..._unity 岩浆shader
文章浏览阅读5k次。广义线性模型是线性模型的扩展,它通过连接函数建立响应变量的数学期望值与线性组合的预测变量之间的关系。广义线性模型拟合的形式为:其中g(μY)是条件均值的函数(称为连接函数)。另外,你可放松Y为正态分布的假设,改为Y 服从指数分布族中的一种分布即可。设定好连接函数和概率分布后,便可以通过最大似然估计的多次迭代推导出各参数值。在大部分情况下,线性模型就可以通过一系列连续型或类别型预测变量来预测正态分布的响应变量的工作。但是,有时候我们要进行非正态因变量的分析,例如:(1)类别型.._广义线性回归模型
文章浏览阅读69次。环境保护、 保护地球、 校园环保、垃圾分类、绿色家园、等网站的设计与制作。 总结了一些学生网页制作的经验:一般的网页需要融入以下知识点:div+css布局、浮动、定位、高级css、表格、表单及验证、js轮播图、音频 视频 Flash的应用、ul li、下拉导航栏、鼠标划过效果等知识点,网页的风格主题也很全面:如爱好、风景、校园、美食、动漫、游戏、咖啡、音乐、家乡、电影、名人、商城以及个人主页等主题,学生、新手可参考下方页面的布局和设计和HTML源码(有用点赞△) 一套A+的网_垃圾分类网页设计目标怎么写
文章浏览阅读614次,点赞7次,收藏11次。之前找到一个修改 exe 中 DLL地址 的方法, 不太好使,虽然能正确启动, 但无法改变 exe 的工作目录,这就影响了.Net 中很多获取 exe 执行目录来拼接的地址 ( 相对路径 ),比如 wwwroot 和 代码中相对目录还有一些复制到目录的普通文件 等等,它们的地址都会指向原来 exe 的目录, 而不是自定义的 “lib” 目录,根本原因就是没有修改 exe 的工作目录这次来搞一个启动程序,把 .net 的所有东西都放在一个文件夹,在文件夹同级的目录制作一个 exe._.net dll 全局目录
文章浏览阅读1.5k次。本文为转载,原博客地址:http://blog.csdn.net/hujingshuang/article/details/46910259简介 BRIEF是2010年的一篇名为《BRIEF:Binary Robust Independent Elementary Features》的文章中提出,BRIEF是对已检测到的特征点进行描述,它是一种二进制编码的描述子,摈弃了利用区域灰度..._breif description calculation 特征点
文章浏览阅读4.1k次,点赞21次,收藏79次。本文是《基于SpringBoot的房屋租赁管理系统》的配套原创说明文档,可以给应届毕业生提供格式撰写参考,也可以给开发类似系统的朋友们提供功能业务设计思路。_基于spring boot的房屋租赁系统论文