《1.算法案的基本思想演示文稿》由会员分享，可在线阅读，更多相关《1.算法案的基本思想演示文稿（32页珍藏版）》请在金锄头文库上搜索。
1、2.1.12.1.1算法案例分析（算法案例分析（1 1）2021/6/161算法的基本思想算法的基本思想例例1 在电视台的某个娱乐节目中在电视台的某个娱乐节目中,要求参与者快速猜要求参与者快速猜出物品价格出物品价格.主持人出某件物品主持人出某件物品,参与者每次估算参与者每次估算出一个价格出一个价格,主持人只能回答高了、低了或者正主持人只能回答高了、低了或者正确确.在某次节目中，主持人出示了一台价值在在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜元以内的随身听，并开始了竞猜.下面是主下面是主持人和参与者之间的一段对话：持人和参与者之间的一段对话： 参与者：参与者：800
2、元！元！ 主持人：高了！主持人：高了！ 参与者：参与者：400元！元！ 主持人：低了！主持人：低了！ 参与者：参与者：600元！元！ 主持人：低了！主持人：低了！ 如果你是参与者，你接下来会怎么猜？如果你是参与者，你接下来会怎么猜？2021/6/162分析理解分析理解如果用如果用P表示商品的价格，则参与者的猜表示商品的价格，则参与者的猜测结果为：测结果为：由主持人的第一次回答，由主持人的第一次回答，P在在0800元之元之间；间；由主持人的第二次回答，由主持人的第二次回答，P在在400800元元之间；之间；由主持人的第三次回答，由主持人的第三次回答，P在在600800之之间间.2021/6/16
3、3根据参与者的猜测，我们知道，参与者根据参与者的猜测，我们知道，参与者首先需要确定的是商品价格的范围，数学首先需要确定的是商品价格的范围，数学上一般可以用区间来表示，然后再根据主上一般可以用区间来表示，然后再根据主持人的回答，报出区间中点，将价格区间持人的回答，报出区间中点，将价格区间缩小一半缩小一半. .因此，下一步参与者要猜的数应是因此，下一步参与者要猜的数应是700700元，然后根据主持人的回答继续猜，直至元，然后根据主持人的回答继续猜，直至猜出正确价格猜出正确价格. .分析理解分析理解2021/6/164抽象概括抽象概括实际上，可以把上述过程概括如下：实际上，可以把上述过程概括如下：1
4、.报出首次价格报出首次价格T1；2.根据主持人的回答确定价格区间：根据主持人的回答确定价格区间： （1）若报价小于商品价格，则商品的价格区间为（）若报价小于商品价格，则商品的价格区间为（T1，1000）；）； （2）若报价大于商品价格，则商品的价格区间为（）若报价大于商品价格，则商品的价格区间为（0，T1）；）； （3）若报价等于商品价格，则游戏结束）若报价等于商品价格，则游戏结束.3.如果游没有结束，则报出上面确定的价格区间的中点如果游没有结束，则报出上面确定的价格区间的中点T2.按照上述方法，继续判断，直到游戏结束按照上述方法，继续判断，直到游戏结束. 像这样的一系列步骤通常称为这个问题的
5、一个算法像这样的一系列步骤通常称为这个问题的一个算法.2021/6/165分析理解分析理解1.查表判断查表判断936是否是素数：是否是素数： （1）如果如果936是素数，则分解结束；是素数，则分解结束； （2）如果不是素数，则进行第如果不是素数，则进行第2步步. 2.确定确定936的最小素因数的最小素因数:2. 936=2468 3.查表判断查表判断468是否则是素数是否则是素数: (1)如果如果468是素数是素数,则分解结束则分解结束; (2)如果如果468不是素数不是素数,则重复上述步骤则重复上述步骤,确定确定468的的 最小素因数最小素因数.重复进行上述步骤重复进行上述步骤,直到找出直到
6、找出936的所有素因数的所有素因数.例例2 2 在给定素数表的条件下，设计算法，将在给定素数表的条件下，设计算法，将936936分解分解成素因数的乘积（成素因数的乘积（40004000以内的素数见附录以内的素数见附录1 1）2021/6/166解解 算法步骤如下算法步骤如下:1.判断判断936是否为素数是否为素数:否否.2.确定确定936的最小素因数的最小素因数:2. 936=2468.3.判断判断468是否为素数是否为素数:否否.4.确定确定468最小素因数最小素因数: 2. 936=22234.5.判断判断234是否为素数：否是否为素数：否.6.确定确定234最小素因数：最小素因数：2.
7、936=2221177.判断判断117是否为素数：否是否为素数：否.分析理解分析理解2021/6/1678.确定确定117最小素因数：最小素因数： 3. 936=222339.9.判断判断39是否为素数：否是否为素数：否.10.确定确定39的最小素因数：的最小素因数：3. 936=222331311.判断判断13是否为素数：是否为素数：13是素数是素数.所以分解结束所以分解结束. 分解结果是：分解结果是：936=2223313分析理解分析理解2021/6/168分析理解分析理解 按照以上程序，完成了对按照以上程序，完成了对936的素因的素因数分解数分解.实际上，在给定素数表的基础实际上，在给定
8、素数表的基础上，对任意自然数上，对任意自然数n，都可以按照上述，都可以按照上述办法进行分解办法进行分解. 以上步骤是解决素因数分解问题的以上步骤是解决素因数分解问题的一个过程，只要依照这一系列步骤，一个过程，只要依照这一系列步骤，都能解决这个问题都能解决这个问题.我们把这一系列步我们把这一系列步骤成为解决这个问题的一个算法骤成为解决这个问题的一个算法.2021/6/169 我们已经学习了对自然数进行素因数分解的方法，下我们已经学习了对自然数进行素因数分解的方法，下面的算法就是在此基础上设计的面的算法就是在此基础上设计的.解答这个问题需要按解答这个问题需要按以下思路进行以下思路进行.首先，对两个
9、数分别进行素因数分解：首先，对两个数分别进行素因数分解： 840=23357， 1764=223272 其次，确定两数的公共素因数：其次，确定两数的公共素因数：2，3，7.接着，确定接着，确定公共素因数的指数：对于公共素因数公共素因数的指数：对于公共素因数2，22是是1764的的因数，因数，23是是840的因数，因此的因数，因此22是这两个数的公因数，是这两个数的公因数，这样就确定了公共素因数这样就确定了公共素因数2的指数为的指数为2. 同样，可以确定出公因数同样，可以确定出公因数3和和7的指数均为的指数均为1. 这样，就确定了这样，就确定了840与与1746的最大公因数为：的最大公因数为：
10、223171=84.例例3 设计一个算法，求设计一个算法，求840与与1764的最大公因数的最大公因数.例题讲解例题讲解2021/6/1610解解 算法步骤如下：算法步骤如下：1.先将先将840进行素因数分解：进行素因数分解：840=23357；2.然后将然后将1764进行素因数分解：进行素因数分解：1746=223272；3.确定它们的公共素因数：确定它们的公共素因数：2，3，7；4.确定公共素因数的指数：公共素因数确定公共素因数的指数：公共素因数2，3，7的指数分别为的指数分别为2，1，1；5.最大公因数为：最大公因数为：223171=84.例题讲解例题讲解2021/6/1611分析理解分
11、析理解 以上步骤就是求两个正整数的最大公因数的一个算以上步骤就是求两个正整数的最大公因数的一个算法法.这个算法的思想具有一般性，它可以帮助设计求这个算法的思想具有一般性，它可以帮助设计求三个或者三个以上正整数的最大公因数的算法三个或者三个以上正整数的最大公因数的算法.在这在这个算法的设计中，我们首先分别对个算法的设计中，我们首先分别对840和和1764进行素进行素因数分解，那么，如何将因数分解，那么，如何将840或或1764的所有素因数都的所有素因数都找出来呢？例找出来呢？例2给出了具体的算法给出了具体的算法.我们通常会把我们通常会把“对对自然数进行素因数分解自然数进行素因数分解”的算法，做成
12、一个的算法，做成一个“程序包程序包”，又称为一个，又称为一个“平台平台”，在需要，在需要“对自然数进行素对自然数进行素因数分解因数分解”时，把做好的时，把做好的“程序包程序包”拿来使用即可拿来使用即可.同样的，我们也可以把同样的，我们也可以把“求两个自然数的最大公因数求两个自然数的最大公因数”2021/6/1612做成一个做成一个“程序包程序包”或或“平台平台”，在解决其他问，在解决其他问题时，如果需要题时，如果需要“求两个自然数的最大公因数求两个自然数的最大公因数”，我们就可以把做好的程序包直接拿来使用，通，我们就可以把做好的程序包直接拿来使用，通常把这种思想称为常把这种思想称为“平台思想平
13、台思想”，“平台平台”的思的思想在算法设计中是一个最基本的思想，也是数学想在算法设计中是一个最基本的思想，也是数学中思考问题的一个重要思想中思考问题的一个重要思想. . 通过以上的例子可以看出，算法是解决某类通过以上的例子可以看出，算法是解决某类问题的一系列步骤或程序，只要按照这些步骤执问题的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决行，都能使问题得到解决. .一般来说，一般来说，“用算法用算法解决问题解决问题”都是可以利用计算机帮助完成的都是可以利用计算机帮助完成的. .分析理解分析理解2021/6/1613课堂练习课堂练习1.模仿例模仿例3，设计一个算法，求，设计一个算法，
14、求 324，440，556的最大公因数的最大公因数.1.解（解（1）分别将）分别将324，440，556进行素因数分进行素因数分解：解： 324=2234，440=23511，556=22139. （2）确定三个数的公共素因数：）确定三个数的公共素因数：2 （3）确定公共素因数的指数：）确定公共素因数的指数：2 （4）最大公因数为：）最大公因数为：22=4.2021/6/16142.解（解（1）首先将）首先将1356和和2400进行素因数进行素因数分解：分解： 1356=223113，2400=25352. （2）确定最小公倍数的素因数：）确定最小公倍数的素因数：2，3， 5，113. （3）
15、确定素因数的指数分别为：）确定素因数的指数分别为：5，1，2，1. （4）最小公倍数为：）最小公倍数为：25352113=271200.课堂练习课堂练习2.设计算法，求设计算法，求 1356和和2400的最小公倍数的最小公倍数.2021/6/16152.1.1算法案例分析(2)2021/6/1616例题解析例题解析 例例1 “韩信点兵韩信点兵”问题问题 韩信是汉高祖刘邦手上的大将，他英勇善韩信是汉高祖刘邦手上的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳战，智谋超群，为建立汉朝立下了汗马功劳.据说他在点兵的时候，为了保住军事机密，据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部
16、队的实力，采用下述点不让敌人知道自己部队的实力，采用下述点兵方式：兵方式： 先令士兵从先令士兵从13报数，结果最后一个士兵报数，结果最后一个士兵报报2；再令士兵从；再令士兵从15报数，结果最后一个士报数，结果最后一个士兵报兵报3；又令士兵从；又令士兵从17报数，结果最后一个报数，结果最后一个士兵报士兵报4.2021/6/1617分析理解分析理解 士兵从士兵从13报数，最后一个士兵报报数，最后一个士兵报2.这句话说明士这句话说明士兵的总人数除以兵的总人数除以3余余2.算法的第一步是将所有除以算法的第一步是将所有除以3余余2的正整数找出来，按照从小到大的顺序排成一列数的正整数找出来，按照从小到大的
17、顺序排成一列数.士兵从士兵从15报数，最后一个士兵报报数，最后一个士兵报3.这句话说明士兵这句话说明士兵的总人数除以的总人数除以5余余3.算法的第二步是从上列数中找出算法的第二步是从上列数中找出除以除以5余余3的一列数的一列数. 最后，在满足前两个条件的上列数中再找出除以最后，在满足前两个条件的上列数中再找出除以7余余4的一列数，这列数中最小的数，即为我们所求的的一列数，这列数中最小的数，即为我们所求的数可数可.这样，韩信很快计算出了自己部队士兵的总人数这样，韩信很快计算出了自己部队士兵的总人数.请设计一个算法，求出士兵至少有多少人请设计一个算法，求出士兵至少有多少人.2021/6/1618解
18、解 算法步骤如下：算法步骤如下：1.首先确定最小的满足除以首先确定最小的满足除以3余余2的正整数：的正整数：2；2.依次加依次加3就得到所有除以就得到所有除以3余余2的正整数：的正整数： 2，5，8，11，14，17，20，23，26，29，32，35，38，41，44，47，50，53，56，3.在上列数中确定最小的满足除以在上列数中确定最小的满足除以5余余3的的正整数：正整数：8；分析理解分析理解2021/6/16194.然后依次加上然后依次加上15，得到，得到8，23，38，53，不难看出，这些数既满足除以不难看出，这些数既满足除以3余余2，又满足除以又满足除以5余余3；5.在第在第4步
19、得到得以列数中找出满足除以步得到得以列数中找出满足除以7余余4的最小数的最小数53，这就是我们要求的数，这就是我们要求的数. 在完成上述步骤后就找到了所求的数在完成上述步骤后就找到了所求的数53，这，这5个步骤称为解决个步骤称为解决“韩信点兵韩信点兵”问题问题的一个算法的一个算法.2021/6/1620想一想想一想 大家可以想一想，能否在这个算法的基大家可以想一想，能否在这个算法的基础会上作一些改进，以更快地获得结果？础会上作一些改进，以更快地获得结果？ 实际上，我们颠倒一下实际上，我们颠倒一下3，5，7的顺序，就的顺序，就可以得到另一个算法；可以得到另一个算法； 1.首先确定最小的除以首先确
20、定最小的除以7余余4的正整数：的正整数：4； 2.依次加依次加7就得到所有除以就得到所有除以7余余4的正整数；的正整数； 4，11，18，25，32，39，46，53，60，2021/6/16213.在第在第2步得到的一列数中确定最小步得到的一列数中确定最小的除以的除以5余余3的正整数：的正整数：18；4.然后依次加上然后依次加上35，得到，得到 18，53，88，5.在第在第4步得到的一列数中找出最小步得到的一列数中找出最小的满足除以的满足除以3余余2的正整数：的正整数：53.2021/6/1622例题解析例题解析例例2 一位商人有一位商人有9枚银元，其中有一枚略轻枚银元，其中有一枚略轻的是
21、假银元的是假银元.你能用天平（不用砝码）将假你能用天平（不用砝码）将假银元找出来吗？银元找出来吗？ 最容易想到的解决这个问题的一种方法最容易想到的解决这个问题的一种方法是：把是：把9枚银元按顺序排成一列，先称前枚银元按顺序排成一列，先称前2枚，若不平衡，则可找出假银元；若平衡，枚，若不平衡，则可找出假银元；若平衡，则则2枚银元都是真的，再依次与剩下的银元枚银元都是真的，再依次与剩下的银元比较，就能找出假银元比较，就能找出假银元.2021/6/1623分析理解分析理解 解解 按照下列步骤，就能将假银元找出来：按照下列步骤，就能将假银元找出来： 1.1.任取任取2 2枚银元分别放在天平的两边枚银元
22、分别放在天平的两边. .如果天平左如果天平左右不平衡，则轻的一边就是假银元；如果天平平右不平衡，则轻的一边就是假银元；如果天平平衡，则进行第二步衡，则进行第二步. . 2. 2.取下右边的银元，放在一边，然后把剩余的取下右边的银元，放在一边，然后把剩余的7 7枚银元依次放在右边进行称量，直到天平不平衡，枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元偏轻的那一枚就是假银元. . 这种算法最少要称这种算法最少要称1 1次，最多要称次，最多要称7 7次，是次，是不是还有更好的办法，使得称量次数少一不是还有更好的办法，使得称量次数少一些？些？我们可以采用下面的方法：我们可以采用下面
23、的方法：2021/6/16241.把银元分成把银元分成3组，每组组，每组3枚枚.2.先将两组分别放在天平的两边先将两组分别放在天平的两边.如果天平不平衡，那如果天平不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的第银元就在未称的第3组里组里.3.取出含假银元的那一组，从中任取两枚银元放在天取出含假银元的那一组，从中任取两枚银元放在天平的两边平的两边.如果左右不平衡，则轻的那一边就是假银元；如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元如果天平两边平衡，则未称的那一枚就是假银元.分析理解分析理
24、解2021/6/1625分析理解分析理解 进分析发现，这种算法只需称量两次，进分析发现，这种算法只需称量两次，这种做法要明显好于前一种做法这种做法要明显好于前一种做法.当然，当然，这两种方法都具有一般性，同样适用于这两种方法都具有一般性，同样适用于n枚银元的情形枚银元的情形.这是信息论中的一个模这是信息论中的一个模型，可以帮助我们找出某些特殊信息型，可以帮助我们找出某些特殊信息. 从以上两个问题中可以看出，同一个问从以上两个问题中可以看出，同一个问题可能存在着多种算法，其中一些可能题可能存在着多种算法，其中一些可能要比另一些好要比另一些好.在实际问题和算法理论中，在实际问题和算法理论中，找出好
25、的算法是一项重要的工作找出好的算法是一项重要的工作.2021/6/1626方程近似解算法方程近似解算法其算法步骤如下：其算法步骤如下：1.确定有解区间确定有解区间a,b（f(a)f(b)0）.2.取取a,b的中点的中点x=（a+b）/2.3.计算函数计算函数f(x)在中点处的函数值在中点处的函数值f(（a+b）/2).4.判断函数值判断函数值f(（a+b）/2)是否为是否为0；（1）如果为）如果为0，x=（a+b）/2就是方程的解，问题就是方程的解，问题就得到可解决；就得到可解决；（2）如果函数值）如果函数值f(（a+b）/2)不为不为0，则分析下列，则分析下列两种情形：两种情形：若若f(a)
26、f(（a+b）/2)0,则确定新的有解区间为则确定新的有解区间为（a+b）/2,b).5.判断新的有解区间的长度是否小于精确度：判断新的有解区间的长度是否小于精确度：（1）如果新的有解区间长度大于或等于精确度，则在）如果新的有解区间长度大于或等于精确度，则在新的有解区间的基础上重复上述步骤；新的有解区间的基础上重复上述步骤；（2）如果新的有解区间长度小于精确度，则取新的有）如果新的有解区间长度小于精确度，则取新的有解区间的中点为方程的近似解解区间的中点为方程的近似解.2021/6/1628例题解析例题解析例例3 求方程求方程f(x)=x3+x2-1=0在在0,1上的近似解，精确度为上的近似解，
27、精确度为0.01.解解 根据上述分析，可以通过下列步骤求得方程的近似解：根据上述分析，可以通过下列步骤求得方程的近似解：1.因为因为f(0)=-1,f(1)=1,f(0)f(1)0.01;2.取取0,1的区间中点的区间中点0.5;3.计算计算f(0.5)=-0.625;4.由于由于f(0.5)f(1)0,可得新的有解区间可得新的有解区间0.5,1，精确度，精确度1-0.5=0.50.01；5.取取0.5,1的区间中点的区间中点0.75；2021/6/16296.计算计算f(0.75)=-0.01563;7.由于由于f(0.75)f(1)0,可得新的有解区间可得新的有解区间0.75,1,精确精确
28、度度1-0.75=0.250.01； 当得到新的有解区间当得到新的有解区间0.75,0.75782时，由于时，由于|0.75782-0.75|=0.07820.01， 该区间精确度已满足要求，所以取区间该区间精确度已满足要求，所以取区间0.75,0.75782的中点的中点0.75391，它是方程的一个近似，它是方程的一个近似解解.2021/6/1630课堂练习课堂练习1.有一把围棋子，有一把围棋子，5个个5个地数，最后余个地数，最后余下下2个；个；7个个7个地数，最后余下个地数，最后余下3个；个；9个个9个地数，最后余下个地数，最后余下4个，请设计一个，请设计一种算法，求出这把围棋子至少有多少种算法，求出这把围棋子至少有多少个？个？2.一个大油瓶装一个大油瓶装8kg油油.还有两个空油瓶，还有两个空油瓶，一个能装一个能装5kg，另一个能装，另一个能装3kg.请设计请设计一种算法，将这一种算法，将这8kg油平均分成两份油平均分成两份.2021/6/1631 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
