算法设计与分析 课件 许瑾晨 第4--10章 分治法 --- 综合应用 .pptx

信息工程大学

国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

主要内容

典型应用

二分有哪些信誉好的足球投注网站

快速排序

归并排序

算法引例棋盘覆盖

寻找假币大整数乘

寻找金块

一二三

算法基本思想

分治法解题步骤

分治法适用条件

分治法代码框架

重点掌握：

1.算法的基本思想

2.平衡划分原则

3.分治法的优化方法

信息工程大学

国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

一寻找假币

已知条件：一个装有16枚硬币的袋子，其中有一

枚硬币是伪造的，并且伪造的硬币比真的硬币要

轻一些。

工具：一台天枰，可用来比较两组硬币的重量。

问题：找出这枚伪造的硬币。

一寻找假币

方法一

任意取1枚硬币，与其它硬币进行比较，若发现轻

者，则轻者为假币。

最多可能有15次比较。

123456789101112131415

一寻找假币

方法二

将硬币分为8组，每组2个，每组比较一次，若发

现轻的，则为假币。

最多可能有8次比较。

12345678

一寻找假币

方法三每次将待比较硬币分为相等两组，共4轮比较。

第1组

1次比较

第2组

第1组

1次比较

第2组

共4次比较

第1组

1次比较

第2组

第1组

1次比较

第2组

一寻找假币

算法分析与比较

上述三种方法，分别需要比较15次，8次，4次。

比较次数差异的根本原因是什么?

方法1：每枚硬币都至少进行了一次比较，而有

一枚硬币进行了15次比较。

方法2：每一枚硬币只进行了一次比较。

方法3：一次比较可以将硬币的范围缩小到原来

的一半，充分利用了只有1枚假币的基本性质。

一寻找假币

方法四首轮采取平分，第二轮采取三分法。

第1组

1次比较

第2组

第1组

1次比较

第2组共3次比较

不等相等

第3组

1次比较1次比较

一寻找假币

测试

选择题：

现有24个硬币，其中有1个硬币是假币（重

量更轻），利用一个天枰，在最坏情况下，最少

需要（）次比较。

A：3

B：4

C：5

D：6

一寻找假币

方法二方法三方法四

比较次数843

分治法的主要内容之一：如何实现更好的问题划分

信息工程大学

国家级实验教学示范中心计算机学科组规划教材