《数学（第8版 下册）》 课件 第5章 算法初步

算法初步第5章204目录5.1算法的含义5.2流程图5.3基本算法语句205学习目标1.通过对解决具体问题过程与步骤的分析（如一元二次方程组求解等问题），体会算法的思想，并能叙述算法的含义.2.在具体问题的解决过程中，能说出程序框图的三种基本逻辑结构（顺序、选择、循环）及绘制算法框图的常用符号和含义.3.能写出简单问题的算法及流程，并绘制算法框图.4.了解伪代码的基本算法语句，能根据流程图用伪代码写出简单问题的算法.2065.1算法的含义207实例考察在你面前的桌面上摆放着A，B两个大小相同的杯子.A杯子中装有水，B杯子中装有饮料，采取怎样的办法才能交换A，B两个杯子中的液体?解决这个问题，我们可以按以下步骤进行.第一步：先找一个容量不小于A，B的空杯子C；第二步：将A杯子中的水倒入到C杯子中；第三步：将B杯子中的饮料倒入到A杯子中；第四步：将C杯子中的水倒入到B杯子中，完成交换.208以上过程实际上是按一种机械的程序进行的一系列操作.一般而言，对一类问题的机械的、统一的求解方法称为算法.同一项任务可以用不同的算法完成，花费的时间可能不同.一个算法的好坏可以综合复杂程度和执行这个算法耗费的时间等因素来衡量.如果一个算法有缺陷或不适合某个问题，执行这个算法就不能解决这个问题.209例

写出求解方程组的一个算法.解

我们用消元法求解这个方程组.第一步：方程①不变，用方程②中x的系数除以方程①中x的系数，得到乘数m=.210第二步：方程②减去

m

倍的方程①，从而消去方程②中的x项，得到第三步：将上面的方程组自下而上回代求解，得到

x=1，y=2.所以，原方程组的解为211上面例子所示的消元回代的算法适用于一般线性方程组的求解.所谓找到了某种算法，是指使用一系列运算规则能在有限步骤内求解某类问题，其中的每条规则必须是明确定义、可以执行的.算法从初始步骤开始，每一个步骤只能有一个确定的后继步骤，从而组成一个步骤序列，序列的终止表示问题得到解答或指出问题没有答案.我们所学过的许多数学公式都是算法，加、减、乘、除运算法则以及多项式的运算法则也是算法.2125.2流程图213实例考察

在快递派送过程中，因为目的地偏远而派送不到的情形被快递公司称为快递超区.一般情况下，快递公司对此采取以下措施.可以看到，用框图和线来表示各种操作流程的优点是形象直观、便于理解.2145.2.1流程图实例考察中，快递公司把每一步工作流程都按照方框里面的指令操作，各步骤之间用流程线顺序连接成一个整体.这种用规定的图框、流程线及文字来准确、直观地表示算法的图形，叫做算法的流程图.它是算法的一种图形表示形式，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序.构成流程图的图形符号及其功能见下表.215216

流程图的图形符号及其功能5.2.2流程图的基本机构实例考察某企业根据岗位需求招募高技能人才，用人部门、人事部门、管理层紧密配合，按照规定一般遵循以下流程图.217

从流程图中可以看出，该算法步骤中，有些是按顺序执行，有些需选择执行.事实上，算法的流程图有三种基本的逻辑结构：顺序结构、选择结构和循环结构.这三种结构通过组合和嵌套来表达算法的流程图.流程图可以帮助我们更方便直观地表现这三种基本的算法结构.2181.顺序结构顺序结构是一种按顺序依次进行多个处理的结构.如图所示，虚线框内是一个顺序结构，其中A

和B

两个框是依次执行的.顺序结构是一种最简单、最基本的结构.2192.选择结构选择结构是一种先根据条件做出判断，再决定执行哪一种操作的结构（或称为分支结构）.如图所示，虚线框内是一个选择结构，它包含一个判断框，当条件p成立（或为“真”）时，执行A，否则执行B.选择结构是一种有条件的二选一的操作结构.2203.循环结构在算法中，需要重复执行同一操作的结构称为循环结构.如图所示，虚线框内是一种常见的循环结构：先判断所给条件p

是否成立，若p

成立，则执行

A；再判断条件p是否成立，若p仍成立，则又执行A，如此反复，直到某一次条件p不成立时为止.这样的循环结构称为当型循环.221下面这种循环结构称为直到型循环：先执行A，再判断条件p是否成立，若p不成立，则再执行A，如此反复，直到p成立，该循环过程结束.2225.3基本算法语句223算法是一种数学语言，计算机完成任何一项任务都需要算法，但是计算机无法识别数学语言，因此还需要我们把算法表示成计算机能够“理解”的程序语言.伪代码（pseudocode）就是介于自然语言与计算机语言之间的文字和符号.程序语言多种多样，为了表示算法的三种基本逻辑结构，各种程序语言中都包含下列基本的算法语句.2245.3.1赋值语句、输入和输出语句在伪代码中，赋值语句用符号“←”表示，例如

“x←y”

表示将y的值赋给x，其中x是一个变量，y是一个与x同类型的变量或表达式.2255.3.2条件语句和循环语句计算机不仅可以进行一些简单的赋值运算，还可以对给出的条件进行分析、比较、判断，并按照判断后的不同情况进行不同的处理.例如，判断一个数的正负、比较两个数的大小、对一组数据进行排序等.226当型循环可用下面的语句来描述：它表示当所给条件p成立时，执行循环体部分，然后再判断条件p是否成立.如果p

仍成立，那么再次执行循环体，如此反复，直到某一次条件p不成立时退出循环.227上述算法用当型循环语句

“While...EndWhile”表示如下：228上述的算法也可以改为直到型循环.S1：T←1；S2：I←3；S3：T←T×I；S4：I←I+2；S5：如果I>99，那么转S6，否则转S3；S6：输出T.229直到型循环可用下面的语句来描述：它表示先执行循环体部分，然后再判断条件p

是否成立.如果p不成立，那么再次执行循环体，如此反复，直到某一次条件p成立时退出循环.230

上述算法用直到型循环语句“Do...EndDo”表示如下：231如果循环语句中的循环次数已知，那么还可采用“For”

语句来描述.“For”

语句的一般形式是：232上述算法用

“For”

语句可表示如下：在上面的For语句中，如果省略语句“Step2”，那么重复循环时，I的值每次增加1.2335.3.3算法应用例题解析例

设计解决“孙子问题”的算法.我国

《算经十书》

之一的

《孙子算经》

中有这样的原文：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何?答曰：二十三.”“物不知数”问题提出之后，便引起了人们的很大兴趣.南宋数学家秦昭九对此加以推广，并给出新的解法———“大衍求一术”.这种解法和高斯的解法本质上是一致的，但比高斯早了500余年.这种问题的通用解法被称为

“孙子剩余定理”或“中国剩余定理”，这个定理在近代数学和计算机程序设计中有着广泛的应用.234解

算法设计思想：“孙子问题”相当于求关于x，y，z的不定方程组的正整数解.设所求的数为m，根据题意，m

应同时满足下列3个条件：（1）m