人教版高一数学(必修三)第一章 算法初步

算法初步算法的基本思想高二数学必修三中国传媒大学汪程洁算法初步算法的基本思想【例】在电视台的某个娱乐节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：参与者：800元！主持人：高了！参与者：400元！主持人：低了！参与者：600元！主持人：低了！………………….如果你是参与者，你接下来会怎么猜？我们为什么要学习算法？问题：为什么要在数学课上教语句和算法？学习算法有什么用，跟生活又什么关系？1、体会算法基本思想；2、提高逻辑思维能力；3、提高思辨能力和实践能力；思考以下问题的算法：一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？解:1.把银元分成3组，每组3枚；2．先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在未称的第3组里；3．取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。【例】写出你在家中烧开水的过程的一个算法1、往壶内注水；2、点火加热；3、观察：如果水开，则停止烧火，否则继续烧火；4、如果水未开，重复“3”直至水开。总结一、其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步，才能更好地认清事物的本质，进而提出解决问题的方法；二、判断水是否烧开与是否继续烧火的过程是一个判断与反馈的过程，因此有必要不断重复过程“3”算法的基本思想△随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会的方方面。在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等。完成这些工作都需要一系列程序化的步骤，这就是算法的思想。算法是什么△算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看成按要求设计好的有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题。简单的说，算法就是解决问题的步骤和方法。判断一个正整数是否是质数的算法1、自然语言描述第一步：判断n是否等于2？若n=2，则n是质数，否则，执行第二步；第二步：依次从2~（n-1）检验是不是n的因数，即能整除n的数，若有这样的数，则n不是质数；若没有，则n是质数。开始输入nn=2?d=2flag=0d=d+1d整除n?d=n-1且flag=1?flag=1?n是质数n不是质数结束是否否是否是否是算法的四个特征算法不同于求解一个具体问题的方法，是这种方法的高度概括。算法具有如下特征：（1）可行性(effectiveness）算法的可行性包括两个方面：一是算法中的每一个步骤必须是能实现的。例如，在算法中，不允许出现分母为零的情况；在实数范围内不能求一个负数的平方根等。二是算法执行的结果要能达到预期的目的。通常，针对实际问题设计的算法，人们总是希望能够得到满意的结果。算法的四个特征（2）确定性(definiteness）算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。这一特征也反映了算法与数学公式的明显差异。在解决实际问题时，可能会出现这样的情况：针对某种特特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从，这是因为，根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，该计算过程就不能适应了。算法的四个特征例如，某计算工具规定：大于100的数认为是比1大很多，而小于10的数不能认为是比1大很多；且在正常情况下出现的数或是大于100,或是小于10.但指令“输入一个X，若x比1大很多，则输出数字1，否则输出数字0”是不确定的。这是因为，在正常的输入情况下，这一指令的执行可以得到正确的结果，但在异常情况下（输入的x在10与100之间），这一指令执行的结果就不确定了．算法的四个特征（3）有穷性(finiteness）算法的有穷性是指算法必须能在有限的时间内执行完，即算法必须能在执行有限个步骤之后终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数的过程只能是有穷的。因此，一个数的无穷级数的表示只是一种计算公式，而根据精度要求确定的计算过程才是有穷的算法。算法的四个特征算法的有穷性还应包括合理的执行时间的含义。如果一个算法的执行时间是有穷的，但却需要执行千万年．显然这就失去了算法的实用价值。例如，克莱姆(Cramer)规则是求解线性代数方程组的一种数学方法，但不能以此为算法，这是因为，虽然总可以根据克莱姆规则设计出一个计算过程用于计算所有可能出现的行列式，但这样的计算过程所需的时间实际上是不能容忍的。算法的四个特征从理论上讲，总可以写出一个正确的弈棋程序，而且这也并不是一件很困难的工作。由于在一个棋盘上安排棋子的方式总是有限的，而且，根据一定的规则．在有限次移动棋子之后比赛一定结束。因此．弈棋程序可以考虑计算机每一次可能的移动，它的对手每一次可能的应答，以及计算机对这些移动的可能应答等等，直到每个可能的移动停止下来为止。算法的四个特征此外，由于计算机可以知道每次移动的结果，因此总可以选择一种最好的移动方式。但即使如此，这种弈棋程序还是不可能执行，因为所有这些可能移动的次数太多，所要花费的时间不能容忍。由上述两个例子可以看出，虽然许多计算过程是有限的．但仍有可能无实用价值。算法的四个特征（4）算法必须拥有足够的情报一个算法是否有效，还取决于为算法的执行所提供的情报是否足够。例如，对于指令“如果小明是学生，则输出字母Y，否则输出N”。当算法执行过程中提供了小明一定不是学生的某种信息时，执行的结果将输出字母N；当提供的只是部分学生的名单，且小明恰在此名单之中，则执行的结果将输出字母Y。但如果在提供的部分学生的名单中找不到小明的名字．则在执行该指令时无法确定小明是否是学生。请试写出一个算法？写出求一个数绝对值的一个算法①请输入要求绝对值的数a；大家要注意写算法的要求②若a=0,则b=0(b为a的绝对值)；若a0，则b=a；若a0，则b=-a.③输出a的绝对值b。答案绝对值问题开始输入aa≥0输出|a|=a输出|a|=-a结束NY算法是解决问题的精确的描述，但是并不是所有问题都有算法，有些问题使用形式化、程序化的刻画是最恰当的，这就要求我们在写算法时应精练、简练、清晰地表达清楚，更要善于分析任何可能出现的问题。程序化的算法共有三大模块：1、输入数据；2、分析、判断、执行；3、输出结果。算法初步程序框图程序框图是描述算法的适度形式自然语言：模糊性和二义性；程序框图：表述算法基本逻辑结构的图形组成，它使复杂的内容与关系表现的非常明了，具有很好的可读性，但是计算机不能读解；程序设计：将算法用计算机能够识别的语言表述出来，但由于程序设计非常形式化，过于复杂，数学课上没必要讲述。程序框图部分的教学目标只要掌握三种基本结构和五个基本算法语句就可以了。顺序结构：条件结构：输入nflag=1flag=1?n是质数n不是质数结束是否循环结构循环结构示意图flag=0d=d+1d整除n?d＜=n－1且flag=1?否是否是五种语句1、输入语句；2、输出语句；3、赋值语句；4、条件语句；5、循环语句；小结1、循环结构的特点：重复同一个处理过程2、循环结构的框图表示：当型（条件满足）和直到型（条件不满足）3、循环结构注意的问题：避免死循环的出现，设置好进入（结束）循环体的条件。程序框图又称流程图，是一种用规定的图形，指向线及文字说明来准确、直观地表示算法的图形。名称功能终端框（起止框）一个算法的起始和结束输入、输出框算法的输入和输出的信息处理框（执行框）赋值、计算判断框判断一个条件是否成立，用“是”、“否”或“Y”、“N”标明例1设计一算法：输入圆的半径,输出圆的面积，并画出流程图开始结束输入半径R计算S=Pi*R*R输出面积S定义Pi=3.14第一步：输入圆的半径；第二步：利用公式“圆的面积=圆周率×（半径的平方）”计算圆的面积；第三步：输出圆的面积。思考：整个程序框图有什么特点？例：设计房租收费的算法,其要求是:住房面积80平方米以内,每平方米收费3元,住房面积超过80平方米时,超过部分,每平方米收费5元.输入住房面积数,输出应付的房租。思考：整个程序框图有什么特点？算法如下：第一步：输入住房面积S；第二步：根据面积选择计费方式：如果S小于或等于80，则租金为M=s×3，否则为M=240+(S-80)×5；第三步：输出房租M的值。开始结束输入面积S输出租金MS=80M=3*SM=240+5*(S-8)否是练习题一城区一中学生数学模块学分认定由模块成绩决定，模块成绩由模块考试成绩和平时成绩构成，各占50%，若模块成绩大于或等于60分，获得2学分，否则不能获得学分（为0分），设计一算法，通过考试成绩和平时成绩计算学分，并画出程序框图。答案开始结束输入a,bS=60?credit=2credit=0否是S=(a+b)*0.5输出credit练习题二为了加强居民的节水意识，某市制定了以下生活用水收费标准：每户每月用水未超过７ｍ３时，每立方米收费1.0元，并加收0.2元的城市污水处理费,超过７ｍ３的部分,每立方米收费1.5元，并加收0.4元的城市污水处理费。答案y=1.2xy=1.9x－4.9结束yN开始输入xx≤7输入y