21-算法的基本思想

《21-算法的基本思想》由会员分享，可在线阅读，更多相关《21-算法的基本思想（29页珍藏版）》请在装配图网上搜索。

1、北师大必修三 第二章 算法 第一课时第一课时 作为家里的一员，在平时分担一些力所能及的事是作为家里的一员，在平时分担一些力所能及的事是我们应尽的义务，你每天都帮家里做事吗？你会煮我们应尽的义务，你每天都帮家里做事吗？你会煮饺子吗？请写出你在家中饺子吗？请写出你在家中煮饺子煮饺子的过程的过程 1 1、往锅子内注水；、往锅子内注水； 2 2、点火加热，等水沸腾后，放入饺子；、点火加热，等水沸腾后，放入饺子； 3 3、观察，当饺子浮起来后继续加水；、观察，当饺子浮起来后继续加水； 4 4、重复步骤、重复步骤3 3至少两次。至少两次。 总结：总结： “1 1”其实大部分事情都是按照一定的程序执行，因此

2、要理其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。“清事情的每一步。“2 2”类似于这样按照顺序执行一系列步骤，类似于这样按照顺序执行一系列步骤，最后完成任务的解决问题的思想，就是算法的基本思想。最后完成任务的解决问题的思想，就是算法的基本思想。 事实上，我们完成任何事，都要有一个步骤，事实上，我们完成任何事，都要有一个步骤，合理安排步骤，会达到事半功倍的效果。在合理安排步骤，会达到事半功倍的效果。在我们数学的意义来讲，在解决某些问题时，我们数学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，

3、我们通常把通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法这些步骤称为解决问题的一种算法。这种描。这种描述不是算法的定义，但反映了述不是算法的定义，但反映了算法的基本思算法的基本思想想。 一般而言，我们将解决某类问题的一系列一般而言，我们将解决某类问题的一系列步骤或程序称为步骤或程序称为算法算法。 【例例1】在中央电视台的在中央电视台的幸运幸运52节目中，要求参节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低与者每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次

4、节目中，主持人出示了一台价值了或者正确。在某次节目中，主持人出示了一台价值在在1000元以内的随身听，并开始了竞猜。下面是主元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：持人和参与者的一段对话： . 如果你是参与者，你接下来会怎么猜？ 800元！元！ 高了高了 400元！元！ 600元！元！ 低了低了 高了高了 参与者参与者 主持人：李咏主持人：李咏 方法：（已知价格在方法：（已知价格在1000元以内）元以内） 1.报出报出首次价格首次价格T1； 2.根据回答确定价格区间：根据回答确定价格区间： （1）若）若T1低于低于价格价格P，则价格区间为（，则价格区间为（T1,1000）

5、；）； （2）若）若T1高于高于价格价格P，则价格区间为（，则价格区间为（0，T1）；）； （3）若）若T1等于等于价格价格P，则游戏结束，则游戏结束. 3.若没结束，则报出上面确定的价格若没结束，则报出上面确定的价格区间的中点区间的中点T2. 按照这种方法，继续判断，直到游戏结束按照这种方法，继续判断，直到游戏结束 . 【例例2】在给定素数表的条件下，请你设计一个算在给定素数表的条件下，请你设计一个算法，将法，将936936分成素因数的乘积分成素因数的乘积. . 解：算法步骤如下：解：算法步骤如下： 判断判断936936是否为素数：否。是否为素数：否。 确定确定936936的最小素因数：的最

6、小素因数：2 2。936=2*468936=2*468 判断判断468468是否为素数：否。是否为素数：否。 确定确定468468的最小素因数：的最小素因数：2 2。936=2*2*234936=2*2*234。 判断判断234234是否为素数：否。是否为素数：否。 确定确定234234的最小素因数：的最小素因数：2 2。936=2*2*2*117936=2*2*2*117。 判断判断117117是否为素数：否。是否为素数：否。 确定确定117117的最小素因数：的最小素因数：3 3。936=2*2*2*3*39936=2*2*2*3*39。 判断判断3939是否为素数：否。是否为素数：否。

7、确定确定3939的最小素因数：的最小素因数：3 3。936=2*2*2*3*3*13936=2*2*2*3*3*13。 判断判断13 13 是否为素数：是否为素数：1313是素数，所以分解结束。是素数，所以分解结束。 分解结果是：分解结果是：936=2*2*2*3*3*13936=2*2*2*3*3*13 短除法短除法可以使这个过程更清晰可以使这个过程更清晰. 4 6 8 9 3 6 2 3 4 2 2 2 1 1 7 3 3 3 9 1 3 【例例3】 设计算法，求设计算法，求840840与与17641764的最大公的最大公因数因数. . 解：解：第一步，将第一步，将840分解质因数分解质因

8、数：840=233 5 7; 第二步，将第二步，将1764分解质因数分解质因数：1764=22372; 第三步，确定它们的第三步，确定它们的公共质因数公共质因数：2、3、7; 第四步，确定第四步，确定公共质因数的指数公共质因数的指数：2、1、1; 第五步，第五步，最大公因数最大公因数为：为：2237= 84. 【例例4】“韩信点兵韩信点兵”问题 【例例5】思考以下问题的算法：思考以下问题的算法： 一位商人有一位商人有9 9枚银元，其中有枚银元，其中有1 1枚略轻的是假银元。枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？你能用天平（不用砝码）将假银元找出来吗？ 另外算法：另外算法：

9、解解: 1.: 1.把银元分成把银元分成3 3组，每组组，每组3 3枚。枚。 2 2先将两组分别放在天平的两边。如果天先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的如果天平左右平衡，则假银元就在末称的第第3 3组里。组里。 3 3取出含假银元的那一组，从中任取两枚取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元。，则未称的那一枚就是假银元。

10、说明：说明： 1.算法实际上就是解决某一类问题的步骤和方法，在算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。则与步骤，一步一步地去做，最终便能解决问题。 2.算法的基本思想就是我们分析问题时的想法。由于想算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在法不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。不同的算法，算法有优劣之分。 3.从熟悉的问题出发，体会算法的程序化思想，学会用从熟悉的问题

11、出发，体会算法的程序化思想，学会用自然语言来描述算法自然语言来描述算法 有限性：有限性：一个算法的步骤必须是有限的，必须在有一个算法的步骤必须是有限的，必须在有 限操作之后停止，不能是无限的限操作之后停止，不能是无限的. . 确定性：确定性：算法中的每一步应该是确定的并且能有效算法中的每一步应该是确定的并且能有效 地执行且得到确定的结果，而不应当是模棱两可地执行且得到确定的结果，而不应当是模棱两可. . 逻辑性：逻辑性：从开始的第一步直到最后一步之间必须环从开始的第一步直到最后一步之间必须环 环相扣，分工明确环相扣，分工明确 普遍性：普遍性：一个算法通常设计成能解决一类问题，而一个算法通常设计

12、成能解决一类问题，而不是解决一两个具体问题不是解决一两个具体问题 不唯一性：不唯一性：求解某一个问题的解法不一定是唯一求解某一个问题的解法不一定是唯一 的，对于一个问题可以有不同的算法的，对于一个问题可以有不同的算法. . 两个大人和两个小孩一起渡河，渡口只有一条小两个大人和两个小孩一起渡河，渡口只有一条小船每次只能渡船每次只能渡1 个大人或两个小孩，他们四人都个大人或两个小孩，他们四人都会划会划 船，但都不会游泳试问他们怎样渡过河去？船，但都不会游泳试问他们怎样渡过河去？请写出一个渡河方案。请写出一个渡河方案。 S1 两个小孩同船过河去；两个小孩同船过河去； S2 一个小孩划船回来；一个小孩

13、划船回来； S3 一个大人划船过河去；一个大人划船过河去； S4 对岸的小孩划船回来；对岸的小孩划船回来； S5 两个小孩同船渡过河去；两个小孩同船渡过河去； S6 一个小孩划船回来；一个小孩划船回来； S7 余下的一个大人独自划船渡过河去；余下的一个大人独自划船渡过河去； 对岸的小孩划船回来；对岸的小孩划船回来； S8 两个小孩再同时划船渡过河去。两个小孩再同时划船渡过河去。 练习：练习： 试给出求解一元二次方程试给出求解一元二次方程x2-2x-30的一个算法的一个算法. 第一步第一步 移项，得移项，得x22x3; 第二步第二步 将第一步的结果两边加将第一步的结果两边加1配方，得配方，得(x

14、1)24; 第三步第三步 将第二步的结果两边开方，得将第二步的结果两边开方，得 x12，或，或 x12; 第四步第四步 解得解得 x3，或，或 x1 . 第一步第一步 求求b24ac16; 第二步第二步 将将a1，b2，c3代入求根公式代入求根公式 ， 解得解得x3，或，或 x1 . abx2方方法法1 1 方方法法2 2 对于一元二次方程对于一元二次方程,可以用熟悉的可以用熟悉的求根公式来求解求根公式来求解,但是但是,绝大部分的方绝大部分的方程不存在求根公式程不存在求根公式. 在实际问题中,通常只要获得满足一定精确度的近似解就可以了.因此,讨论方程近似解的算法具有重要的意义! 在函数的应用部

15、分在函数的应用部分,我们学习了用二我们学习了用二分法求方程分法求方程f(x)=0的近似解的近似解.如图所示如图所示 y x O a b x* 二分法的基本思想是二分法的基本思想是:将方程的有解区间分为两个小将方程的有解区间分为两个小区间区间,然后判断解在哪个小区间然后判断解在哪个小区间;继续把有解的区间一分为二进继续把有解的区间一分为二进行判断行判断,如此周而复始如此周而复始,直到求出直到求出满足精度要求的近似解满足精度要求的近似解. 第一步，取函数第一步，取函数f(x)f(x)，给定精确度，给定精确度d. d. 第二步，确定区间第二步，确定区间 a，bb，满足，满足f(f(a) ) f(b)

16、f(b)0. 0. 第五步，判断第五步，判断 a,b,b的长度是否小于的长度是否小于d d或或f(m)f(m)是是否等于否等于0.0.若是，则若是，则m m是方程的近似解；否则，返是方程的近似解；否则，返回第三步回第三步. . 第三步，取区间中点第三步，取区间中点 . . ma+b2 第四步，若第四步，若f(f(a) ) f(m)f(m)0,0,则含零点的区间则含零点的区间 为为 a,m,m,否则，含零点的区间为否则，含零点的区间为mm，b.b. 将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为 a,b;,b; 解:1.因为f(0)=-1,f(1)=1,f(0)f(1)0.1 1.求方

17、程f(x)=x3+x2-1=0在区间 上的实数解,精确度为0.1. 10，3.计算f(0.5)= -0.125; 4.由于f(0.5)f(1)0.1 15.0 ，1.求方程f(x)=x3+x2-1=0在区间 上的实数解,精确度为0.1. 10，10，2.取 的区间中点0.5; 10，例例6 6.计算f(0.75)= - 0.1563; 7.由于f(0.75)f(1)0.1 8.取区间 的中点0.875; 175.0，9.计算f(0.875)=0.43555 10.由于f(0.75)f(0.875)0.1; 875. 075. 0，11.取区间 的中点0.8125 875. 075. 0，5.取

18、 的区间中点0.75; 15.0 ，175.0，5.取 的区间中点0.75; 15.0 ，8.取区间 的中点0.875; 175.0，875. 075. 0，10.由于f(0.75)f(0.875)0.1; 875. 075. 0，11.计算f(0.8125)=0.19653 13.该区间已满足精确度的要求,所以取该区间的中点0.78125,它是方程的一个近似解. 12.因f(0.75)f(0.8125)0, 得区间 0.8125-0.75=0.06250.1 8125. 075. 0，第一步:令f(x)=x3+x2-1,因为f(0)f(1)0,则令x1= m;否则,令x2= m. 简化写法：

19、简化写法： 第二步:令m= ,判断f(m)是否为0,若是,则m为所求;若否,则继续判断f(x1)f(m)大于0还是小于0. 221xx 第四步:判断|x1-x2|0.1是否成立?若是,则x1,x2之间的中间值为满足条件的近似根;若否,则返回第二步 算法,出现在12世纪,指的是运用阿拉伯数字进行算术运算的过程.在数学中,现代意义上的“算法”,通常指的是可以用计算机来解决来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确的有效的,而且能够在有限步之内完成. 练习.书本83 :1 2.设计一个算法设计一个算法,求函数求函数y=log2x,当当x=3时的函数值时的函数值(精确到精确到0.1) (

20、用反函数的思想转化为求用反函数的思想转化为求f(x)=2x-3=0的近似解的近似解.用二分法算法计算用二分法算法计算) 解解:算法算法(二分法二分法): 因为因为f(1)=-1,f(2)=1,f(1)f(2)0,则则x*属于属于(x0,b),a= x0;若若f(a)f(x0)0则则x*属于属于(a,x0), b= x0; 第四步第四步:若若|a-b|0.1,计算终止计算终止,输出输出x*= x0,否则转到第二步否则转到第二步. 1.625 第二步第二步:取区间取区间 的中点的中点 ,将区间一分为二将区间一分为二; ba,第二步第二步:取区间取区间 的中点的中点 ,将区间一分为二将区间一分为二; ba,第二步第二步:取区间取区间 的中点的中点 ,将区间一分为二将区间一分为二; ba,