陕西省蓝田县焦岱中学高中数学必修三21算法的基本思想（1）课件

§1算法的基本思想（1）第二章§1算法的基本思想第二章算法初步引入作为家里的一员，在平时分担一些力所能及的家务是我们应尽的义务，你每天都帮家里做家务吗？你会烧开水吗？请写出你在家中烧开水的过程.1.往壶内注水；2.点火加热；3.观察：如果水开，则停止烧火，否则继续烧火；4.如果水未开，重复过程“3”，直至水开.§1算法的基本思想第二章算法初步引入狼羊菜过河一个猎人带着一只羊，一只狼和一棵白菜回家，路上遇到一条河。河边只有一条船，但船太小，一次最多只可载猎人和另一样东西过河。但猎人不在时，狼要吃羊，羊要吃白菜。请问怎样才能把狼，羊，白菜都安全运过河？§1算法的基本思想第二章算法初步事实上，我们完成任何事，都要有步骤，合理安排步骤，这样会达到事半功倍的效果.从我们数学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法.这种描述不是算法的定义，但反映了算法的基本思想.一、算法的思想§1算法的基本思想第二章算法初步随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会的方方面面.在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等.完成这些工作都需要一系列程序化的步骤，这就是算法的思想.一、算法的思想§1算法的基本思想第二章算法初步一、算法的思想

算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看成按要求设计好的、有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题.现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤.§1算法的基本思想第二章算法初步一、算法的思想说明：1.算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题.2.算法的基本思想就是我们分析问题时的想法.由于想法不同、思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分.3.从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法.§1算法的基本思想第二章算法初步二、算法的特征1、通用性2、程序性3、确定性4、有穷性5、精确性能解决一类问题，重复使用算法的过程要一步一步执行算法的每一步执行的操作必须确切，不能含混不清必须在有限步内完成任务，不能无限制地执行要注意细节和精细化§1算法的基本思想第二章算法初步三、算法案例案例1（看商品猜价格）在电视台的某个娱乐节目中，要求参与者快速猜出物品价格.主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确.在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜.下面是主持人和参与者之间的一段对话：参与者：800元！主持人：高了！参与者：400元！主持人：低了！参与者：600元！主持人：低了!……如果你是参与者，你接下来会怎么猜？§1算法的基本思想第二章算法初步三、算法案例实际上，可以把过程概括如下：按照上述方法，继续判断，直到游戏结束.像这样的一系列步骤通常称为解决这个问题的一个算法.§1算法的基本思想第二章算法初步三、算法案例案例2（素因数分解）

在给定素数表的条件下，设计算法，将936分解成素因数的乘积.(4000以内的素数表见课本附录1)解:算法步骤如下：1.判断936是否为素数：否.2.确定936的最小素因数：2.936=2×468.3.判断468是否为素数：否.4.确定468的最小素因数：2.936=2×2×234.5.判断234是否为素数：否.6.确定234的最小素因数：2.936=2×2×2×117.§1算法的基本思想第二章算法初步三、算法案例案例2（素因数分解）

在给定素数表的条件下，设计算法，将936分解成素因数的乘积.(4000以内的素数表见课本附录1)7.判断117是否为素数：否.8.确定117的最小素因数：3.936=2×2×2×3×39.9.判断39是否为素数：否.10.确定39的最小素因数：3.936=2×2×2×3×3×13.11.判断13是否为素数：13是素数，所以分解结束.分解结果是：936=2×2×2×3×3×13.§1算法的基本思想第二章算法初步三、算法案例案例2（素因数分解）

在给定素数表的条件下，设计算法，将936分解成素因数的乘积.(4000以内的素数表见课本附录1)分析理解:1.查表判断936是否是素数:（1）如果963是素数,则分解结束;（2）如果963不是素数,则进行第2步.2.确定936的最小素因素:2.3.查表判断468是否是素数:（1）如果468是素数,则分解结束;（2）如果468不是素数,则重复上述步骤,确定468的最小素因素.重复进行上述步骤,直到找出936的所有素因素.§1算法的基本思想第二章算法初步三、算法案例案例2（素因数分解）

在给定素数表的条件下，设计算法，将936分解成素因数的乘积.(4000以内的素数表见课本附录1)解算法步骤如下:1.判断936是否是素数:否.2.确定936最小素因素:2.3.判断468是否是素数:否.4.确定468最小素因素:2.5.判断234是否是素数:否.6.确定234最小素因素:2.7.判断117是否是素数:否.8.确定117最小素因素:3.9.判断39是否是素数:否.10.确定39最小素因素:3.11.判断13是否是素数:是,分解结束.分解结果是:短除法９３６２４６８２２３４２１１７３９３１３３§1算法的基本思想第二章算法初步三、算法案例案例3（最大公因数）

设计一个算法，求840与1764的最大公因数.1.先将840进行素因数分解：；2.然后将1764进行素因数分解：

；3.确定它们的公共素因数:2,3,7；4.确定公共素因数的指数：公共素因数2,3,7的指数分别为2,1,1;5.最大公因数为:.解：算法步骤如下：练习1.设计一个算法,求324,440,556的最大公因数.练习2.设计一个算法,