1.1.1算法的概念整理.ppt

1、第一章 算法初步,3,算法自古就有，中国古代数学在 世界数学史上一度占居领先地位她 注重实际问题的解决，以算法为中心， 寓理于算，其中蕴涵了丰富的算法思 想算筹是中国古代的计算工具，在春秋时期已经很普遍，算盘在明代开始盛行中国古代涌现了许多著名的数学家，如三国、两晋的赵爽、刘徽，南北朝的祖冲之、祖暅父子，宋、元的秦九韶、杨辉、朱世杰等.著名的数学专著有九章算术、周髀算经、数书九章、四元玉鉴、黄帝九章算法细草、议古根源、数书九章、详解九章算法和杨辉算法等,内容简介,1.1 算法与程序框图,本章共分3大节,1.2 基本算法语句,1.3 中国古代数学中的算法案例,1.1.1 算法的概念,山东省齐河第

2、一中学 冯钢柱,学习目标,1.通过已学过的二元一次方程组的方法，初步认识、体会算法的基本思想。,2.了解算法的含义、特征。,学习重点,根据求解数学问题的一般方法与步骤，体会算法的基本思想。,创设情景,要把大象装冰箱，分几步？哈哈,问题1：,现有九枚硬币，有一枚略重，你能用天平(不用砝码)将其找出来吗？设计一种最有效的方法，解决这一问题。,S1：把九枚硬币平均分成三份，取其中两份放天平上称，若平衡则重的在剩下的一份里，若不平衡则在重的一份里；,S2：在重的一份里取两枚放天平的两边，若平衡则剩下的一枚就是所找的，若不平衡则重的那枚就是所要找的。,问题2：,问题3：,一个农夫带着一只狼、一头山羊和一

3、篮蔬菜要过河，但只有一条小船。乘船时,农夫只能带一样东西。当农夫在场的时候,这三样东西相安无事，一旦农夫不在，狼会吃羊，羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。,S1:农夫带羊过河;,S2:农夫独自回来;,S3:农夫带狼过河;,S4:农夫带羊回来;,S5:农夫带蔬菜过河;,S6:农夫独自回来;,S7:农夫带羊过河。,广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。 在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的算法

4、，等等。,算法的概念,算法可以理解为由基本运算及规定的运 算顺序所构成的完整的解题步骤，或者 看成按照要求设计好的有限的确切的计 算序列，并且这样的步骤或序列能够解 决一类问题。,算法的表示,描述算法可以有不同的方式,常用的有自然语言、程序框图、程序设计语言等.,(1)自然语言,自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向,并且操作步骤较多时,就不那么直观清晰了.,(2)程序框图,1.1.2程序框图中讲解,(3)程序语言,1.2基本算法语句中讲解,怎样才能设计出一个

5、名副其实 的算法呢？,例1 “一群小兔一群鸡，两群合到一群里，要数腿共48，要数脑袋整17，多少小兔多少鸡？”,解：算术方法：如果没有小兔，那么小鸡应为17只，总的腿数应为217=34条，但现在有48条腿，造成腿的数目不够是由于小兔的数目为0，每有一只小兔便会增加两条腿，故应有(48172) 2=7只小兔。相应的，小鸡有10只。,代数方法：设有x只小鸡，y只小兔. 则,将第一个方程的两边同乘以2加到第二个方程中去，得到,解第二个方程得y=7.,把y代入到第一个方程得x=10.,思考1： 教材中例1是著名的“鸡兔同笼”问题，其中第一种解法是算术方法，教材中对它的评价是“简单直观，却包含着深刻的算

6、法思想”，那么它是如何体现算法的思想呢？,S1 假设没有小兔，则小鸡应为n只； S2 计算总腿数为2n只； S3 计算实际总腿数与假设总腿数的差值为m2n；,S4 计算小兔只数为 ;,S5 小鸡的只数为n .,思考2 教材中例1的第二种解法是列方程组的方法，它是否也是一种算法呢？ 探究：是的，其算法步骤为：,S1 设未知数； S2 根据题意列方程组； S3 解方程组； S4 还原实际问题，得到实际问题的答案。,在实际中，很多问题可以归结为求解二元一次方程组，下面我们用消元法来解一般的二元一次方程组,S1 假定a110，a11a21得,S2 如果a11a22a12a210，则执行下步； 否则执行

7、S6,S3 两边同除以a11a22a12a210得,S4 代入.得,S5 输出结果x1，x2，,S6 若a11b2a21b10. 则执行下一步；否则执行S8,S7 输出“方程组无解”.,S8 输出“方程组有无穷多个解”,以上解二元一次方程组的方法，叫做高斯消去法,事实上，我们可以将一般的二元一次方程组的解法转化成计算机语言，做成一个求解二元一次方程组的程序.,这儿已经做好了，试一试吧！,算法的要求,(1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用;,(2) 算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且经过有限步之后能得出结果.,例

8、2 写出一个求有限整数序列中的最大值的算法。,解：算法如下： S1 先假定序列中的第一个整数为“最大值”; S2 将序列中的下一个整数值与“最大值”比较，如果它大于此“最大值”，这时你就假定“最大值”是这个整数； S3 如果序列中还有其他整数，重复S2; S4 在序列中一直到没有可比的数为止，这时假定的“最大值”就是这个序列中的最大值。,如果让你去找，你可能不会这样做，可能认为，这样太机械、太枯燥。不要忘了，我们写的是算法。算法要求按部就班地做，每一步都有唯一的结果，又要求写出的算法对任意整数序列都适用，总能得到结果。所以上面写的，符合算法的要求。,S1 max=a S2 如果bmax, 则m

9、ax=b. S3 如果Cmax, 则max=c. S4 max就是a, b, c中的最大值。,下面我们用数学语言，写出对任意3个整数a，b，c求出最大值的算法。,练习 写出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步,计算=b2-4ac.,第二步,如果0,则原方程无实数解 ;否则(0)时，,第三步:输出x1, x2或无实数解.,例3 设计算法解决下面的问题：已知点P的坐标为(x0，y0)，直线l的方程为ax+by+c=0 (ab0)，求点P到直线l的距离.,算法一： S1 求出直线l的斜率为k， ；,S2 求出与l垂直的直线的斜率k， ；,S3 求出过点P且与直线l垂直的直线l方程，直线l的方程为,S4 求出直线l和l的交点M的坐标；把l和l联立，得方程组,由此可以得到点M的坐标为,S5 把点M的横坐标和纵坐标分别赋值给变量x1，y1；,S6 把点(x1，y1)代入两点间距离公式，计算求得d的值；,算法二： S1 计算 的值 S2 计算z0=|ax0+by0+c|的值. S3 计算 得所求的距离.,不唯一性:求解某一个问题的算法不一定是唯一的，对于一个问题可以有不同的算法,2.算法的特点：思路简单清晰，叙述复