算法设计与分析 课件 4.1-分治法 - 引例-寻找假币_第1页
算法设计与分析 课件 4.1-分治法 - 引例-寻找假币_第2页
算法设计与分析 课件 4.1-分治法 - 引例-寻找假币_第3页
算法设计与分析 课件 4.1-分治法 - 引例-寻找假币_第4页
算法设计与分析 课件 4.1-分治法 - 引例-寻找假币_第5页
已阅读5页，还剩4页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析分治引例-寻找假币信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版已知条件：一个装有16枚硬币的袋子，其中有一枚硬币是伪造的，并且伪造的硬币比真的硬币要轻一些。工具：一台天枰，可用来比较两组硬币的重量。问题：找出这枚伪造的硬币。方法一任意取1枚硬币，与其它硬币进行比较，若发现轻者，则轻者为假币。最多可能有15次比较。123456789101112131415方法二将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为假币。最多可能有8次比较。12345678方法三第1组第2组1次比较第1组第2组1次比较第1组第2组1次比较第1组第2组1次比较共4次比较每次将待比较硬币分为相等两组，共4轮比较。算法分析与比较上述三种方法，分别需要比较15次，8次，4次。比较次数差异的根本原因是什么?方法1：每枚硬币都至少进行了一次比较，而有一枚硬币进行了15次比较。方法2：每一枚硬币只进行了一次比较。方法3：一次比较可以将硬币的范围缩小到原来的一半，充分利用了只有1枚假币的基本性质。方法四第1组第2组1次比较第1组第2组1次比较第3组共3次比较不等相等1次比较1次比较首轮采取平分，第二轮采取三分法。测试选择题：现有24个硬币，其中有1个硬币是假币（重量更轻），利用一个天枰，在最坏情况下，最少需要（）次比较。A：3B：4C：5D：6方法二8方法三

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论