《世界名画陈列馆问题.ppt》由会员分享，可在线阅读，更多相关《世界名画陈列馆问题.ppt（10页珍藏版）》请在三一文库上搜索。
1、世界名画陈列馆问题,(不重复监视) 主讲人：张伟海,世界名画陈列馆由mn个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。 试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。,问题描述,基本思想,设陈列馆由m*n个陈列室组成,因为不存在重复监视，所以很多情况下都无解，我们采用的做法是根据 m和n的值进行分类讨论。首先，先比较m、n大小，使 m始终大于n，方面程序书写。 分三种情况讨论： n1 这时可
2、以直接写出最优解： 当m mod 31时，将哨位置于（1，3k1）； 当m mod 30或2时，将哨位置于（2，3k2），其中k0、1、【m/3】。 n2 这种情形下必须2端分别设置2个哨位，他们各监视三个陈列室。那么当m为偶数时问题就无解了。,当m为奇数时，将哨位分别至于（1，4k3）和（2，4k1），k0、1、【m/4】。 n2 容易验证 当n3，m3和n3，m4时无解，n4，m4有解。 设置哨位时，允许在的n1行和m1列设置哨位，但不要求的第n1行和m1列陈列室受到监视，那么当n=3且m=5时在不重复监视下有解那么n3，m5的不可重复监视问题一定有解。但是通过验证n3，m5的不可重复监视
3、哨位设置问题无解，那么当n=3且m=5时在不重复监视下无解。 通过以上讨论就将所有情况分析完全了，简单写一个包含多个条件判断的程序就可以实现该算法。,哪里不懂，点哪里?,#include using namespace std; void main () int n,m,k; coutn; coutm; if(nm) k=n; n=m; m=k; ,if(n=1) if(m%3=0) k=m/3; else k=m/3+1; else if(n=2) if(m%2=1)k=(m-3)/2+2; else cout“No Solution!“;k=0; ,if (k!=0) cout kendl ; system(“pause“); ,else if(n=3) cout=3 ,验证,n=1时 当m mod 31 当m mod 30或2,谢谢！,