算法的基本思想.pptx

焦作师专附中 孙红霞2014.05！本章在高考中的地位！本章在高考中的地位作为家里的一员，在平时分担一些力所能及的事是作为家里的一员，在平时分担一些力所能及的事是我们应尽的义务，你每天都帮家里做事吗？你会煮我们应尽的义务，你每天都帮家里做事吗？你会煮饺子吗？请写出你在家中饺子吗？请写出你在家中煮饺子煮饺子的过程的过程1 1、往锅里注水；、往锅里注水；2 2、点火加热，等水沸腾后，放入饺子；、点火加热，等水沸腾后，放入饺子；3 3、观察，当饺子浮起来后继续加水；、观察，当饺子浮起来后继续加水；4 4、重复步骤、重复步骤3 3至少两次。至少两次。总结：总结：“1”1”其实大部分事情都是其实大部分事情都是按照一定的程序执行按照一定的程序执行，因此要理清事情的每一步。，因此要理清事情的每一步。“2”2”类似于这样类似于这样按照顺序执行一系列步骤按照顺序执行一系列步骤，最后完成任务的解决问题的思想，最后完成任务的解决问题的思想，就是算法的基本思想。就是算法的基本思想。事实上，我们完成任何事，都要有一个事实上，我们完成任何事，都要有一个步骤，合理安排步骤，会达到事半功倍步骤，合理安排步骤，会达到事半功倍的效果。在我们数学上的意义来讲：在的效果。在我们数学上的意义来讲：在解决某些问题时，需要设计出解决某些问题时，需要设计出一系列可一系列可操作或可计算的步骤操作或可计算的步骤，通过实施这些步，通过实施这些步骤来解决问题，我们通常把这些步骤称骤来解决问题，我们通常把这些步骤称为解决问题的一种算法。这种描述不是为解决问题的一种算法。这种描述不是算法的定义，但反映了算法的定义，但反映了算法的基本思想。算法的基本思想。引：在中央电视台的引：在中央电视台的幸运幸运52节目中，要求参与者节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在者正确。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：和参与者的一段对话：.如果你是参与者，你接下来会怎么猜？800元！元！高了高了400元！元！600元！元！低了低了高了高了参与者参与者主持人：李咏主持人：李咏2班提问 确定1班提问 确定3班提问 确定【例例1】一个同学想一个一个同学想一个0到到30之间的一个数，另一个之间的一个数，另一个同学负责猜，第一个同学只需要给出同学负责猜，第一个同学只需要给出“高了高了”，“低低了了”，“正确正确”的提示。的提示。2班提问 确定1班提问 确定3班提问 确定我们写的这个过程能我们写的这个过程能不能称为是一个算法不能称为是一个算法呢？呢？算法是要解决一类问题而不是一个问题，所算法是要解决一类问题而不是一个问题，所以我们这样写出来的不能称为一个算法。把以我们这样写出来的不能称为一个算法。把它一般化就成为一个算法。而且从第一步到它一般化就成为一个算法。而且从第一步到最后一步做到环环相扣，分工明确。最后一步做到环环相扣，分工明确。算法特征：普遍性、逻辑性方法：已知数字在一个范围内（方法：已知数字在一个范围内（030）1.报出报出首次首次T1；2.根据回答确定下一个区间：根据回答确定下一个区间：（1）若）若T1低于低于数字数字P，则下一个区间为，则下一个区间为（T1，30）；）；（2）若）若T1高于高于数字数字P，则价格区间为（，则价格区间为（0，T1）；）；（3）若）若T1等于等于数字数字P，则游戏结束，则游戏结束.3.若没结束，则报出上面确定的新若没结束，则报出上面确定的新区间的中区间的中点点T2.按照这种方法，继续判断，直到游戏结束按照这种方法，继续判断，直到游戏结束.例二例二 思考以下问题的算法：思考以下问题的算法：一位商人有一位商人有9 9枚银元，其中有枚银元，其中有1 1枚略轻的是假银元。你枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？能用天平（不用砝码）将假银元找出来吗？解解:1.:1.把银元分成把银元分成3 3组，每组组，每组3 3枚。枚。2 2先将两组分别放在天平的两边。如果天先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的如果天平左右平衡，则假银元就在末称的第第3 3组里。组里。3 3取出含假银元的那一组，从中任取两枚取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。则末称的那一枚就是假银元。2班提问 确定1班提问 确定3班提问 确定算法特征：不唯一性算法特征：不唯一性在解决这个问题时我在解决这个问题时我们共有几个方法，是们共有几个方法，是不是每种方法都能把不是每种方法都能把假银元找出来呢假银元找出来呢两个大人和两个小孩一起渡河，渡口只有一条小两个大人和两个小孩一起渡河，渡口只有一条小船每次只能渡船每次只能渡1 个大人或两个小孩，他们四人都个大人或两个小孩，他们四人都会划会划 船，但都不会游泳试问他们怎样渡过河去？船，但都不会游泳试问他们怎样渡过河去？请写出一个渡河方案。请写出一个渡河方案。S1 两个小孩同船过河去；两个小孩同船过河去；S2 一个小孩划船回来；一个小孩划船回来；S3 一个大人划船过去一个大人划船过去S4 对岸的小孩划船回来；对岸的小孩划船回来；S5 两个小孩同船过河去；两个小孩同船过河去；S6 一个小孩划船回来；一个小孩划船回来；S7 余下的一个大人独自划船渡过河去；余下的一个大人独自划船渡过河去；S8对岸的小孩划船回来；对岸的小孩划船回来；S9 两个小孩再同时划船渡过河去。两个小孩再同时划船渡过河去。算法特征：有限性、确定性算法特征：有限性、确定性在解决这个问题时我在解决这个问题时我们的步骤有点多，但们的步骤有点多，但是我们最终也把事情是我们最终也把事情做完了。做完了。说明：说明：1算法实际上就是算法实际上就是解决某一类问题的步骤和方法解决某一类问题的步骤和方法，在解，在解决问题时形成的决问题时形成的规律性规律性的东西，按照算法描述的规则的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。与步骤，一步一步地去做，最终便能解决问题。2算法的基本思想就是我们算法的基本思想就是我们分析问题时的想法分析问题时的想法。由于想法。由于想法不同思考的角度不同，着手点不一样，不同思考的角度不同，着手点不一样，同一问题存在不同一问题存在不同的算法同的算法，算法有优劣之分。，算法有优劣之分。3从熟悉的问题出发，体会算法的从熟悉的问题出发，体会算法的程序化思想程序化思想，学会用，学会用自然语言自然语言来描述算法来描述算法算法的特征算法的特征 普遍性：普遍性：必须能解决一类问题，并且能重复使用必须能解决一类问题，并且能重复使用逻辑性：逻辑性：算法具有正确性和顺序性，并且每一步都具算法具有正确性和顺序性，并且每一步都具 有确切的含义，从而组成一个很强逻辑性的序列有确切的含义，从而组成一个很强逻辑性的序列有限性有限性:一个算法在执行有限的步骤后，结束且有正一个算法在执行有限的步骤后，结束且有正确的输出确的输出不唯一性不唯一性:求解某一问题的算法不唯一求解某一问题的算法不唯一3班提问 确定1班提问 确定2班提问 确定确定性：确定性：算法的每一步计算都必须有确定的结果，算法的每一步计算都必须有确定的结果，不能模棱两可不能模棱两可应用练习应用练习下列关于算法的说法，正确的有（下列关于算法的说法，正确的有（）求解某一类问题的算法是唯一的；求解某一类问题的算法是唯一的；算法必须在有限步骤操作之后停止；算法必须在有限步骤操作之后停止；算法的每一步操作必须是明确的，不能有歧义算法的每一步操作必须是明确的，不能有歧义 或模糊；或模糊；算法执行后一定产生确定的结果；算法执行后一定产生确定的结果；例例1 1：在给定素数表的条件下，请你设计一个算法，：在给定素数表的条件下，请你设计一个算法，将将936936分成素因数的乘积分成素因数的乘积.3班提问 确定2班提问 确定1班提问 确定 4 6 89 3 6 2 3 4 2221 1 7 333 91 3短除法短除法可以使这个过程更清晰可以使这个过程更清晰.解：判断解：判断936936是否为素数：否。是否为素数：否。确定确定936936的的最小最小素因数：素因数：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是否为素数：否。是否为素数：否。确定确定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算法步骤如下：算法步骤如下：例二：例二：设计算法，求设计算法，求840840与与17641764的最大的最大公因数公因数.解：解：第一步，将第一步，将840分解质因数分解质因数：840=233 5 7;第二步，将第二步，将1764分解质因数分解质因数：1764=22372;第三步，确定它们的第三步，确定它们的公共质因数公共质因数：2、3、7;第四步，确定第四步，确定公共质因数的指数公共质因数的指数：2、1、1;第五步，第五步，最大公因数最大公因数为：为：2237=84.例三：例三：设计算法，求方程设计算法，求方程x x2 2-2x-3-2x-30 0的的解？解？解析解析 求一元二次方程的根的问题，解法较多，可求一元二次方程的根的问题，解法较多，可有配方法、判别式法。本题用判别式法写出算法。有配方法、判别式法。本题用判别式法写出算法。算法：算法：1.计算方程的根的判别式计算方程的根的判别式 b2-4ac与与0的关系的关系2.若若0，将将a,b,c的值代入求根公式的值代入求根公式x=-b b2-4ac 2a得解。得解。3.若若0，则方程无解。，则方程无解。例四：例四：设函数设函数f(x)f(x)的图象是一条连续不断的的图象是一条连续不断的曲线，写出用曲线，写出用“二分法二分法”求方程求方程 f(x)=0f(x)=0的一的一个近似解的算法个近似解的算法.第一步，取函数第一步，取函数f(x)f(x)，给定精确度，给定精确度d.d.第二步，确定区间第二步，确定区间 a，bb，满足，满足f(f(a)f(b)f(b)0.0.第五步，判断第五步，判断 a,b,b的区间长度是否小于的区间长度是否小于d d或或f(m)f(m)是是否等于否等于0.0.若是，则若是，则m m是方程的近似解；否则，返是方程的近似解；否则，返回第三步回第三步.第三步，取区间中点第三步，取区间中点.第四步，若第四步，若f(f(a)f(m)f(m)0,0,则含零点的区间则含零点的区间 为为 a,m,m,否则，含零点的区间为否则，含零点的区间为mm，b.b.将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为 a,b;,b;课堂小结课堂小结1.算法思想：解决问题的步骤清晰化、顺序化。算法思想：解决问题的步骤清晰化、顺序化。2.算法特征：算法特征：逻辑性、确定性、有限性、不唯一性、普遍性。逻辑性、确定性、有限性、不唯一性、普遍性。3.算法在高中阶段的意义：回归数学，解决类型题。算法在高中阶段的意义：回归数学，解决类型题。作业：P78 练习1 第一题