欢迎来到天天文库
浏览记录
ID:39774360
大小:415.60 KB
页数:10页
时间:2019-07-11
《世界名画陈列馆问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、世界名画陈列馆问题(不重复监视)主讲人:张伟海世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。★问题描述基本思想设陈列馆由m*n个陈列室组成,因为不存在重复监视,所以很多情况下都无解,我们采用的做法是根据m和n的值进行分类讨论。首先,先比较m、n大小,使m始终大于n,方面程序书写。分三种情况讨论:n=1这时
2、可以直接写出最优解:当mmod3=1时,将哨位置于(1,3k+1);当mmod3=0或2时,将哨位置于(2,3k+2),其中k=0、1、…、【m/3】。n=2这种情形下必须2端分别设置2个哨位,他们各监视三个陈列室。那么当m为偶数时问题就无解了。当m为奇数时,将哨位分别至于(1,4k+3)和(2,4k+1),k=0、1、…、【m/4】。n>2容易验证当n=3,m=3和n=3,m=4时无解,n=4,m=4有解。设置哨位时,允许在的n+1行和m+1列设置哨位,但不要求的第n+1行和m+1列陈列室受到监视,那么当n>=3且m>=5时在不重复监视下有解那么n=3,m=5的不可重复
3、监视问题一定有解。但是通过验证n=3,m=5的不可重复监视哨位设置问题无解,那么当n>=3且m>=5时在不重复监视下无解。通过以上讨论就将所有情况分析完全了,简单写一个包含多个条件判断的程序就可以实现该算法。哪里不懂,点哪里?#includeusingnamespacestd;voidmain(){intn,m,k;cout<<"设陈列馆由m*n个陈列室组成,请分别输入m和n:"<>n;cout<<"m=";cin>>m;if(n>m){k=n;n=m;m=k;}if(n==1){if(m%3==0)k=m/3
4、;elsek=m/3+1;}else{if(n==2){if(m%2==1)k=(m-3)/2+2;else{cout<<"NoSolution!";k=0;}}if(k!=0)cout<=3&&m>=5){cout<<"NoSolution!";k=0;}}}}验证n=1时当mmod3=1当mmod3=0或2谢谢!
此文档下载收益归作者所有