1.1.1算法的概念
教学目标:
1.知识与技能目标
(1)了解算法的含义,体会算法的思想。 (2)能够说明解决简单问题的算法步骤。
(3)了解正确的算法应满足的要求,即算法的特点。
(4)初步了解高斯消去法的思想,会写出解线性方程(组)的算法。 (5)了解利用Scilab求二元一次方程组解的方法。 2.过程与方法目标
通过分析高斯消去法的过程,体会算法的思想,发展对具体问题的过程与 步骤的分析能力,发展从具体问题中提炼算法思想的能力,发展有条理地清晰地 思维的能力,提高学生的算法素养。
3.情感、态度与价值观目标
通过本节的学习,使我们对计算机的算法语言有一个基本的了解,明确算法的要求,认识到计算机是人类征服自然的一各有力工具,进一步提高探索、认识世界的能力。
重点:算法的概念和算法的合理表述。 难点:算法的合理表述、高斯消去法。
教学过程:
一、引入新课
1.要把大象装入冰箱分几步? 第一步 把冰箱打开。 第二步 把大象放进冰箱。 第三步 把冰箱门关上。
2.组织学生模拟参加幸运52的竞猜游戏。
价格竞猜中我们运用了曾经学过的二分法的数学思想。利用二分法求函数的零点时,我们是一步一步进行的,每一步都能得到一个结果,如果结果满足精确度则停止运算;若不满足则继续寻找,直到找到满足精确度的结果为止。这样的求解过程就是这一类问题的算法。今天我们就来学习算法的概念。
我们学过的求函数零点的二分法以及在解析几何初步中利用公式计算的几何问题进行
分步求解,这些计算方法都有一个共同的特点,就是对一类问题(不是个别问题)都有效,计算可以一步一步地进行,每一步都能得到惟一的结果,通常我们把这一类问题的求解过程叫做解决这一类问题的算法。这些算法虽然很机械,计算量大,但优点是一种通法,只要按部就班地去做,总能算出结果。通常把算法过程成为“数学机械化”,数学机械化最大的优点是它可以利用计算机来完成。所以学习算法是为了学习编辑程序,让计算机去帮助我们去解决更多的问题。
用学生熟悉的问题来引入算法的概念,降低新课的入门难度,有利于学生正确理解算法的概念。 二.新课讲解
随着计算科学和信息技术的飞速发展,算法的思想已经渗透到了社会的方方面面。在以前的学习中,虽然没有出现算法这个名词,但是实际在数学学习中已经渗透了大量的算法的思想,如四则运算的过程(先乘除后加减),完成这些工作都需要一系列程序化的步骤,这就是算法的思想。
(一)算法的概念:算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤,或看成按要求设计好的有限的、确切的计算序列,并且这样的步骤或序列能解决一类问题。
(二)描述算法的方式:自然语言、数学语言、形式语言、框图语言 【例1】写出你在家中烧开水的过程。 解: S
1、往壶内注水; S
2、点火加热;
S3、观察:如果水开,则停止烧火,否则继续烧火; S
4、如果水未开,重复“3”直至水开。
总结:1其实大部分事情都是按照一定的程序执行,因此要理清事情的每一步。2判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程,因此有必要不断重复过程3 。
广义地说,对于一项任务,按照事先设计好的步骤,一步一步地执行并在有限步内完成任务,则这些步骤称为该任务的一个算法.简单地说,算法就是就是完成工作所需要的一系列程序化的步骤,就是做某一件事的步骤或程序。菜谱是做菜肴的算法,洗衣机的使用说明书是操作洗衣机的算法,歌谱是一首歌曲的算法。在数学中,主要研究计算机能实现的算法,即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的算法,等等。
【例2】一群小兔一群鸡,两群合到一群里,要数腿共48,要数脑袋整17,多少小兔
多少鸡?
算法1:
解 :S1 首先计算没有小兔时,小鸡的数为:17只,腿的总数为34条。
S2 再确定每多一只小兔、减少一只小鸡增加的腿数2条。 S3 再根据缺的腿的条数确定小兔的数量: (48-34)/2=7只 S4 最后确定小鸡的数量:17-7=10只.算法2:
解 :S1 首先设x只小鸡,y只小兔。
2x4y48S2 再列方程组为:
xy17S3 解方程组得:y7
x10S4 指出小鸡10只,小兔7只。
本题讲解紧扣算法的定义,层层诱导,提示学生如何设计步骤,可以先由学生提出,师生共同总结。最后提示学生,一个问题算法可能不止一个。深化对算法概念的理解,使学生体会到算法并不是高渗莫测的东西,实际上是我们从前解题步骤的总结。
再归纳一般二元一次方程组的通用方法,即用高斯消去法解一般的二元一次方程组
a11x1a12x2b1。 a21x1a22x2b2S1 假定a110(如果a110,可以将第一个方程与第二个方程互换), ① (a21aaab)②,得到: (a222112)x2b2211 a11a11a11原方程组化为:
(3)a11x1a12x2b1 aaaaxabab (4)211221122111122S2 如果a11a22a21a120,输出方程组无解或有无数组解
如果a11a22a21a120,解(4)得x2a11b2a21b1 (5)
a11a22a21a1
2S3 将(5)代入(3),整理得:x1a22b1a12b2 (6)
a11a22a21a12S4 输出结果x1,x
2、方程组无解或有无数组解
令Da11a22a21a12,若D0,方程组无解或有无数多解。 若D0,则x1b1a22b2a12bab1a21,x2211。
DD由此可得解二元一次方程组的算法。
S
1计算Da11a22a21a12;
S
2如果D0,则原方程组无解或有无穷多组解;否则(D0),
x1b1a22b2a12bab1a21,x2211
DDS
3输出计算结果x
1、x2或者无法求解的信息。
(三)写算法的要求
算法不同于求解一个具体问题的方法,是这种方法的高度概括。一个好的算法有如下要求:
1.求解的过程是事先确定的,事先都考虑好了,有确定的步骤.2.写出的算法,必须能解决一类问题(如一元二次方程求根公式),并且能重复使用。 3.算法执行过程中的每一步都是能够做到的,要简洁,要清晰可读,不能弄搞繁杂,以以致于易程序化。
4.算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且在有限步内有结果,应完成给定的任务。
(四) 算法的特征
确定性,通用性,可行性,有穷性,有输出
【例3】.写出一个求有限整数序列中的最大值的算法。 解:为了便于理解,算法步骤用自然语言叙述: 算法1:
S1 先假定序列中的第一个数为“最大值”。
S2 将序列的第二个整数值与\"最大值\"比较,如果第二个整数大于“最大值”,这时就假定这个数为“最大值”。
S3 将序列的第三个整数值与“最大值”比较,如果第三个整数大于“最大值”,这时就假定这个数为“最大值”。
S4 将序列的第四个整数值与“最大值”比较,如果第四个整数大于“最大值”,这时就假定这个数为“最大值” 依此类推
Sn 将序列的第n个整数值与“最大值”比较,如果第n个整数大于“最大值”,这时就假定这这个数为“最大值”。
Sn+1 直到序列中没有可比的数为止,“最大值”就是序列的最大值。 算法2 S1 先假定序列中的第一个数为“最大值”。
S2 将序列中的下一个整数值与\"最大值\"比较,如果大于“最大值”,这时就假定这个数为“最大值”。
S3 如果序列中还有其它整数,重复S2。
S4 直到序列中没有可比的数为止,这时假定的“最大值”就是序列的最大值。 带领学生分析题目,找出算法。让学生观察算法1,思考如何简化算法?让学生体会到算法的特点是:“机械的、呆板的、可以按部就班执行”,体会到学习算法的意义和必要性。体会到算法优化的意义,指出算法要设计合理,运行要高效,让学生体会顺序结构的简单直观,但有时却很繁琐的特点。促使学生产生改进方法的欲望。
试用数学语言写出对任意3个整数a、b、c中最大值的求法
S
1max=a S
2如果b>max,则max=b S
3如果c>max,则max=c, S
4max就是a、b、c中的最大值。
三、巩固练习
1.给出求100!123100的一个算法。
2.给出求点P(x0,y0)关于直线AxByC0的对称点的一个算法。
3.一位商人有9枚银元,其中有1枚略轻的是假银元。你能用天平(不用砝码)将假银元找出来吗?
四、课堂小结:
1.算法的概念:由基本运算及规定的运算顺序所构成的完整的解题步骤,或者是按照要求设计好的有限的计算序列,并且这样的步骤或序列能解决一类问题。
2.描述算法的方式:自然语言、数学语言、形式语言、框图语言 3.算法的特征:确定性,通用性,可行性,有穷性,有输出
五、作业
P7练习A
P8练习B
1、
2、3