首页 考试吧论坛 Exam8视线 考试商城 网络课程 模拟考试 考友录 实用文档 求职招聘 论文下载
2011中考 | 2011高考 | 2012考研 | 考研培训 | 在职研 | 自学考试 | 成人高考 | 法律硕士 | MBA考试
MPA考试 | 中科院
四六级 | 职称英语 | 商务英语 | 公共英语 | 托福 | 雅思 | 专四专八 | 口译笔译 | 博思 | GRE GMAT
新概念英语 | 成人英语三级 | 申硕英语 | 攻硕英语 | 职称日语 | 日语学习 | 法语 | 德语 | 韩语
计算机等级考试 | 软件水平考试 | 职称计算机 | 微软认证 | 思科认证 | Oracle认证 | Linux认证
华为认证 | Java认证
公务员 | 报关员 | 银行从业资格 | 证券从业资格 | 期货从业资格 | 司法考试 | 法律顾问 | 导游资格
报检员 | 教师资格 | 社会工作者 | 外销员 | 国际商务师 | 跟单员 | 单证员 | 物流师 | 价格鉴证师
人力资源 | 管理咨询师考试 | 秘书资格 | 心理咨询师考试 | 出版专业资格 | 广告师职业水平
驾驶员 | 网络编辑
卫生资格 | 执业医师 | 执业药师 | 执业护士
会计从业资格考试会计证) | 经济师 | 会计职称 | 注册会计师 | 审计师 | 注册税务师
注册资产评估师 | 高级会计师 | ACCA | 统计师 | 精算师 | 理财规划师 | 国际内审师
一级建造师 | 二级建造师 | 造价工程师 | 造价员 | 咨询工程师 | 监理工程师 | 安全工程师
质量工程师 | 物业管理师 | 招标师 | 结构工程师 | 建筑师 | 房地产估价师 | 土地估价师 | 岩土师
设备监理师 | 房地产经纪人 | 投资项目管理师 | 土地登记代理人 | 环境影响评价师 | 环保工程师
城市规划师 | 公路监理师 | 公路造价师 | 安全评价师 | 电气工程师 | 注册测绘师 | 注册计量师
缤纷校园 | 实用文档 | 英语学习 | 作文大全 | 求职招聘 | 论文下载 | 访谈 | 游戏
您现在的位置: 考试吧(Exam8.com) > 计算机等级考试 > 计算机二级 > C语言 > 实例编程 > 正文

2011年计算机等级考试二级C辅导实例编程(20)

来源:考试吧Exam8.com) 2010-12-26 14:05:37 考试吧:中国教育培训第一门户 模拟考场
考试吧整理了2011年计算机等级考试二级C辅导实例编程,帮助考生备考。

  最小圆覆盖 随机增量算法

  最小圆覆盖。神奇的随机算法。当点以随机的顺序加入时期望复杂度是线性的。

  ------------------------------------------------------------------------------------

  algorithm:

  A、令Ci表示为前i个点的最小覆盖圆。当加入新点pi时如果pi不在Ci-1里那么pi必定在Ci的边界上。

  B、再从新考虑这样一个问题,Ci为前i个点最小覆盖圆且p在Ci的的边界上!同理加入新点pi时如果p

  i不在Ci-1里那么pi必定在Ci的边界上。这时我们就包含了两个点在这个最小圆的边界上。

  C、再从新考虑这样一个问题,Ci为前i个点最小覆盖圆且有两个确定点再边界上!此时先让

  O(N)的方法能够判定出最小圆。

  ------------------------------------------------------------------------------------

  analysis:

  现在来分析为什么是线性的。

  C是线性的这是显然的。

  B<-C的过程中。考虑pi 他在园内的概率为 (i-1)/i 。在圆外的概率为 1/i 所以加入pi的期望复杂度为:(1-i)/i*O(1) +(1/i)*O(i) {前者在园内那么不进入C,只用了O(1)。后者进入C用了O(i)的时间}这样分析出来,复杂度实际上仍旧

  是线性的。

  A<-B的过程中。考虑方法相同,这样A<-B仍旧是线性。于是难以置信的最小圆覆盖的复杂度变成了线性的。

  -------------------------------------------------------------------------------------

  下面的程序没有先将点随机化,因为数据通常也是随机的= =!

  1

  2 #include

  3 #include

  4 #include

  5 using namespace std;

  6 struct node{

  7 double x,y;

  8 };

  9 int n;

1 2 3 下一页
  相关推荐:

  2011计算机等级考试二级C辅导实例编程汇总

  计算机等级考试二级C语言历年真题汇总(2005-2010)

  2011年计算机等级考试二级C语言常见问题汇总

  计算机等级考试二级C语言常见知识点总结

文章搜索
版权声明:如果计算机等级考试网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本计算机等级考试网内容,请注明出处。