算法初步
算法的基本思想
高二数学必修三
中国传媒大学 汪程洁
算法初步
算法的基本思想
【例】在电视台的某个娱乐节目中，要求参与者快速
猜出物品的价格。主持人出示某件物品，参与者每次
估算出一个价格，主持人只能回答高了、低了或者正 确。
在某次节目中，主持人出示了一台价值在1000元 以内的随身听，并开始了竞猜。下面是主持人和参与 者的一段对话：
【例】写出你在家中烧开水的过程的一个算法
1、往壶内注水； 2、点火加热； 3、观察：如果水开，则停止烧火，否 则继续烧火； 4、如果水未开，重复“3”直至水开。
总结
一、其实大部分事情都是按照一定的程序执行， 因此要理清事情的每一步，才能更好地认清事 物的本质，进而提出解决问题的方法；
二、判断水是否烧开与是否继续烧火的过程是 一个判断与反馈的过程，因此有必要不断重复 过程“3”
思考以下问题的算法：
一位商人有9枚银元，其中有1枚略轻的是假银 元。你能用天平（不用砝码）将假银元找出来吗？
解: 1.把银元分成3组，每组3枚；
2．先将两组分别放在天平的两边。如果天平 不平衡，那边假银元就放在轻的那一组；如果天平 左右平衡，则假银元就在未称的第3组里；
3．取出含假银元的那一组，从中任取两枚放 在天平的两边。如果左右不平衡，则轻的那一边就 是假银元；如果天平两边平衡，则末称的那一枚就 是假银元。
算法的四个特征
例如，某计算工具规定：大于100的数认为是比1 大很多，而小于10的数不能认为是比1大很多；且 在正常情况下出现的数或是大于100,或是小于10. 但指令“输入一个X，若x比1大很多，则输出数字 1，否则输出数字0”是不确定的。这是因为，在正 常的输入情况下，这一指令的执行可以得到正确 的结果，但在异常情况下（输入的x在10与100之 间），这一指令执行的结果就不确定了．
算法的四个特征
（3）有穷性(finiteness） 算法的有穷性是指算法必须能在有限的时间内执 行完，即算法必须能在执行有限个步骤之后终止。 数学中的无穷级数，在实际计算时只能取有限项， 即计算无穷级数的过程只能是有穷的。因此，一 个数的无穷级数的表示只是一种计算公式，而根 据精度要求确定的计算过程才是有穷的算法。
算法的四个特征
从理论上讲，总可以写出一个正确的弈棋程序， 而且这也并不是一件很困难的工作。由于在一个 棋盘上安排棋子的方式总是有限的，而且，根据 一定的规则．在有限次移动棋子之后比赛一定结 束。因此．弈棋程序可以考虑计算机每一次可能 的移动，它的对手每一次可能的应答，以及计算 机对这些移动的可能应答等等，直到每个可能的 移动停止下来为止。
本运算及规定的运算顺
序构成的完整的解题步 骤，或看成按要求设计 好的有限的、确切的计 算序列，并且这样的步
算 法 是
骤或序列能解决一类问 什
题。
么
简单的说，算法就是解
决问题的步骤和方法。
判断一个正整数是否是质数的算法
1、自然语言描述
第一步：判断n是否等于2？若n=2，则n是质数，否则， 执行第二步；
（1）可行性(effectiveness）
算法的可行性包括两个方面：一是算法中的每一 个步骤必须是能实现的。例如，在算法中，不允 许出现分母为零的情况；在实数范围内不能求一 个负数的平方根等。二是算法执行的结果要能达 到预期的目的。通常，针对实际问题设计的算法， 人们总是希望能够得到满意的结果。
算法的四个特征
一个算法是否有效，还取决于为算法的执行所提 供的情报是否足够。例如，对于指令“如果小明 是学生，则输出字母Y，否则输出N”。当算法执行 过程中提供了小明一定不是学生的某种信息时， 执行的结果将输出字母N；当提供的只是部分学生 的名单，且小明恰在此名单之中，则执行的结果 将输出字母Y。但如果在提供的部分学生的名单中 找不到小明的名字．则在执行该指令时无法确定 小明是否是学生。
参与者：800元！ 主持人：高了！ 参与者：400元！ 主持人：低了！ 参与者：600元！ 主持人：低了！ ………………….
如果你是参与者，你接下来会怎么猜？
我们为什么要学习算法？
问题：为什么要在数学课上教语句和算法？ 学习算法有什么用，跟生活又什么关系？
1、体会算法基本思想； 2、提高逻辑思维能力； 3、提高思辨能力和实践能力；
第二步：依次从2~（n-1）检验是不是n的因数，即能 整除n的数，若有这样的数，则n不是质数；若没有，则 n是质数。
开始
输入n
是 n=2? 否 d=2
d整除n? 是
flag=0
否 d=d+1
是
d<=n-1且
flag=1?
否 否
flag=1?
是
n是质数
n不是质数
结束
算法的四个特征
算法不同于求解一个具体问题的方法，是这种方 法的高度概括。算法具有如下特征：
△随着计算科学和信息技术
的飞速发展，算法的思想已经
渗透到社会的方方面。在以前 算
的学习中，虽然没有出现算法 法
这个名词，但实际上在数学教 的
学中已经渗透了大量的算法思
基
想，如四则运算的过程、求解 方程的步骤等等。完成这些工 作都需要一系列程序化的步骤，
本 思
这就是算法的思想。
想
△算法可以理解为由基
算法的四个特征
此外，由于计算机可以知道每次移动的结果，因 此总可以选择一种最好的移动方式。但即使如此， 这种弈棋程序还是不可能执行，因为所有这些可 能移动的次数太多，所要花费的时间不能容忍。 由上述两个例子可以看出，虽然许多计算过程是 有限的．但仍有可能无实用价值。
算法的四个特征
（4）算法必须拥有足够的情报
（2）确定性(definiteness）
算法的确定性，是指算法中的每一个步骤都必须是有明确 定义的，不允许有模棱两可的解释，也不允许有多义性。 这一特征也反映了算法与数学公式的明显差异。在解决实 际问题时，可能会出现这样的情况：针对某种特特殊问题， 数学公式是正确的，但按此数学公式设计的计算过程可能 会使计算机系统无所适从，这是因为，根据数学公式设计 的计算过程只考虑了正常使用的情况，而当出现异常情况 时，征
算法的有穷性还应包括合理的执行时间的含义。 如果一个算法的执行时间是有穷的，但却需要执 行千万年．显然这就失去了算法的实用价值。例 如，克莱姆(Cramer)规则是求解线性代数方程组 的一种数学方法，但不能以此为算法，这是因为， 虽然总可以根据克莱姆规则设计出一个计算过程 用于计算所有可能出现的行列式，但这样的计算 过程所需的时间实际上是不能容忍的。