SeventhExper.zip

  • 长庚123
    了解作者
  • C/C++
    开发工具
  • 2.2MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-09-27 08:10
    上传日期
卫兵布置问题。一个博物馆由排成m*n个矩形阵列的陈列室组成,需要在陈列室中设立哨位,每个哨位上的哨兵除了可以监视自己所在陈列室外,还可以监视他上、下、左、右四个陈列室,试给出一个最佳哨位安排方法,使得所有陈列室都在监视之下,但使用的哨兵最少。
SeventhExper.zip
  • .vs
  • SeventhExper
  • v15
  • .suo
    29.5KB
  • SeventhExper
  • SeventhExper.vcxproj
    3.2KB
  • SeventhExper.vcxproj.filters
    941B
  • Դ.cpp
    2.8KB
  • SeventhExper.v11.suo
    25KB
  • SeventhExper.sdf
    7.5MB
  • SeventhExper.sln
    903B
内容介绍
#include <iostream> #include <conio.h> #include <chrono> using namespace std; #define MAX 50 int m,n;//行数和列数 int Monitor[MAX+2][MAX+2]={0};//记录该位置是否被监控 int Guard[MAX+2][MAX+2]={0};//记录该位置是否有哨兵 int best;//最优哨兵数 int B;//当前哨兵数 int i=1,j=1;//控制位置从(1,1)开始 int kind=0;//记录最优解的个数 struct{int m[MAX+2][MAX+2];}T[MAX*MAX];//保存最优解 void Backtrack()//回溯 { while(i*j>1 && Guard[i][j]==1) { if(j==1) {i--;j=n;} else j--; } if(Guard[i][j]==0) { Guard[i][j]=1; Monitor[i][j]++; Monitor[i-1][j]++; Monitor[i][j-1]++; Monitor[i][j+1]++; Monitor[i+1][j]++; B++; if(j==n) { if(i==m) j++; else {j=1;i++;} } else j++; } } void Output()//输出 { cout<<"一共有"<<kind+1<<"种最优方案"<<endl; cout<<"最优哨兵数为:"<<best<<endl; for(int i=0;i<=kind;i++) { cout<<"第"<<i+1<<"种"<<endl; for(int j=1;j<=m;j++) { for(int k=1;k<=n;k++) { cout<<T[i].m[j][k]<<" "; } cout<<endl; } cout<<endl; } } void Cancelguard()//取消哨兵 { Guard[i][j]=0; Monitor[i][j]--; Monitor[i-1][j]--; Monitor[i+1][j]--; Monitor[i][j-1]--; Monitor[i][j+1]--; } void Run() { while(1) { while(i*j<=n*m) { if(i==m) { if(Monitor[i][j]-1!=0 && Monitor[i-1][j]-1!=0 && Monitor[i+1][j]-1!=0 && Monitor[i][j-1]-1!=0 && Monitor[i][j+1]-1!=0) { Cancelguard();j++;B--; } else { j++; } } else { if(Monitor[i][j]-1!=0 && Monitor[i-1][j]-1!=0 && Monitor[i+1][j]-1!=0 && Monitor[i][j-1]-1!=0 && Monitor[i][j+1]-1!=0) { Cancelguard(); if(j==n) {j = 1;i++;} else j++; B--; } else { if(j==n) {j = 1;i++;} else j++; } } } if(B<best) { best=B;kind=0; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) {T[kind].m[i][j]=Guard[i][j];} } } else if(B==best) { kind++; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) {T[kind].m[i][j]=Guard[i][j];} } } j--; Backtrack(); if(i==1 && j==1) break; } } int main() { cout<<"请输入陈列馆的行数和列数m,n:"; cin>>m>>n; B=m*n;best=m*n/3+2; for(int i=1;i<=m;i++) for (int j=1;j<=n;j++) { Guard[i][j]=1; Monitor[i][j]++; Monitor[i-1][j]++; Monitor[i][j-1]++; Monitor[i][j+1]++; Monitor[i+1][j]++; } for (int j=0;j<=n+1;j++) { Monitor[0][j]=2; Monitor[m+1][j]=2; } for (int i=0;i<=m+1;i++) { Monitor[i][0]=2; Monitor[i][n+1]=2; } auto start = std::chrono::steady_clock::now(); Run(); auto end = std::chrono::steady_clock::now(); std::chrono::duration <double, std::micro> elapsed=end-start; std::cout<< "主算法运行时间(微秒): "<<elapsed.count()<< "us" <<std::endl; Output(); getch(); return 0; }
评论
    相关推荐
    • 卫兵问题.rar
      完成算法课程作业,实现博物馆卫兵问题,仅供参考
    • 卫兵布置问题.rar
      一个算法程序作业,利用C++实现卫兵布置问题
    • WUBIAide(五笔反查).rar
      WUBIAide(五笔反查).rar
    • SIM800C_MQTT.rar
      使用SIM800C模块,使用MQTT协议,连接中国移动onenet平台,能实现数据的订阅、发布、存储等
    • android从bootloader到launcher启动流程整理
      讲述android 开机流程 从boot rom---bootloader---init--zygote---systemserver---ams 并附上自己整理的每个流程的流程图 ,清晰熟悉android 启动流程
    • matlabpam代码-dsp-library:用于光通信的MATLABDSP函数库
      matlab pam代码 DSP库 该项目包含几种不同的功能,可将DSP算法应用于光通信。 这些功能适用于相干和非相干(PAM,DMT)光通信。 大多数功能是相互独立的。 因此,该代码中的功能可以轻松使用,并与其他DSP功能结合使用。 用法 功能列表以及简短说明在文件中。 输入和输出参数的描述在每个函数的标题中。 讯号 通常,输入(和输出)信号在第一维度上具有时间(例如,列向量),而第二维度用于一次管理多个信号(例如,不同的极化,不同的参数等)。 之所以选择这种约定,是因为MATLAB通过将列保留在内存的连续部分中来存储矩阵,因此,这种约定比其他方法(行向量)要快。 参数 大多数功能使用参数结构作为输入参数。 函数中使用的参数的描述通常在标头中,而coherent-dsp函数的默认参数在文件中。 参考 执照 此代码在下发布。
    • 有关多目标跟踪的PHD滤波的一些资料
      一些关于多目标跟踪的新的文献,主要是有关概率假设密度(PHD)的
    • 基于python开发的全国新工商采集工具 v1.2版本
      这个软件是通过scrapy爬虫框架结合代理IP池再加上request模拟请求技术以及验证码识别技术,可以做到日更新采集全国新工商信息。采集的数据自动存储在mysql数据库表里,可下载全量1.8亿多企业工商基本信息和36维度的详细信息.支持sql和excel导出数据包格式。
    • 卷积神经网络
      这是卷积神经网络的一个实际用例,已经调试好了,能够在matlab上成功运行,适合从事卷积神经网络(CNN)研究的人员学习使用。
    • matlab匹配滤波代码-matlab_for_thesis:Matlab博士学位论文代码
      matlab匹配滤波代码博士论文的MATLAB代码 博士论文的MATLAB代码的一部分,“井田双色散水下声通道中的多载波通信”。 函数下的func_JingTian文件夹 FUNC_JINGTIAN包含多载波通信中一些通常需要的功能: OFDM调制/解调模块,包括几种数据辅助的信道估计方法和差分解调; 快速实现GFDM和C-FBMC调制/解调,分别包括时域和频域的迫零(ZF)和匹配滤波(MF)均衡; 为OFDM信道估计中使用的压缩感测方法计算字典的功能; 增加信道效应,施加宽带多普勒失真的功能; 通过线性调频Z变换(CZT)以任意精度对频域中的信号进行重采样; Hermite函数合成的信号之间的交叉歧义函数的计算。 演示文件夹 以下列出了四个演示 demo1:使用基本追踪(BP)算法形式的压缩感知方法对OFDM进行稀疏2-D信道估计; demo2:比较基本数据辅助OFDM信道估计算法,包括常规频域插值和基于IDFT的变换域方法; demo3:圆形滤波器组多载波(C-FBMC / OQAM)的基于DFT特征向量的原型滤波器合成; demo4:用于广义频分复用(GFDM)的辅助日期辅助无干