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

G 山求程工大彩 SHANDONG UNIVERSITY OF TECHNOLOGY 第五篇算法与程序设计 第9章算法

第五篇 算法与程序设计 第9章 算法

0 目录 什草凤利学与拉未学脑 算法的概念 算法的描述 经典算法设计

目录 3. 经典算法设计 2. 算法的描述 1. 算法的概念

1.算法的概念 0 计草机利学与校未学网 ·算法概述 口没有算法，就没有计算机程序 口算法(algorithm)是一组解决问题的有穷规则的集合 ▣欧几里得算法 算法9.1： (1)输入任意两个整数m和n,使得m>n; (2)计算：m除以n得余数r; (3)若r=0,则n为求得的最大公约数，算法结束；否则执行(4)： (4)将m的值修改为n,将n的值修改为r,再重复执行(2)

1.算法的概念 ◼ 算法概述 ❑ 没有算法，就没有计算机程序 ❑ 算法(algorithm)是一组解决问题的有穷规则的集合 ❑ 欧几里得算法 算法9.1： (1) 输入任意两个整数m和n，使得m>n； (2) 计算：m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) 将m的值修改为n，将n的值修改为r，再重复执行(2)

1.算法的概念 0 件菜凤利学与拉未学腐 ■算法的特征 口有限性：算法在执行有限步以后必须终止 确定性：算法的每一个步骤都有精确的定义 ▣可行性：算法中有待实现的运算都是可以实现的 0 输入：一个算法可以有0个或多个输入数据，作为 算法开始执行的初始值 口输出：一个算法必须有一个或者多个输出数据，这 些输出的结果与输入的数据有特定的关系

1.算法的概念 ◼ 算法的特征 ❑ 有限性：算法在执行有限步以后必须终止 ❑ 确定性：算法的每一个步骤都有精确的定义 ❑ 可行性：算法中有待实现的运算都是可以实现的 ❑ 输入：一个算法可以有0个或多个输入数据，作为 算法开始执行的初始值 ❑ 输出：一个算法必须有一个或者多个输出数据，这 些输出的结果与输入的数据有特定的关系

2.算法的描述 0 计草机利学与校术学网 ■自然语言 ▣这种方法是用人们日常使用的语言来描述算法。它 无需专门训练就可以描述出通俗易懂的算法。例如 第一节的算法9.1，就是用自然语言描述的。 ▣但是，自然语言固有的不严密性使得我们很难做到 简单清晰的描述算法，并且自然语言不便于翻译成 计算机设计语言，所以伪代码应运而生

2.算法的描述 ◼ 自然语言 ❑ 这种方法是用人们日常使用的语言来描述算法。它 无需专门训练就可以描述出通俗易懂的算法。例如 第一节的算法9.1，就是用自然语言描述的。 ❑ 但是，自然语言固有的不严密性使得我们很难做到 简单清晰的描述算法，并且自然语言不便于翻译成 计算机设计语言，所以伪代码应运而生

2.算法的描述 0 杜算风利学与技本学脑 ■伪代码 口伪代码是自然语言和类编程语言组成的混合结构， 它比自然语言更精确，更简洁，如果熟悉一门现代 编程语言就更容易理解了。 欧几里得算法的伪代码： 1.r=m%n∥%是求余数运算符 2.while r<>=0∥<>代表不等于 /这条语句的功能是当不等于0的前提下循环下面三行代码 m=n n=r r=m %n 3.输出n

2.算法的描述 ◼ 伪代码 ❑ 伪代码是自然语言和类编程语言组成的混合结构， 它比自然语言更精确，更简洁，如果熟悉一门现代 编程语言就更容易理解了。 欧几里得算法的伪代码： 1. r= m % n //%是求余数运算符 2. while r<>=0 //<>代表不等于 //这条语句的功能是当r不等于0的前提下循环下面三行代码 m=n n=r r=m % n 3. 输出n

2.算法的描述 0 计草机利学与校术学网 流程图 ▣用一组标准图形符号来描述算法。 开始 欧几里得算法的流程图： 输入m和n 它的主要优点是画法简单、结构清晰、逻 辑性强、容易理解，便于初学者掌握。但是 r=m%n 流程图本质上不是逐步求精的好工具，复杂 Y 的算法用流程图描述时会占用很大篇幅。实 =0 践证明，除了一些非常简单的算法以外，这 种表示方法使用起来非常不便。所以，己经 m=n;n=r 有越来越多的人不再使用流程图了 输出n 结束

2.算法的描述 ◼ 流程图 ❑ 用一组标准图形符号来描述算法。 欧几里得算法的流程图： 它的主要优点是画法简单、结构清晰、逻 辑性强、容易理解，便于初学者掌握。但是 流程图本质上不是逐步求精的好工具，复杂 的算法用流程图描述时会占用很大篇幅。实 践证明，除了一些非常简单的算法以外，这 种表示方法使用起来非常不便。所以，已经 有越来越多的人不再使用流程图了

3.经典算法设计 0 杜算风利学与技本学脑 ·穷举法 口穷举法，也被称为枚举法，是指从可能的集合中一 一枚举各个元素，用题目给定的约束条件判定哪些 是无用的，哪些是有用的，能使命题成立者即为问 题的解。 1)百元百鸡： 公元5世纪末，我国古代数学家张丘建在他编写的《算经》中提 出这样一个问题：“鸡翁一值钱五；鸡母一值钱三；鸡雏三值钱一。 百钱买百鸡，问鸡翁、母、雏各几何？”意思是说，公鸡每只5元， 母鸡每只3元，3只小鸡1元，用100元钱买100只鸡，求公鸡、母鸡和 小鸡各多少只。这里设每种鸡至少一只

3.经典算法设计 ◼ 穷举法 ❑ 穷举法，也被称为枚举法，是指从可能的集合中一 一枚举各个元素，用题目给定的约束条件判定哪些 是无用的，哪些是有用的，能使命题成立者即为问 题的解。 1）百元百鸡： 公元5世纪末，我国古代数学家张丘建在他编写的《算经》中提 出这样一个问题：“鸡翁一值钱五；鸡母一值钱三；鸡雏三值钱一。 百钱买百鸡，问鸡翁、母、雏各几何？”意思是说，公鸡每只5元， 母鸡每只3元，3只小鸡1元，用100元钱买100只鸡，求公鸡、母鸡和 小鸡各多少只。这里设每种鸡至少一只

3.经典算法设计 计草机利学与校未学网 1)百元百鸡： 这个算法对x、y、z都从1开始枚举到100，计算 【算法分析】 机需要做100*100*100次比较操作，虽然这点 我们假达 鸡总数(+y “规模”对计算机来说不算什么，可以很快完成 条件，穷举出计算，但是，这个算法仍然后很大的改进空间。 算法9.2： for1to100/公鸡数从1枚举到100 fory=1to100/母鸡数从1枚举到100 forz=1to100/小鸡数从1枚举到100 if(x+y+z)=100and(5*x+3*y+z/3)=100则 输出x、y、z的值

3.经典算法设计 1）百元百鸡： 【算法分析】 我们假设公鸡、母鸡、小鸡的只数分别为x、y、z。我们以三种 鸡总数（x+y+z）和买鸡的总钱数（5*x+3*y+z/3）都等于100为判定 条件，穷举出各种鸡的只数。 算法9.2： for x=1 to 100 //公鸡数从1枚举到100 for y=1 to 100 //母鸡数从1枚举到100 for z=1 to 100 //小鸡数从1枚举到100 if (x+y+z)=100 and (5*x+3*y+z/3)=100 则 输出x、y、z的值 这个算法对x、y、z都从1开始枚举到100，计算 机需要做100*100*100次比较操作，虽然这点 “规模”对计算机来说不算什么，可以很快完成 计算，但是，这个算法仍然后很大的改进空间

3经典算法设计 杜算风利学与技本学脑 1)百元百鸡： 因为公鸡5元钱一只，所以100元最多买20只公鸡。同理，100元 最多买33只母鸡，而小鸡的数目是100-xy,因此没必要枚举。改进 后的算法如下： 算法9.3： forx=1to20/公鸡数从1枚举到100 fory=1to33/母鸡数从1枚举到100 z=100-×-y if(5*x+3*y+z3)=100则 输出x、y、z的值 改进后的算法让计算机执行操作的次数减少到大约660次。这个 程度的优化在实际运行中是感觉不到的。但是算法优化的思想还请读 者记在心里

3.经典算法设计 1）百元百鸡： 因为公鸡5元钱一只，所以100元最多买20只公鸡。同理，100元 最多买33只母鸡，而小鸡的数目是100-x-y，因此没必要枚举。改进 后的算法如下： 算法9.3： for x=1 to 20 //公鸡数从1枚举到100 for y=1 to 33 //母鸡数从1枚举到100 z=100-x-y if (5*x+3*y+z/3)=100 则 输出x、y、z的值 改进后的算法让计算机执行操作的次数减少到大约660次。这个 程度的优化在实际运行中是感觉不到的。但是算法优化的思想还请读 者记在心里