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");
}
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下:http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态:[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
文章浏览阅读1.3w次,点赞45次,收藏99次。我个人用的是anaconda3的一个python集成环境,自带jupyter notebook,但在我打开jupyter notebook界面后,却找不到对应的虚拟环境,原来是jupyter notebook只是通用于下载anaconda时自带的环境,其他环境要想使用必须手动下载一些库:1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
文章浏览阅读5.2k次,点赞19次,收藏28次。选择scoop纯属意外,也是无奈,因为电脑用户被锁了管理员权限,所有exe安装程序都无法安装,只可以用绿色软件,最后被我发现scoop,省去了到处下载XXX绿色版的烦恼,当然scoop里需要管理员权限的软件也跟我无缘了(譬如everything)。推荐添加dorado这个bucket镜像,里面很多中文软件,但是部分国外的软件下载地址在github,可能无法下载。以上两个是官方bucket的国内镜像,所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
文章浏览阅读4.5k次,点赞2次,收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了,例如:这里的:sty..._vue el-color-picker
文章浏览阅读640次。基于芯片日益增长的问题,所以内核开发者们引入了新的方法,就是在内核中只保留函数,而数据则不包含,由用户(应用程序员)自己把数据按照规定的格式编写,并放在约定的地方,为了不占用过多的内存,还要求数据以根精简的方式编写。boot启动时,传参给内核,告诉内核设备树文件和kernel的位置,内核启动时根据地址去找到设备树文件,再利用专用的编译器去反编译dtb文件,将dtb还原成数据结构,以供驱动的函数去调用。firmware是三星的一个固件的设备信息,因为找不到固件,所以内核启动不成功。_exynos 4412 刷机
文章浏览阅读2w次,点赞24次,收藏42次。Linux系统配置jdkLinux学习教程,Linux入门教程(超详细)_linux配置jdk
文章浏览阅读3.3k次,点赞5次,收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图:_matlab微米怎么输入
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件,可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中,对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数,而关闭则使用fclose函数。在C语言中,可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量:7 ️文章类型:【 C语言程序设计 】在C语言中,用于打开文件的函数是____,用于关闭文件的函数是____。
文章浏览阅读3.4k次,点赞2次,收藏13次。跟随鼠标移动的粒子以grid(SOP)为partical(SOP)的资源模板,调整后连接【Geo组合+point spirit(MAT)】,在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in(CHOP)鼠标位置到metaball的坐标,实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
文章浏览阅读178次。项目运行环境配置:Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX(Webstorm也行)+ Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。项目技术:Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成,B/S模式 + Maven管理等等。环境需要1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多,会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析,后面会慢慢更新。另外,博客只作为自己学习记录的一种方式,对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
文章浏览阅读2.4k次,点赞41次,收藏13次。java 数据结构与算法 ——快速排序法_快速排序法