1.1算法案例分析1.课件.ppt

1算法的基本思想（第一课时）,主讲人：刘冬发,CompanyLogo,算法的基本思想,例1在电视台的某个娱乐节目中,要求参与者快速猜出物品价格.主持人出某件物品,参与者每次估算出一个价格,主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参与者之间的一段对话：参与者：800元！主持人：高了！参与者：400元！主持人：低了！参与者：600元！主持人：低了！如果你是参与者，你接下来会怎么猜？,CompanyLogo,分析理解,如果用P表示商品的价格，则参与者的猜测结果为：由主持人的第一次回答，P在0800元之间；由主持人的第二次回答，P在400800元之间；由主持人的第三次回答，P在600800之间。根据参与者的猜测，我们知道，参与者首先需要确定的是商品价格的范围，数学上一般可以用区间来表示，然后再根据主持人的回答，报出区间中点，将价格区间缩小一半。因此，下一步参与者要猜的数应是700元，然后根据主持人的回答继续猜，直至猜出正确价格。,CompanyLogo,抽象概括,实际上，可以把上述过程概括如下：1.报出首次价格T1；2.根据主持人的回答确定价格区间：（1）若报价小于商品价格，则商品的价格区间为（T1，1000）；（2）若报价大于商品价格，则商品的价格区间为（0，T1）；（3）若报价等于商品价格，则游戏结束.3.如果游没有结束，则报出上面确定的价格区间的中点T2.按照上述方法，继续判断，直到游戏结束.像这样的一系列步骤通常称为这个问题的一个算法。,CompanyLogo,分析理解,1.查表判断936是否是素数：（1）如果936是素数，则分解结束；（2）如果不是素数，则进行第2步。2.确定936的最小素因数:2.936=24683.查表判断468是否则是素数:(1)如果468是素数,则分解结束;(2)如果468不是素数,则重复上述步骤,确定468的最小素因数.重复进行上述步骤,直到找出9366的所有素因数.,例2在给定素数表的条件下，设计算法，将936分解成素因数的乘积（4000以内的素数见附录1）,CompanyLogo,解算法步骤如下:1.判断936是否为素数:否.2.确定936的最小素因数:2936=2468.3.判断468是否为素数:否.4.确定468是否为素数:2.936=22234。5.判断234是否为素数：否。6.确定234是否为素数：2.936=2221177.判断117是否为素数：否。8.确定117是否为最小素因数：3.936=222339.9.判断39是否为素数：否。10确定39的最小素因数：3.936=222331311.判断13是否为素数：13是素数。所以分解结束。分解结果是：936=2223313,分析理解,短除法,CompanyLogo,分析理解,按照以上程序，完成了对936的素因数分解。实际上，在给定素数表的基础上，对任意自然数n，都可以按照上述办法进行分解。以上步骤是解决素因数分解问题的一个过程，只要依照这一系列步骤，都能解决这个问题。我们把这一系列步骤成为解决这个问题的一个算法。,CompanyLogo,我们已经学习了对自然数进行素因数分解的方法，下面的算法就是在此基础上设计的。解答这个问题需要按以下思路进行。首先，对两个数分别进行素因数分解：840=23357，1764=223272其次，确定两数的公共素因数：2，3，7。接着，确定公共素因数的指数：对于公共素因数2，22是1764的因数，23是840的因数，因此22是这两个数的公因数，这样就确定了公共素因数2的指数为2。同样，可以确定出公因数3和7的指数均为1。这样，就确定了840与1746的最大公因数为：223171=84,例3设计一个算法，求840与764的最大公因数,CompanyLogo,解算法步骤如下：1.先将840进行素因数分解：840=23357；2.然后将1764进行素因数分解：1746=223272；3.确定它们的公共素因数：2，3，7；4.确定公共素因数的指数：公共素因数2，3，7的指数分别为2，1，1；5.最大公因数为：223171=84。,CompanyLogo,分析理解,以上步骤就是求两个正整数的最大公因数的一个算法。这个算法的思想具有一般性，它可以帮助设计求三个或者三个以上正整数的最大公因数的算法。在这个算法的设计中，我们首先分别对840和1764进行素因数分解，那么，如何将840或1764的所有素因数都找出来呢？例2给出了具体的算法。我们通常会把“对自然数进行素因数分解”的算法，做成一个“程序包”，又称为一个“平台”，在需要“对自然数进行素因数分解”时，把做好的“程序包”拿来使用即可。同样的，我们也可以把“求两个自然数的最大公因数”做成一个“程序包”或“平台”，在解决其他问题时，如果需要“求两个自然数的最大公因数”，我们就可以把做好的程序包直接拿来使用，通常把这种思想称为“平台思想”，“平台”的思想在算法设计中是一个最基本的思想，也是数学中思考问题的一个重要思想。通过以上的例子可以看出，算法是解决某类问题的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决。一般来说，“用算法解决问题”都是可以利用计算机帮助完成的。,CompanyLogo,课堂练习,1.模仿例3，设计一个算法，求324，440，556的最大公因数.2.设计算法，求1356和2400的最小公倍数.,1.解（1）分别将324，440，556进行素因数分解：324=2234，440=23511，556=22139.（2）确定三个数的公共素因数：2（3）确定公共素因数的指数：2（4）最大公因数为：22=4.,2.解（1）首先将1365和2400进行素因数分解：1365=22