1、第二章 算法初步,1 算法的基本思想,学习目标 1.了解算法的含义，体会算法的思想，能够用自然语言叙述算法. 2.掌握正确的算法应满足的要求. 3.学会将一整数分解成素因数之积，会设计求两整数的最大公因数的算法，了解“韩信点兵”问题及二分法求方程近似解.,题型探究,问题导学,内容索引,当堂训练,问题导学,有一碗酱油，一碗醋和一个空碗.现要把两碗盛的物品交换一下，试用自然语言表述你的操作方法.,思考,知识点一 算法的概念,答案,先把醋倒入空碗，再把酱油倒入原来盛醋的碗，最后把倒入空碗中的醋倒入原来盛酱油的碗，就完成了交换.,梳理 一般地，算法是解决某类问题的一系列 ，只要按照这些步骤执行，都能使
2、问题得到解决.一般来说，“用算法解决问题”都是可以利用 帮助完成的. 同一个问题可能存在多种算法，一个算法也可以解决某一类问题.,步骤或程序,计算机,知识点二 算法的特点,思考,设想一下电脑程序需要计算无限多步，会怎么样？,若有无限步，必将陷入死循环，解决不了问题.故算法必须在有限步内解决问题.,答案,梳理 一般地，算法的特点有： (1)有穷性 一个算法应包括 的操作步骤，能在执行有穷的操作步骤之后 . (2)确定性 算法的计算规则及相应的计算步骤必须是唯一确定的. (3)可行性 算法中的每一个步骤都是可以在 的时间内完成的基本操作，并能得到 的结果.,有限,结束,确定,有限,题型探究,例1
3、在电视台的某个娱乐节目中，要求参与者快速猜出物品价格.主持人出示了一台价值在1 000元以内的随身听，并开始了竞猜.下面是主持人和参与者之间的一段对话： 参与者：800元！ 主持人：高了！ 参与者：400元！ 主持人：低了！ 参与者：600元！ 主持人：低了！ 试把参与者的竞猜策略概括成一系列的步骤.,类型一 生活中的算法案例,解答,1.报出首次价格T1； 2.根据主持人的回答确定价格区间：(1)若报价小于商品价格，则商品的价格区间为(T1,1 000)； (2)若报价大于商品价格，则商品的价格区间为(0，T1)； (3)若报价等于商品价格，则游戏结束. 3.如果游戏没有结束，则报出上面确定的
4、价格区间的中点T2.,按照上述方法，继续判断，直到游戏结束.像这样的一系列步骤通常称为解决这个问题的一个算法.生活中有很多蕴含算法思想的案例.,反思与感悟,跟踪训练1 一个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡1个大人或两个小孩，他们三人都会划船，但都不会游泳.试问他们怎样渡过河去？请写出一个渡河方案.,解答,1.两个小孩同船过河去； 2.一个小孩划船回来； 3.一个大人划船过河去； 4.对岸的小孩划船回来； 5.两个小孩同船渡过河去.,类型二 数学中的算法思想,例2 设计一个算法，求840与1 764的最大公因数.,解答,算法步骤如下： 1.先将840进行素因数分解：84023
5、357； 2.然后将1 764进行素因数分解：1 764223272； 3.确定它们的公共素因数：2,3,7； 4.确定公共素因数的指数：公共素因数2,3,7的指数分别为2,1,1； 5.最大公因数为22317184.,以上这个算法的思想具有一般性，它可以帮助设计求三个或者三个以上正整数的最大公因数的算法.,反思与感悟,跟踪训练2 设计一个算法，求98与63的最大公因数.,解答,算法步骤如下： 1.先将98进行素因数分解：98272； 2.然后将63进行素因数分解：63327； 3.确定它们的公共素因数：7； 4.确定公共素因数的指数：公共素因数的指数是1； 5.最大公因数为7.,例3 “韩信
6、点兵”问题 韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳.据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力.采用下述点兵方法：先令士兵从13报数，结果最后一个士兵报2；再令士兵从15报数，结果最后一个士兵报3；又令士兵从17报数，结果最后一个士兵报4.这样，韩信很快就算出了自己部队士兵的总人数.请设计一个算法，求出士兵至少有多少人.,解答,算法步骤如下： 1.首先确定最小的满足除以3余2的正整数：2； 2.依次加3就得到所有除以3余2的正整数：2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,56
7、， 3.在上列数中确定最小的满足除以5余3的正整数：8； 4.然后依次加上15，得到8,23,38,53， 不难看出，这些数既满足除以3余2，又满足除以5余3； 5.在第4步得到的一列数中找出满足除以7余4的最小数53，这就是我们要求的数.,在完成上述步骤后，就找到了所求的数53，这5个步骤称为解决“韩信点兵”问题的一个算法.,反思与感悟,跟踪训练3 在例3中，我们颠倒一下3,5,7的顺序，请再设计一个算法.,解答,算法步骤如下： 1.首先确定最小的除以7余4的正整数：4； 2.依次加7就得到所有除以7余4的正整数：4,11,18,25,32,39,46,53,60， 3.在第2步得到的一列数
8、中确定最小的除以5余3的正整数：18； 4.然后依次加上35，得到18,53,88， 5.在第4步得到的一列数中找出最小的满足除以3余2的正整数：53.,类型三 用二分法求方程近似解,例4 求方程x3x210在0,1上的近似解，精度为0.1.,解答,根据上述分析，可以通过下列步骤求得方程的近似解： 设f(x)x3x21， 1.因为f(0)1，f(1)1，f(0)f(1)0.1； 5.取0.5,1的区间中点0.75； 6.计算f(0.75)0.015 625；,7.由于f(0.75)f(1)0.1； 8.取0.75,1的区间中点0.875； 9.计算f(0.875)0.435 546 875；
9、10.由于f(0.75)f(0.875)0.1； 11.取0.75,0.875的区间中点0.812 5； 12.计算f(0.812 5)0.196 533 203 125； 13.由于f(0.75)f(0.812 5)0，可得新的有解区间0.75,0.812 5，0.812 50.750.062 50.1. 所以，区间0.75,0.812 5中的任一数值，都可以作为方程的近似解.,二分法求方程近似解的基本思想：逐渐缩小有解区间的长度，直到满足精度的要求.虽然看似烦琐，但很适合计算机执行.,反思与感悟,跟踪训练4 用二分法设计一个求方程x220的近似正根的算法，精度为0.05.,解答,1.因为f
10、(1)1，f(2)2，f(1)f(2)0.05； 2.取1,2的中点1.5； 3.计算f(1.5)0.25； 4.由于f(1)f(1.5)0.05； 5.取1,1.5的中点1.25；,6.计算f(1.25)0.437 5； 7.由于f(1.25)f(1.5)0.05； 当得到新的有解区间1.406 25,1.437 5时， 由于|1.437 51.406 25|0.031 250.05， 该区间精度已满足要求，所以取区间1.406 25,1.437 5的任一数值，都可以作为方程的一个近似解.,当堂训练,1.下列关于算法的说法，正确的个数为 求解某一类问题的算法是唯一的； 算法必须在有限步操作之
11、后停止； 算法的每一步操作必须是明确的，不能有歧义或模糊； 算法执行后一定产生确定的结果. A.1 B.2 C.3 D.4,答案,解析,由于算法具有有穷性、确定性、输出性等特点，所以正确，而解决某类问题的算法不一定唯一，所以错误.,2,3,4,1,2.已知一个算法： (1)给出三个数x、y、z； (2)计算Mxyz； (3)计算N 1 3 M； (4)得出每次计算的结果. 则上述算法是 A.求和 B.求余数 C.求平均数 D.先求和再求平均数,答案,解析,由算法过程可知，M为三数之和，N为这三数的平均数，故选D.,2,3,4,1,3.看下面的四段话，其中不是解决问题的算法是_. (1)从济南到
12、北京旅游，先坐火车，再坐飞机抵达； (2)解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1； (3)方程x210有两个实根； (4)求12345的值，先计算123，再计算336,6410,10515，最终结果为15.,2,3,4,1,答案,解析,由于(3)不是解决某一类问题的步骤，故(3)不是解决问题的算法.,(3),4.已知直角三角形两直角边长为a，b，求斜边长c的一个算法分下列三步： (1)计算c ； (2)输入直角三角形两直角边长a，b的值； (3)输出斜边长c的值. 其中正确的顺序是_.,答案,解析,算法的步骤是有先后顺序的，第一步是输入，最后一步是输出，中间的步骤是赋值、计算.,2,3,4,1,(2)(1)(3),算法是建立在解法基础上的操作过程，算法不一定要有运算结果，答案可以由计算机解决，算法没有一个固定的模式，但有以下几个基本要求： (1)符合运算规则，计算机能操作； (2)每个步骤都有一个明确的计算任务； (3)对重复操作步骤返回处理； (4)步骤个数尽可能少； (5)每个步骤的语言描述要准确、简明.,规律与方法,本课结束,