123
返回列表 发帖
班超

Rank: 9Rank: 9Rank: 9

积分
21770 
威望
3067  
金钱
4  
阅读权限
100 
在线时间
2779 小时 
1# 跳转到 » 正序看帖
打印
tT
发表于 2006-12-19 19:08 | 只看该作者

[其他] 猜谜！

波恩大学某系办公楼的平面图是不规则的多边形，多边形内部无障碍。
如果要在楼里安装摄像头监视该平面内所有地方，无论这个多边形多复杂，安几个摄像头肯定够用？？？

[ 本帖最后由 班超 于 2006-12-20 08:37 编辑 ]
收藏 分享
Share |
Share

Klein_Yu

Rank: 8Rank: 8

积分
8776 
威望
609  
金钱
0  
阅读权限
90 
性别
男 
来自
HZ 
在线时间
1437 小时 
30#
发表于 2006-12-25 00:22 | 只看该作者
答案好像有点问题哦！如果是一个正六边形，只要在中心点放置一个摄像头就可以了。那么，n/3就好象不对了。

TOP

班超

Rank: 9Rank: 9Rank: 9

积分
21770 
威望
3067  
金钱
4  
阅读权限
100 
在线时间
2779 小时 
29#
发表于 2006-12-21 23:17 | 只看该作者

哦

原帖由 qquchn 于 2006-12-21 22:27 发表
你这是最坏情况还是 平均？


Fuer Ein einfaches Polygon mit n Ecken kommen stets n/3 (beschraekt nach unten) Waechter aus.

TOP

qquchn

Rank: 6Rank: 6

积分
43492 
威望
9279  
金钱
8  
阅读权限
150 
来自
Bonn 
在线时间
3551 小时 
28#
发表于 2006-12-21 22:27 | 只看该作者
你这是最坏情况还是 平均？
末世征象：地震 粮荒 战争 瘟疫 世界四分五裂

TOP

班超

Rank: 9Rank: 9Rank: 9

积分
21770 
威望
3067  
金钱
4  
阅读权限
100 
在线时间
2779 小时 
27#
发表于 2006-12-21 17:03 | 只看该作者

ok

n/3 beschränk nach unten

TOP

dongfeng71

Rank: 7Rank: 7Rank: 7

积分
4917 
威望
706  
金钱
1  
阅读权限
80 
在线时间
610 小时 
26#
发表于 2006-12-20 23:38 | 只看该作者
快给答案，快给答案！

TOP

班超

Rank: 9Rank: 9Rank: 9

积分
21770 
威望
3067  
金钱
4  
阅读权限
100 
在线时间
2779 小时 
25#
发表于 2006-12-20 22:00 | 只看该作者

ha

原帖由 qquchn 于 2006-12-20 21:20 发表
你的题目是至少多少摄像头，而n/2肯定不是最优解 这只是最坏情况下的解 还应当给出约束 如果平面图只有矩形 则N/4 下取整


你的思路加上楼上的思路就差不多了，现在只缺一个答案！

TOP

qquchn

Rank: 6Rank: 6

积分
43492 
威望
9279  
金钱
8  
阅读权限
150 
来自
Bonn 
在线时间
3551 小时 
24#
发表于 2006-12-20 21:20 | 只看该作者
你的题目是至少多少摄像头，而n/2肯定不是最优解 这只是最坏情况下的解 还应当给出约束 如果平面图只有矩形 则N/4 下取整
末世征象：地震 粮荒 战争 瘟疫 世界四分五裂

TOP

班超

Rank: 9Rank: 9Rank: 9

积分
21770 
威望
3067  
金钱
4  
阅读权限
100 
在线时间
2779 小时 
23#
发表于 2006-12-20 20:43 | 只看该作者

en

原帖由 chinesehejing 于 2006-12-20 18:33 发表
n/2或n/2+1


接近了。

TOP

qquchn

Rank: 6Rank: 6

积分
43492 
威望
9279  
金钱
8  
阅读权限
150 
来自
Bonn 
在线时间
3551 小时 
22#
发表于 2006-12-20 19:24 | 只看该作者
你这个答案有点不靠谱
末世征象：地震 粮荒 战争 瘟疫 世界四分五裂

TOP

123
返回列表