算法的概念.doc

算法的概念知能阐释 一、知识精讲 1算法的含义 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或看成按要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题。 说明：（1）算法一般是机械的，有时要进行大量的重复计算，只要按部就班地去做，总能算出结果。通常把算法过程称为“数学机械化”，数学机械化的最大优点，是它可以让计算机来完成。 （2）实际上，处理任何问题都需要算法，中国象棋有中国象棋的棋谱，国际象棋有国际象棋的棋谱。再比如，邮寄物品有其相应的手续，购买飞机票也有一系列的手续等等。 （3）求解某个问题的算法不唯一。 2算法的特征 （1）确定性：算法的每一步必须是确切定义的，且无二意性，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。 （2）有容性：一个算法必须在执行有穷次运算后结束，在所规定的时间和空间内，若不能获得正确结果，其算法也是不能被采用的。 （3）可行性：算法中的每一个步骤都必须能用实现算法的工具可执行指令精确表达，并在有限步骤内完成，否则这种算法也是不会被采纳的。 （4）算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤。 （5）有输出，算法一定能得到问题的解，有一个或多个结果输出，达到求解问题的目的，没有输出结果的算法是没有意义的。 3算法的描述 （1）自然语言：自然语言就是人们日常使用的语言，可以是汉语、英语或数学语言等。用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解。缺点是如果算法中包含判断或转向，并且操作步骤较多时，就不那么直观清晰了。 （2）框图（流程图）：所谓框图，就是指用规定的图形符号来描述算法，用框图描述算法，具有直观、结构清晰、条理分明、通俗易懂、便于检查修改及交流等优点。 （3）程序设计语言：算法最终可通过程序的形式编写出来，并在计算机上执行。程序设计语言可分为低级语言和高级语言，低级语言包括机器语言和汇编语言。3设计算法的要求（1）写出的算法，必须解决一类问题，并且能够重复使用。（2）要使算法尽量简单、步骤尽量少。（3）要保证算法正确，且计算机能够执行，如：让计算机计算是可以做到的，但让计算机去执行“倒一杯水”则是做不到的。 二、范例剖析 例1 写出作的外接圆的一个算法。 分析：解决这个问题可按下面的算法进行。 解析：第一步：作的垂直平分线；第二步：作的垂直平分线；第三步：以与的交点为圆心，为半径作圆，圆即为的外接圆。评注：本题实质就是将的外接圆的一个作法分步写出。 例2 写出求经过点、的直线与两坐标轴围成的三角形面积的一个算法。 分析：已知直线上的两点、，由两点式可写出直线的方程，令，得与轴交点；令，得与轴交点。求出三角形两直角边的长，根据三角形的面积公式求出三角形的面积。 解析：算法如下： 第一步：取，； 第二步：得直线方程； 第三步：在第二步的方程中，令，得的值，从而得直线与轴的交点； 第四步：在第二步的方程中，令，得的值，从而得直线与轴的交点； 第五步：根据三角形的面积公式求； 第六步：输出运算结果。 评注：由于两点式直线方程可以有公式套用，所以这一步骤选择了套用公式的算法；三角形的面积需要求两直角边的长度，而本题中正是先求出三角形的两直角边的长度，再代入面积公式求出了三角形的面积。例3 一位商人有9枚银元，其中有一枚略轻的是假银元，你能用天平（不用砝码）将假银元找出来吗？分析1：最容易想到的解决这个问题的一种方法是：把9枚银元按顺序排成一列，先称前2枚，若不平衡，则可找出假银元；若平衡，则2枚银元都是真的，再依次与剩下的银元比较，就能找出假银元。解析：算法步骤如下：第一步：任取2枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则进行第二步；第二步：取下右边的银元放在一边，然后把剩余的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。分析2：上述算法至少要称1次，最多称7次，我们可以采用下面的办法，使称量次数少一些。第一步：把银元分成3组，每组3枚；第二步：先将两组分别放在天平的两边，如果天平不平衡，那么假银元就在轻的一组；如果天平左右平衡，则假银元就在未称的第3组里；第三步：取出含假银元的那一组，从中任取两枚银元放在天平的两边，如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元。 评注：从第二种方法中，我们发现一共只需要称两次就可以了，比第一种方法要优越。算法初步中的一、二、三、四、五一个概念算法概念是本章的一个基本概念，算法作为新名词，在以前的数学教科书中没有出现过但是算法本身，同学们并不陌生，解方程的算法、解不等式的算法、因式分解的算法，都是同学们熟知的内容而现代意义上的算法通常是指可以用计算机来解决的某一类问题的程序或步骤. 它具有有穷性（能在有限步之内完成）、可行性（每一步操作都必须是可执行的）、确定性（每一步应是确定的）、顺序性（有若干明确的步骤）等特征.两个要求1、提高对学习算法重要性的认识计算机按算法的程序或步骤对问题的初始数据进行处理，从而实现算法并解决问题，所以我们说算法是计算机科学的重要基础，没有算法就没有计算机.同样，计算机的出现和飞速发展也使算法的内涵有了很大变化，计算机无可比拟的运算速度和惊人的存储量使许多用其他计算工具无法完成的复杂计算成为可能，算法也因此焕发了前所未有的生机和活力学习算法不但能使同学们发展有条理的思考与表达的能力，而且能提高逻辑思维能力2、深刻理解算法思想算法思想是贯穿高中课程的一条主线，算法思想就是指按照一定的步骤，一步一步去解决某个问题的程序化思想. 我们将要学习的很多知识都可以运用算法思想，设计出程序框图，能使解答过程一目了然.当然，我们还可以编制程序，应用计算机解决一些简单问题.算法思想已经成为现代人应具备的一种数学素养三种算法描述语言即自然语言、程序框图、程序语言.自然语言描述算法通俗易懂，缺点是文字描述比较烦琐，运用不好还容易引发歧义，如加的平方是还是？不好确定；程序框图由表示相应操作的程序框（四种）、带箭头的流程线及必要的文字说明组成，具有直观、形象、方便、动态性强等特点，应用广泛，它能较好地展现算法的三种逻辑结构：顺序结构、条件结构、循环结构；将算法用计算机能够理解的语言表达出来，这就是所谓的程序设计，所用的语言称为程序设计语言.程序设计语言有很多种，它们都是由一些有特定含义的程序语句构成，与程序框图的三种基本结构相对应，任何程序设计语言都包含输入、输出语句、赋值语句、条件语句和循环语句.三种逻辑结构一般算法由顺序、条件和循环三种基本结构组成.顺序结构是由若干个依次执行的处理步骤组成的，这是任何一个算法都离不开的基本主体结构；条件结构是以条件的判断为起始点，根据条件是否成立而决定执行哪一个处理步骤；循环结构是本章的重点内容，它是指在算法设计中，从某处开始有规律地反复执行某一处理步骤，这个处理步骤称为循环体.循环结构分为两种当型和直到型。当型循环在执行循环体前对控制循环条件进行判断，当条件满足时循环，不满足停止；直到型循环在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时循环，满足则停止.四个著名的算法案例教材为我们介绍了四个著名的算法案例，它们首先是算法初步知识的应用，又是古代数学中算法思想的体现，我们应把重点放在通过四个案例的算法分析、程序框图或程序语言设计上，加深对算法思想的理解，至于它们所含算法的应用应以简单题型训练为主.当然，除了这四类问题之外，我国古代以及生活中还有许多有名的算法案例，如：割圆术、韩信点兵、孙子问题等，同学们若有兴趣，可搜集相关资料，了解其算法思想.五种基本算法语句关于程序的编写，是在会画程序框图的基础上，了解五种算法语句及一般格式后进行的，所以，一定要准确把握五种算法语句的一般格式及其作用.循环语句的编写是一难点，含循环结构的算法要分清是“当型循环”还是“直到型循环”，它们有不同的格式.这些难点的突破，在把握准表达格式的同时，多看些典型例子，通过模仿和体验，逐步提高.如何运用程序框图程序框图（简称框图），也称流程图，是一种用规定的图形、指向线和文字说明来准确、直观地表示算法的图形.利用程序框图表示算法，具有直观、形象的特点，能更清楚地展现算法的逻辑结构.程序框图一般由程序框和流程线组成.一个或几个流程框的组合表示算法中的一个步骤；流程线是方向箭头，按照算法进行的顺序将程序框连接起来.基本的程序框有起止框、输入框、输出框、处理框、判断框，其中起止框是任何程序框图不可缺少的，而输入、输出框可以用在需要输入输出的位置.画框图的规则是： 使用标准的框图符号； 框图一般按从上到下、从左到右的方向画； 除判断框外，大多数流程图符号只有一个进入点和一个退出点，判断框是具有超过一个退出点的惟一符号； 一种判断框是“是”与“不是”两分支的判断，而且有且仅有两个结果；另一种是多分支判断，有几种不同的结果；在框图符号内描述的语言要非常简练清楚.任何一种算法都是由三种基本逻辑结构组成的，它们分别是顺序结构、条件结构、循环结构.用这三种基本结构 表述的算法及其框图，整齐美观，容易阅读和理解.顺序结构是最简单、最基本的结构，是任何一个算法都离不开的基本结构，它表示语句和语句之间，框与框之间是按从上到下的顺序进行的.在框图中是用流程线将程序框自上而下连接起来.条件结构是指算法中，根据条件是否成立作出判断，再决定执行哪一种操作的结构.它在程序框图中是用判断框来表示的，判断框内写上条件，它的两个出口分别对应着满足条件和不满足条件时所执行的不同指令.在许多算法中，需要对问题的条件作出逻辑判断，判断后依据条件是否成立而进行的处理方式，这就需要用条件结构来实现算法.循环结构是指在算法中从某处开始，按照一定的条件，反复执行某一处理步骤的结构.反复执行的处理步骤称为循环体.显然，循环结构中有关于条件的判断，因此，循环结构中必包含条件结构.在程序框图中它也是利用判断框表示，判断框内写上条件，它的两个出口分别对应着满足条件和不满足条件时所执行的不同指令，其中一个要指向循环体，然后再从循环体回到判断框的入口处.一般说来，这三种结构贯穿于程序中，相互结合，使程序更完美.但在一个算法中，这三种结构不一定同时存在，可能会有一种或两种不存在，但顺序结构是必不可少的.【例1】“特快专递”是目前人们经常使用的异地邮寄信函或托运物品的一种快捷方式.某快递公司规定甲、乙两地之间物品的托运费用根据下列方法计算：其中f （单位：元）为托运费，为托运物品的重量（单位：千克），试画出计算费用f的程序框图.【思考与分析】 这是一个实际问题，据数学模型可知，求费用f的计算公式随物品重量的变化而有所不同，因此计算时先看物品的重量，在不同的条件下，执行不同的指令，这是条件结构的运用，是二分支条件结构.其中，物品的重量通过输入的方式给出.解：算法程序框图如图 1:【例2】如图 2所示的框图是解决某个问题而绘制的程序框图，仔细分析各图框内的内容及图框之间的关系，回答下面的问题：（1）图框中x=a的含义是什么？（2）图框中y=-x2+mx的含义是什么？（3）该程序框图解决的是怎样的一个问题？（4）当输入的x值为0和4时，输出的值相等，问当输入的x值为3时，输出的值为多大？（5）要想使输出的值最大，输入的x值应为多少？（6）按照这个程序框图，当输入的x值都大于2时，x值大的输出的y值反而小，为什么？【思考与分析】 观察框图的结构和各图框中的内容容易看出，该框图属顺序结构，比较简单，赋给x一个值，由处理框可计算出y的值，再输出y的值.解：（1）图框中x=a表示把a赋给变量x.（2） 图框中y=-x2+mx的含义是：在执行该图框的前提下，即当x=a时计算-x2+mx的值，并把这个值赋给y.（3） 该程序框图解决的是求二次函数f（x）=-x2+mx的函数值的问题.（4） 当输入的x值为0和4时，输出的值相等，即f（0）=f（4）. f（0）=0， f（4）=-16+4m，-16+4m=0， m=4， f（x）=-x2+4x. f（3）=-32+34，当输入的x值为3时，输出的值为3.（5）f（x）=-x2+4x=-（x-2）2+4，当x=2时，f（x）max=4，要想使输出的值最大，输入的x值应为2.（6） f（x）=-（x-2）2+4，函数f（x）在2，+）上是减函数.例析当型与直到型循环结构在程序设计中循环结构是非常重要的一种逻辑结构循环结构又分为当型和直到型两种，同学们在学习使用这两种结构时很容易犯概念不清的错误下面谈谈这两种结构的联系与区别1、教材中对两种结构类型的解释当型循环在每次执行循环体前先对控制条件进行判断，当条件满足时，再执行循环体，不满足时则停止；直到型循环则先在执行了一次循环体之后，再对控制条件进行判断，当条件不满足时执行循环体，满足时则停止2、两种循环的区别当型循环是先判断后循环；直到型循环是先执行一次循环体，然后再判断是否继续循环当型循环是在条件满足时才执行循环体，而直到型循环是在条件不满足时才执行循环体因此在掌握使用这两种循环时必须抓住这两条区别3、例题错误分析例下面的流程图中算法的功能是_分析：功能是求积为624的相邻两个偶数但是本流程图中的循环结构是错误的，出现了当型与直到型的混用、错用如果是当型循环结构,应该是在满足条件时,执行循环体,而本图却是在不满足条件时执行了循环体,这与当型循环结构要求矛盾；本流程图如果采用的是直到型循环结构,则应该先执行一次循环体,然后再对控制条件进行判断,而本题却是先判断,后执行循环体，这与直到型循环结构也是不相适应的正确的应为下面（）、（）两种.例谈生活中的算法问题数学来源于生活，服务于社会新课程标准对应用性问题有较高的要求，贯穿于高中数学的始末数学与生活息息相关，数学是有用的，在生活中做一件事情的方法和步骤有多种，生活中的许多问题都可以用算法描述，用程序框图表达例如：一、国王有多少小麦？图(1)例1相传古印度国王舍罕要奖赏他聪明能干的宰相达尔(国际象棋发明者），问他需要什么，达依尔说：“国王只要在国际象棋的棋盘第一格上放一粒麦子，第二格放二粒麦子，第三格放四粒，以后按比例每一格加一倍，一直放到第64格（国际象棋棋盘是88=64格），我就感恩不尽了，其他我什么也不要了”国王想：“这还不容易！”让人扛来一袋小麦，但不到一会儿全用没了，再来一袋很快又没有了，结果全印度的粮食全部用完还不够国王很奇怪，怎样也算不清这笔账现在我们用电子计算机来算一下，求需要多少体积的小麦(1m3约有1.42 108颗），请你设计一个算法，画出程序框图，用基本语句写出程序. （2011年，我国粮食总产量达到了11424亿斤，三大主粮（水稻、小麦、玉米）首次超过了1万亿斤；人均占有粮食首次达到了850斤）307万亿公斤 世界粮食产量达到创记录的23亿2300万吨23230000000000图（2）程序框图如图所示：程序如下：S=oi=oWHILE i63S= S2ii=i十1 WEND V=S/(1.42*108) PRINT V图(4) END二、申办第29届奥林匹克运动会例2北京获得了2008年第29届奥林匹克运动会主办权国际奥委会是通过对遴选出的5个申办城市进行表决而决定主办权的表决的操作程序是：首先进行第一轮投票，如果一个城市得票超过总票数的一半，那么该城市将获得举办权；如果所有申办城市得票数都不超过总票数的一半，则将得票最少的城市淘汰，然后重复上述过程，直到选出一个申办城市为止请设计一个算法表述上面过程，并画出程序框图图（3）解：算法如下：（1）投票； (2)统计票数，如果有一个城市得票超过总票数的一半，那么该城市就获得主办权；否则淘汰得票数最少的城市，转(1)；(3)宣布主办城市程序框图：如图（1）所示点评：算法本身就是用计算机解决一些实际问题的方法，一定要充分理解算法的程序性、有限性、构造性、精确性、问题的指向性等特点三、购买火车票例3儿童乘火车时，若身高不超过1. 1米，则无需购票，若身高超过11米但不超过1.4米，可买半票；若超过1.4米，应买全票设计一个算法，并画出框图分析：根据题意义，该题的算法中应有条件结构，首先要以身高为标准，分成应买票和免票，在买票中再分半票和全票，根据这一思路，买票的算法步骤如下：第1步：测量儿童身高h；第2步：如果h1.1,那么免费乘车,否则, 如果h1.4.那么买半票乘车,否则买全票.其程序框图如图（2）：解后反思：在这个程序里我们关键要知道两个判断点，一个是以1. lm为判断点，把身高分为两段，在大于1. lm的判断里，一个1.4m的判断把其分两段,因此1.4m这个判断是套在1. lm的判断里,在这里我们用到了程序的嵌套.四、分钱例4某科研所决定拿出一定量的资金对科研人员进行奖励，按照科研成果价值的大小决定奖励前10名第1名得全部奖金的一半多1万元，第二名得剩余的奖金的一半多1万元第三名再得剩余奖金的一半多1万元，依次类推，到第10名恰得奖金1万元，问科研所最初拿出多少万元？分析: 第10名奖金额S10=1万元,第9名奖金额S9=(1+1)2=4万元,第8名奖金额S8=(4+1)2=10万元第1名奖金额S1=( S2+1)2得递推公式Sio1, S n =( S n +1+1)2，n1,29.根据以上解题思路，程序框图为如图(3) 程序为:五、电话费例5.某地电信部门规定：拨打市内电话时，如果通话时间不超过3min通话时间不超过3min,则收取通话费0. 22元；如果通话时间超过3min,则超过部分按每分钟0.1元收取通话费，不足1 min按1 min计设通话时间为t(min)，通话费用为y(元)，如何设计一个计算通话费用的算法程序框图解析:实际上y是关于t的分段函数,关系式为:图(5)t-3表示取不大于t-3的整数部分其算法的程序框图如上图(4)所示：点评:先把实际问题转化为数学问题，再画数学问题的算法的程序框图规律及方法总结:1.正确理解算法的概念，一个程序的算法要本着方便简洁的原则，还要讲究科学性，一个程序的算法步骤是按一定顺序进行的，不具有可逆性2.在设计算法的过程中要牢固把握住它的五个特征：有穷性、确定性、可行性、输人、输出3.正确使用算法的程序框图，在对一个算法透彻地分析的基础上再设计流程图4.设计程序框图时可以分模块进行，把一个大的流程图分割成小的几个模块，先将每个小模块设计好，再按顺序把这些小模块组装好，形成完整的程序流程图5熟悉算法的三种基本逻辑结构的构成模式及其功能，根据问题的需要灵活选择运用辨析程序框图中的易错题例1 画出计算的值的程序框图错解：程序框图如图1所示 辨析：上图中，对所计算的值无法实现累加正解：程序框图如图2所示例2有位同学为了求的值，画出了一个程序框图，如图3所示，请你指出其中的错误，并画出正确的程序框图辨析：第一处错误是在第二个处理框内应是“”，而不是“”；第二处错误是判断框中应是“”，而不是“”，正确的程序框图如图4所示例3求函数的值的算法流程图如图5所示，指出流程图中的错误，并重新写出算法，重新绘制解决该问题的流程图，且回答下面提出的问题问题1：要使输出的值为正