1、第一章 算法初步1.1算法与程序框图11.1算法的概念目标 1.通过学习解二元一次方程组的方法,体会算法的基本思想;2.了解算法的含义和特征;3.会用自然语言表述简单的算法重点 用自然语言表述算法难点 算法的含义及思想的理解知识点一算法的概念 填一填1算法的概念在数学中,算法通常是指按照一定规则解决某一类问题的明确和有限的步骤现在,算法通常可以编成计算机程序,让计算机执行并解决问题2算法的五个特征(1)确定性:算法中每一步都是确定的,并且能有效地执行且得到确定的结果(2)有限性:一个算法的步骤是有限的,不能无限地进行下去,它能在有限步的操作后解决问题(3)有序性:算法从初始步骤开始,分为若干明
2、确的步骤,每个步骤只能有一个确定的后续步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步(4)不唯一性:解决一个问题可以有多种不同的算法(5)普遍性:给出一个算法的程序步骤,它可以解决一类问题,并且能够多次重复使用答一答1解决一个问题的算法是唯一的吗?提示:不是解决一个问题的算法可以有多个,如解二元一次方程组的算法有加减消元法和代入消元法但一般算法有优劣之分结构简单、步骤少、速度快的算法是较好的算法,如对于不同的方程组,有的加减消元简单,有的代入消元简单2是不是任何一个算法都有明确的结果?为什么?提示:是算法中的每一步都是确定的,并且能有效地执行且得到确定的结果,而不应当模棱两可3下列
3、对算法的理解不正确的是(D)A一个算法应包含有限的步骤,而不能是无限的B算法中的每一步都应当是确定的,而不应当是含糊、模棱的C算法中的每一步骤都应当有效地执行,并得到确定的结果D一个问题只能设计出一种算法解析:根据算法的概念及特征判断由算法的有限性知A正确;由算法的确定性可知B正确;由算法的逻辑性知C正确;由算法的不唯一性知D不正确知识点二算法的设计 填一填1算法设计的目的设计算法的目的实际上是寻求一类问题的算法,它可以通过计算机来完成设计算法的关键是把过程分解成若干个明确的步骤,然后用计算机能够接受的“语言”准确地描述出来,从而达到计算机执行的目的2算法设计的要求(1)写出的算法必须能解决一
4、类问题;(2)要使算法尽量简单、步骤尽量少;(3)要保证算法正确,且计算机能够执行答一答4描述算法的方式唯一吗?提示:描述算法可以有不同的方式例如,可以用自然语言和数学语言加以叙述,后面还会学习用程序设计语言给出精确的说明,或者用框图直观地显示算法的全貌5将下面的算法补充完整已知一个学生的语文成绩为89分,数学成绩为96分,外语成绩为99分,求他的总分和平均成绩的一个算法为:第一步,取A89,B96,C99.第二步,计算总分DABC.第三步,计算平均成绩E.第四步,输出D,E.类型一算法的概念 例1下列说法正确的是()A算法就是某个问题的解题过程B算法执行后可以产生不同的结果C解决某一个具体问
5、题算法不同,则结果不同D算法执行步骤的次数不可以很大,否则无法实施解析选项B正确,例如:判断一个整数是否为偶数,结果为“是偶数”和“不是偶数”两种;选项A,算法不能等同于解法;选项C,解决某一个具体问题算法不同,但结果应相同;选项D,算法可以为很多次,但不可以无限次答案B(1)明确算法的含义及算法的五个特征.(2)判断一个问题是否有算法,关键看是否有解决某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步骤之内完成.(3)算法实际上是一种程序方法,在利用算法解决问题时,体现了特殊与一般的数学思想.变式训练1有人对哥德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了
6、如下操作步骤:第一步,检验633.第二步,检验835.第三步,检验1055.利用计算机一直进行下去!请问:利用这种步骤能够证明猜想的正确性吗?这是一个算法吗?解:利用这种步骤不能证明猜想的正确性此步骤不满足算法的有限性,因此不是算法类型二算法的设计 命题视角1:数值性问题的算法设计例2写出求123456的一个算法解法一:第一步,计算12得到3.第二步,将第一步中的运算结果3与3相加得到6.第三步,将第二步中的运算结果6与4相加得到10.第四步,将第三步中的运算结果10与5相加得到15.第五步,将第四步中的运算结果15与6相加得到21.法二:第一步,将原式变形为(16)(25)(34)37.第二
7、步,计算37.设计具体问题的算法的一般步骤(1)分析问题,找出解决问题的一般数学方法;(2)借助有关变量或参数对算法加以表述;(3)将解决问题的过程划分为若干步骤;(4)用简练的语言将这个步骤表示出来变式训练2求1357911的值的一个算法如下,请补充完整第一步,求13得结果3.第二步,将第一步所得结果3乘以5,得到结果15.第三步,再将第二步所得结果15乘以7,得到结果105.第四步,再将第三步所得结果105乘以9,得到结果945.第五步,再将第四步所得结果945乘以11,得到结果10 395,即为最后结果解析:依据算法功能可知,第三步应为“再将第二步所得结果15乘以7,得到结果105”命题
8、视角2:非数值性问题的算法设计例3现有有限个正整数,试设计一个求这些正整数中的最大数的算法分析先假定一个基础数(如第一个数),让它作为其中的最大的数,然后将第二个数与这个基础数比较,将这两者中的较大者再作为基础数与第三个数比较,找出其中的较大者,将其作为基础数与第四个数比较,依此类推,直到与最后一个数比较完毕,就能确定出有限个正整数中的最大数解第一步,先假定这些正整数中的第一个数为“最大数”第二步,将这些正整数中的下一个数与“最大数”比较如果它大于此“最大数”,那么就假定它是“最大数”第三步,如果还有其他正整数,那么重复第二步第四步,一直到没有可比较的数为止,这时假定的“最大数”就是这有限个正
9、整数中的最大数非数值型计算问题,如:排序、查找、变量变换、文字处理等需先建立过程模型,通过模型进行算法设计与描述.设计具体的数学问题的算法,实际上就是寻求一类问题的算法,它可以通过计算机来完成. 变式训练3对任意3个整数a,b,c,写出求最大数的算法解:算法步骤如下:第一步,令maxa.第二步,比较max与b的大小,若bmax,则令maxb;否则max不变第三步,比较max与c的大小,若cmax,则令maxc;否则max不变第四步,max就是a,b,c中的最大数1算法的有穷性是指(C)A算法的最后必包含输出B算法中每个操作步骤都是可执行的C算法的步骤必须有限D以上说法均不正确解析:算法必须在有
10、限步内完成,故选C.2下列各式中S值不可以用算法求解的是(D)AS1234BS1222321002CS1DS1234解析:D中的求和不符合算法步骤的有限性,所以它不可以用算法求解3下面是学生高智“出家门先打车去飞机场,再乘飞机去北京”的一个算法,请补充完整第一步,出家门第二步,打车去飞机场第三步,乘飞机去北京4写出求123456100的一个算法,可运用公式123n直接计算第一步:取n100;第二步:计算S;第三步:输出计算的结果5解关于x的方程ax20(aR),写出算法解:算法如下:第一步,移项,得ax2.第二步,当a0时,x,输出x,结束算法当a0时,输出方程无实根,结束算法本课须掌握的三大问题1算法与一般意义上数学问题的解法是一般与特殊的关系,算法是“通用”的方法,是解决某一类问题的程序和步骤,而解法则是算法的具体体现,是在解决具体问题时将算法的各个步骤具体化2算法是“傻瓜化”的,相对于某一类问题的算法,不能省略任何一个小步骤,不能忽略任何一种可能的情况,否则计算机都不能完成执行过程,而只要按照算法一步一步进行,这类问题都会得到解决3加、减、乘法运算法则、多项式的运算法则以及我们学过的许多数学公式等都是算法