算法的基本思想75741.ppt

《算法的基本思想75741.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法的基本思想焦作师专附中孙红霞2014.05！本章在高考中的地位课题引入作为家里的一员，在平时分担一些力所能及的事是我们应尽的义务，你每天都帮家里做事吗？你会煮饺子吗？请写出你在家中煮饺子的过程1、往锅里注水；2、点火加热，等水沸腾后，放入饺子；3、观察，当饺子浮起来后继续加水；4、重复步骤3至少两次。总结：“1”其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。“2”类似于这样按照顺序执行一系列步骤，最后完成任务的解决问题的思想，就是算法的基本思想。事实上，我们完成任何事，都要有一个步骤，合理安排步骤，会达到事半功倍的效果。在我们数学上的意义来讲：在解决

2、某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法。这种描述不是算法的定义，但反映了算法的基本思想。引：在中央电视台的《幸运52》节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：………………….如果你是参与者，你接下来会怎么猜？800元！高了400元！600元！低了高了参与者主持人：李咏2班提问确定1班提问确定3班提问确定【例1】

3、一个同学想一个0到30之间的一个数，另一个同学负责猜，第一个同学只需要给出“高了”，“低了”，“正确”的提示。2班提问确定1班提问确定3班提问确定我们写的这个过程能不能称为是一个算法呢？算法是要解决一类问题而不是一个问题，所以我们这样写出来的不能称为一个算法。把它一般化就成为一个算法。而且从第一步到最后一步做到环环相扣，分工明确。算法特征：普遍性、逻辑性方法：已知数字在一个范围内（0～30）1.报出首次T1；2.根据回答确定下一个区间：（1）若T1低于数字P，则下一个区间为（T1，30）；（2）若T1高于数字P，则价格区间为（0，T1）；（3）若T1等于数字P，则游戏结

4、束.3.若没结束，则报出上面确定的新区间的中点T2.按照这种方法，继续判断，直到游戏结束.例二思考以下问题的算法：一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？解:1.把银元分成3组，每组3枚。2．先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里。3．取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。2班提问确定1班提问确定3班提问确定算法特征：不唯一性在解决这个问题时我们共有几个

5、方法，是不是每种方法都能把假银元找出来呢两个大人和两个小孩一起渡河，渡口只有一条小船每次只能渡1个大人或两个小孩，他们四人都会划船，但都不会游泳试问他们怎样渡过河去？请写出一个渡河方案。智力大比拼S1两个小孩同船过河去；S2一个小孩划船回来；S3一个大人划船过去S4对岸的小孩划船回来；S5两个小孩同船过河去；S6一个小孩划船回来；S7余下的一个大人独自划船渡过河去；S8对岸的小孩划船回来；S9两个小孩再同时划船渡过河去。算法特征：有限性、确定性在解决这个问题时我们的步骤有点多，但是我们最终也把事情做完了。说明：1算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成

6、的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。2算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。3从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法算法的特征普遍性：必须能解决一类问题，并且能重复使用逻辑性：算法具有正确性和顺序性，并且每一步都具有确切的含义，从而组成一个很强逻辑性的序列有限性:一个算法在执行有限的步骤后，结束且有正确的输出不唯一性:求解某一问题的算法不唯一3班提问确定1班提问确定2班提问确定确定性：算法的每一步计算都必须有确定的结果，不

7、能模棱两可应用练习下列关于算法的说法，正确的有（）①求解某一类问题的算法是唯一的；②算法必须在有限步骤操作之后停止；③算法的每一步操作必须是明确的，不能有歧义或模糊；④算法执行后一定产生确定的结果；②③④例1：在给定素数表的条件下，请你设计一个算法，将936分成素因数的乘积.回归3班提问确定2班提问确定1班提问确定468936234222117333913短除法可以使这个过程更清晰.解：判断936是否为素数：否。确定936的最小素因数：2。936=2468判断468是否为素数：否。确定468的最小素因数：2。936=22234判断234是