《计算机应用基础》课程教学资源（PPT课件讲稿）2019算法

第九章算法

第九章 算法

全部章节 CONTENTS 9.1 算法简介 9.2 穷举算法 主要内容：算法的表示 主要内容：百元百鸡 算法运行时间 旅行商问题 9.3 查找算法 9.4 排序算法 主要内容：顺序查找 二分查找 主要内容：直接插入排序 选择排序 冒泡排序 快速排序

9.1 算 法 简 介 主要内容：算法的表示 算法运行时间 9.2 穷 举 算 法 主要内容：百元百鸡 旅行商问题 9.3 查找算法 主要内容：顺序查找 二分查找 9.4 排 序 算 法 主要内容：直接插入排序 选择排序 冒泡排序 快速排序 CONTENTS 全部章节

全部章节 CONTENTS 9.5 贪婪算法 9.6 动态规划 主要内容：背包问题 主要内容：背包问题 旅行商问题 旅行商问题 9.7 回溯法 9.8 趣味算法 主要内容：八皇后问题 主要内容：兔子产仔问题 谁在说谎 有趣的数字

9.5 贪 婪 算 法 主要内容：背包问题 旅行商问题 9.6 动 态 规 划 主要内容：背包问题 旅行商问题 9.7 回溯法 主要内容：八皇后问题 9.8 趣 味 算 法 主要内容：兔子产仔问题 谁在说谎 有趣的数字 CONTENTS 全部章节

9.1算法简介 9.1.1引言 算法这个名词听上去很抽象，让人联想不到任何具体的物体。甚至你会觉得算法 与自己的生活并无太多关联，它只是为计算机专业人员或者科学家服务的。这样的想法 真是大错特错了。 事实上，算法无处不在。比如你去食堂买饭会选择一个较短的队列，有的人则可能 选择一个推进速度快的队列。再比如每天早上起床，你可能先读一会儿书再去吃早餐， 而别的人可能先去吃早餐然后再看书。所有这些行为都是算法的体现。运行这些算法并 不一定是刻意的出现在你的意识中，也通常不会经过精心设计，但它确实存在

9.1 算法简介 9.1.1 引言 算法这个名词听上去很抽象，让人联想不到任何具体的物体。甚至你会觉得算法 与自己的生活并无太多关联，它只是为计算机专业人员或者科学家服务的。这样的想法 真是大错特错了。 事实上，算法无处不在。比如你去食堂买饭会选择一个较短的队列，有的人则可能 选择一个推进速度快的队列。再比如每天早上起床，你可能先读一会儿书再去吃早餐， 而别的人可能先去吃早餐然后再看书。所有这些行为都是算法的体现。运行这些算法并 不一定是刻意的出现在你的意识中，也通常不会经过精心设计，但它确实存在

9.1.2算法是计算机的灵魂 算法是解决问题的有穷步骤的描述。 就拿排序来说，我们的生活中处处可见次序，比如考试排名，工作评优等。大家 首先想到的排序方法是什么呢？这个问题的答案大概就是插入法了。换一个通俗易懂的 说法，就是人们打牌时整理手中扑克牌的算法。这个算法的效率会随着数据量的增加而 大幅度降低。 一个个新的算法都是为了解决前面算法遗留的问题而产生，新的算法提高了效率， 同时也会有意或无意的引入了新的问题，这应该就是算法永远不会停止发展的一个原因 吧

9.1.2 算法是计算机的灵魂 算法是解决问题的有穷步骤的描述。 就拿排序来说，我们的生活中处处可见次序，比如考试排名，工作评优等。大家 首先想到的排序方法是什么呢？这个问题的答案大概就是插入法了。换一个通俗易懂的 说法，就是人们打牌时整理手中扑克牌的算法。这个算法的效率会随着数据量的增加而 大幅度降低。 一个个新的算法都是为了解决前面算法遗留的问题而产生，新的算法提高了效率， 同时也会有意或无意的引入了新的问题，这应该就是算法永远不会停止发展的一个原因 吧

9.1.2算法是计算机的灵魂 要计算1到100的累加和。有人先计算1+2，再将结果加上3，然后再将结果加 上4，以此类推，一直加到100。而有的人会将1+100，然后乘以50即可同样得出答 案。这两种方法的时间复杂度是不一样的，很显然第二种方法更快的得到答案。 由于现代计算机运行速度都非常快，对于运行这样一点小运算来说不会有明显的 时间差异。但是在大型软件项目中，程序的执行效率高低就显得至关重要，会直接影响 到用户体验。因此，合理的算法设计是非常必要的

9.1.2 算法是计算机的灵魂 要计算1到100的累加和。有人先计算 1+ 2 ，再将结果加上3，然后再将结果加 上4，以此类推，一直加到 100。而有的人会将 1 + 100，然后乘以50即可同样得出答 案。这两种方法的时间复杂度是不一样的，很显然第二种方法更快的得到答案。 由于现代计算机运行速度都非常快，对于运行这样一点小运算来说不会有明显的 时间差异。但是在大型软件项目中，程序的执行效率高低就显得至关重要，会直接影响 到用户体验。因此，合理的算法设计是非常必要的

9.1.3运行时间 假设在字典中查找一个以M开头的单词，你可以从头开始翻页，直到进入以M开头 的部分。 你还可以从中间开始，因为你知道M开头的单词在字典的中间位置附近。 再比如有100个数字，已经按照从小到大的顺序排列好了。当我们需要找出其中某 一个数字时，可以从头开始比对，最差的情况是需要比对100次。还可以从中间开始。 对100个数字而言，这种方法最多需要比对7次。如果列表中包含40亿个数字，最 多也只需要比对32次。厉害吧？

9.1.3 运行时间 假设在字典中查找一个以M开头的单词，你可以从头开始翻页，直到进入以M开头 的部分。 你还可以从中间开始，因为你知道M开头的单词在字典的中间位置附近。 再比如有100个数字，已经按照从小到大的顺序排列好了。当我们需要找出其中某 一个数字时，可以从头开始比对，最差的情况是需要比对100次。还可以从中间开始。 对100个数字而言，这种方法最多需要比对7次。如果列表中包含40亿个数字，最 多也只需要比对32次。厉害吧？

9.1.3运行时间 对长度为的列表，使用逐个比对的方法就需要执行n次操作，这个运行时间我们 记做O(),也叫线性时间。如果使用从中间折半的方法就仅仅需要执行1ogn次操作， 记做O(I0g),也叫对数时间。这种表示法不是以秒为单位的，它告诉我们算法到底有 多快，也就是指出了算法运行时间的增速。O(Iogn)比O()快，当需要搜索的元素越多 时，前者比后者快的越多

9.1.3 运行时间 对长度为n的列表，使用逐个比对的方法就需要执行n次操作，这个运行时间我们 记做O(n)，也叫线性时间。如果使用从中间折半的方法就仅仅需要执行log n次操作， 记做O(log n)，也叫对数时间。这种表示法不是以秒为单位的，它告诉我们算法到底有 多快，也就是指出了算法运行时间的增速。O(log n)比O(n)快，当需要搜索的元素越多 时，前者比后者快的越多

9.1.4算法的表示 1.自然语言 知道把大象放冰箱一共分几步吗？ 一，把冰箱门打开。 二，把大象塞进去。 三，把冰箱门关上。 这就是用自然语言描述的算法

9.1.4 算法的表示 1.自然语言 知道把大象放冰箱一共分几步吗？ 一，把冰箱门打开。 二，把大象塞进去。 三，把冰箱门关上。 这就是用自然语言描述的算法

9.1.4算法的表示 1.自然语言 古希腊数学家欧几里得（公元前3世纪）曾在他的著作中描述过求两个数的最大 公因子的过程。这里用到了一个定理，即两个整数的最大公约数等于其中较小的那个数 和两数相除余数的最大公约数。 算法9.1： (1)输入任意两个整数m和n,使得m>n; (2)计算：m除以n得余数r; (3)若r=0,则n为求得的最大公约数，算法结束；否则执行(4)； (4)将m的值修改为n,将n的值修改为r,再重复执行(2)

9.1.4 算法的表示 1.自然语言 古希腊数学家欧几里得（公元前3世纪）曾在他的著作中描述过求两个数的最大 公因子的过程。这里用到了一个定理，即两个整数的最大公约数等于其中较小的那个数 和两数相除余数的最大公约数。 算法9.1： (1) 输入任意两个整数m和n，使得m>n； (2) 计算：m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) 将m的值修改为n，将n的值修改为r，再重复执行(2)