庖丁巧解牛
知识·巧学
一、算法的含义 1.算法的定义
广义的算法是指完成某项工作的方法和步骤,所以我们可以说洗衣机的使用说明书是操作洗衣机的算法,菜谱是做菜的算法,等等.
在数学中,现代意义上的算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤,或看成按要求设计好的有限的确切的计算序列. 2.算法的要求
我们现在学习的算法不同于求解一个具体问题的方法,它有如下要求: (1)写出的算法可适用于一类问题,并且再遇到类似问题时能够重复使用;
(2)算法过程要做到能一步一步地执行,每一步执行的操作,必须确切,不能含混不清,且在有限步后必须得到问题的结果.
辨析比较 算法与数学问题的解法既有联系又有区别.
(1)联系:算法与解法是一般与特殊的关系,也是抽象与具体的关系.譬如,教材先从分析一个具体的二元一次方程组的求解过程(解法)出发,归纳出了二元一次方程组的求解步骤;并且指出,这样的求解步骤也适合有限制条件的二元一次方程组,这些步骤就构成了解二元一次方程组的算法;
(2)区别:算法是解决某一类问题所需要的程序和步骤的统称,也可理解为数学中的“通法通解”;而解法是解决某一个具体问题的过程和步骤,是具体的解题过程. 二、算法的特征及设计要求 1.算法的特征
对于某一个问题,找到解决它的某种算法是指使用一系列运算规则能在有限步骤内求解某类问题,其中的每条规则必须是明确定义的、可行的,不能含糊其辞、模棱两可,同时应对所有的初始数据(而不仅是指对某些特殊数值)有效.
算法从初始步骤开始每一个步骤只能有一个确定的后继步骤,从而组成一个步骤序列,这个序列必须是有限的,序列的终止表示问题得到解决或指出问题没有解答.
我们过去学习过的许多数学公式都是算法,加、减、乘、除运算法则以及多项式的运算法则也是算法.
算法可以概括出以下几个特点:
(1)概括性:写出的算法必须能解决这一类问题,并能重复使用.例如课本中关于二元一次方程组的求解问题,也适用于其他二元一次方程组的解法.
(2)逻辑性:也就是算法应具有正确性和顺序性.算法从初始步骤开始,分为若干明确的步骤,前一步是后一步的基础,只有执行完前一步才能进行下一步,并且每一步都有确切的含义,从而组成了一个具有很强逻辑性的序列.
(3)有穷性:算法的步骤序列是有限的.一个算法对任何合法的输入值必须总是在执行有穷步之后结束,且每一步都可在有穷时间内完成.
(4)不唯一性:求解某个问题的算法不是唯一的,对于一个问题可以有不同的算法,如课本关于二元一次方程组的求解问题可以用公式法,也可以用高斯消去法.
(5)普遍性:很多具体的问题,都可以设计合理的算法去解决,例如心算、手算、计算器计算都要经过有限的、事先设计好的步骤去加以解决,同样一个工作计划、教学计划、生产流程都可以称为“算法”.
辨析比较 课本上有两种表示算法的语言:自然语言和算法语言.对于这两种算法,用自然语言叙述的算法便于理解,但比较冗长,而且操作性不是十分明朗;用数学语言描述的算法十
分简洁,而且清晰,操作性强,但较抽象. 2.算法的设计要求
首先我们要知道,通常算法并不给出精确的解,而是说明如何得到解.算法由一系列加减乘除等运算以及顺序、判断、循环的操作指令完成.研究算法只是将研究解决一类问题的方法分解成一些合理的操作步骤.这些操作步骤必须明确有效并且能在有限步内完成.
如何设计一个算法呢?首先应该从头到尾将这个问题解决的思路,以及各种可能出现的情况都想到,并且进行抽象概括.然后对过程进行细分,把每一个操作概括为一个简洁的算法语句,最后将算法一步步地写出来.一般情况下,一个问题对应很多不同的算法,我们在实际应用中可以选择一个效率最高的算法. 算法设计的要求:
(1)写出的算法必须能解决一类问题(如判断一个任意整数n是否为质数,求任意一个函数式的近似解等),并且能重复使用.
(2)要使算法尽量简单,步骤尽量少,算法从初始步骤开始,每一个步骤只能有一个后继步骤,从而组成一个步骤序列,序列的终止表示问题得到解答或指出问题没有答案.
(3)算法过程要能一步一步执行,每一步执行的操作,必须确切不能含糊不清,而且在有限步后能得出结果.
(4)尽量地从步骤和思想上优化算法,使得算法效率最高.
深化升华 (1)算法实际上就是解决问题的一种程式化方法,它通常指向某一个或某一类问题,而解决的过程具有程序性和构造性.算法又可看成是一种解决问题的特殊的有效方法,我们在学习的过程中应重点学习算法的构造过程.
(2)算法与一般的解决问题的过程有联系,但算法是“傻瓜化”的,即算法要“面面俱到”,不能省略任何一个小小的步骤(只有这样做,人们才能在设计出算法后,把具体的执行过程交给计算机去完成).
三、算法的描述
描述算法可以用不同的方式.例如:可以用自然语言和数学语言加以叙述,也可以借助形式语言(算法语言)给出精确的说明,还可以用程序框图直观地显示算法的全貌. 1.自然语言
自然语言就是人们日常使用的语言,可以是人们之间用来交流的语言、术语等,它通过分步的方式表达解决问题的过程.
优点:好理解,当算法的执行都是先后顺序时比较容易理解.
难点:表达冗长,且不易表达清楚步骤间的重复操作、分情况处理、先后顺序等问题. 2.程序框图
程序框图是用规定的图形符号来表达算法的具体过程. 优点:简捷形象、步骤的执行方向直观明了. 3.程序语言
程序语言是将自然语言和框图所表达的解决问题的步骤用特定的计算机可识别的低级或高级语言编写而成的.
特点:能在计算机上执行,但格式要求严格. 四、程序框图 1.程序框图的定义
程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形.
打个比方,写文章要先拟提纲,盖楼房要先设计图纸,而计算机解题要先考虑算法,然后编制程序框图,程序框图是人们用来描述算法步骤的形象化的方法.
在程序框图中,每一个框都清楚地表示了这一步要做的事,框与框之间的箭头表示相邻两框所做事情的先后顺序,每一种不同形状的框表示不同的操作方法!若把程序框图画出来,对编者来说,思路清晰,逻辑关系一目了然,尤其是在一些较复杂的程序编制中更为实用. 2.构成程序框图的图形符号及其作用
通常,程序框图由程序框和流程线来组成.一个或几个程序框的组合表示算法的一个步骤;流程线是方向箭头,按照算法进行的顺序将程序框连接起来. 程序框图表示算法用到的图形符号如下表:
图形符号 名称 符号表示的意义
起止框 流程图的开始或者结束
输入输出框 数据的输入或者结果的输出
处理框 赋值、执行计算语句、结果传送
判断框 流程线 连结点
根据给定的条件判断 流程进行的方向
连接另一页或另一部分程序框图
学法一得 作程序框图的规则及注意点:
(1)每一种程序框图的符号都有自己的意义,不能混用,符号一定要规范.起始框只有一条流出线,终止框只有一条流入线,输入输出框和处理框只有一条流入线和流出线.判断框有一条流入线和两条流出线(True,False).
(2)流程图的画法是从上而下、从左而右的方向画.一个算法的步骤到另一个算法的步骤,要用流程线连接.流程线要带箭头,表明流程执行的次序.
(3)起止框是任何程序框图必不可少的,表明程序的开始和结束. (4)算法中间要处理的数据,一般分别写在不同的处理框内.
(5)当算法要对两个不同的结果进行判断时,判断条件写在判断框内. (6)程序框图符号框内的文字表述要简洁精炼.
(7)一般情况下,我们先用自然语言编写算法,然后再画程序框图. 3.程序框图的构成
一个程序框图包括以下几部分:
(1)实现不同算法功能的相对应的程序框图的图形符号; (2)带箭头的流程线;
(3)程序框内必要的说明文字. 五、顺序结构
算法含有两大因素:一是操作,主要包括算术运算、逻辑运算、函数运算等;二是逻辑结构.逻辑结构控制着算法的各操作的执行顺序.我们写出的或画出的程序框图,一定要使大家看得清楚、明白、容易阅读.如果写的算法毫无头绪,就让人很难阅读和理解.这就要求算法要有一个良好的结构.
通常一个算法只能由三种基本逻辑结构组成,算法的三种基本逻辑结构分别为:顺序结构、条件结构、循环结构.
顺序结构是最简单的算法结构,语句与语句之间,框与框之间是按从上到下的顺序进行的.
它是由若干个依次执行的步骤组成的,是任何一个算法都离不开的一种基本算法结构. 我们可以用图1-1-1表示,其中的A部分,B部分是依次执行的.只有在执行完A部分的操作后,才会顺次执行B部分的操作.
图1-1-1
深化升华
顺序结构是从上而下依次执行命令,每步只执行一次,不会引起程序步骤的跳转.它只能解决一些简单的问题,步骤之间不能随便调换,调换会使算法不运行或出现错误.单独的顺序结构一般出现在这样几种题目中:根据公式求值、求一般函数(非分段函数)的函数值等;再者顺序结构是其他结构的基础,会出现在其他结构的运行的前后,是算法必需的一个基本结构. 六、条件结构
其实对于条件结构我们遇到的最早,我们遇到一个岔路口,你需要选择向哪走;“鱼和熊掌不能兼得”也只有一个选择;还有我们去坐出租车有3千米以内7元,3千米以外每千米3元的收费标准;等等.这些都是条件结构.显然,条件结构中有一个条件和两个分支,根据条件判断到底来选择哪个分支.
在一个算法中,通常会遇到一些条件的判断,算法的流程根据条件是否成立有不同的流向,这种先根据条件判断,再决定执行哪一种操作的结构称为条件结构.
图1-1-2所示的虚线框内是一种条件结构,此结构中包含一个判断框,根据给定的条件P是否成立而选择A框或B框,请注意无论条件P是否成立,只能执行A框或B框之一,不可能既执行A框又执行B框,也不可能A框、B框都不执行,无论走哪一条路径,在执行完A或B之后,脱离本条件结构.当然A或B两个框中可以有一个是空的,即不执行任何操作,如图1-1-3也是条件结构的一种.
图1-1-2 图1-1-3
辨析比较 条件结构不同于顺序结构的地方是:它不是依次执行操作指令进行运算,而是依据条件作出逻辑判断,选择执行不同指令中的一个.一般地,这里的判断主要是判断“是”(即“Y”)或“否”(即“N”),即是否符合件的要求,因而它有一个入口和两个出口. 七、循环结构
在一些算法中,经常会出现从某处开始,按照一定的条件,反复执行某一处理步骤的情况,这就是循环结构.反复执行的处理步骤称为循环体.显然,循环结构中有关于条件的判断.因此,循环结构中必包含条件结构.
我们先看一个小例子,比如我们要计算1×2×3×4×…×100,该怎么办呢?我们知道最直接的办法:
相关推荐：
loading