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

1算法的基本思想(第二课时),主讲人：刘冬发,CompanyLogo,例题解析,例4“韩信点兵”问题韩信是汉高祖刘邦手上的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳.据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵方式：先令士兵从13报数，结果最后一个士兵报2；再令士兵从15报数，结果最后一个士兵报3；又令士兵从17报数，结果最后一个士兵报4.这样，韩信很快计算出了自己部队士兵的总人数.请设计一个算法，求出士兵至少有多少人.,CompanyLogo,分析理解,士兵从13报数，最后一个士兵报2。这句话说明士兵的总人数除以3余2。算法的第一步是将所有除以3余2的正整数找出来，按照从小到大的顺序排成一列数。士兵从15报数，最后一个士兵报3。这句话说明士兵的总人数除以5余3。算法的第二步是从上列数中找出除以5余3的一列数。最后，在满足前两个条件的上列数中再找出除以7余4的一列数，这列数中最小的数，即为我们所求的数可。,CompanyLogo,解算法步骤如下：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；4.然后依次加上15，得到8，23，38，53，不难看出，这些数既满足除以3余2，又满足除以5余3；5.在第4步得到得以列数中找出满足除以7余4的最小数53，这就是我们要求的数。在完成上述步骤后就找到了所求的数53，这5个步骤称为解决“韩信点兵”问题的一个算法,分析理解,CompanyLogo,想一想,大家可以想一想，能否在这个算法的基础会上作一些改进，以更快地获得结果？实际上，我们颠倒一下3，5，7的顺序，就可以得到另一个算法；1.首先确定最小的除以7余4的正整数：4；2.依次加7就得到所有除以7余4的正整数；4，11，18，25，32，39，46，53，60，3.在第2步得到的一列数中确定最小的除以5余3的正整数：18；4.然后依次加上35，得到18，53，88，5.在第4步得到的一列数中找出最小的满足除以3余2的正整数：53。,从例4的两个算法中，你能得到哪些启示？,CompanyLogo,例题解析,例5一位商人有9枚银元，其中有一枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,最容易想到的解决这个问题的一种方法是：把9枚银元按顺序排成一列，先称前2枚，若不平衡，则可找出假银元；若平衡，则2枚银元都是真的，再依次与剩下的银元比较，就能找出假银元。,CompanyLogo,分析理解,解按照下列步骤，就能将假银元找出来：1.任取2枚银元分别放在天平的两边。如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则进行第二步。2.取下右边的银元，放在一边，然后把剩余的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。这种算法最少要称1次，最多要称7次，是不是还有更好的办法，使得称量次数少一些？我们可以采用下面的方法：1.把银元分成3组，每组3枚。2.先将两组分别放在天平的两边。如果天平不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的第3组里。3.取出含假银元的那一组，从中任取两枚银元放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元。,CompanyLogo,分析理解,进分析发现，这种算法只需称量两次，这种做法要明显好于前一种做法。当然，这两种方法都具有一般性，同样适用于n枚银元的情形。这是信息论中的一个模型，可以帮助我们找出某些特殊信息。从以上两个问题中可以看出，同一个问题可能存在着多种算法，其中一些可能要比另一些好。在实际问题和算法理论中，找出好的算法是一项重要的工作。,CompanyLogo,课堂练习,1.有一把围棋子，5个5个地数，最后余下2个；7个7个地数，最后余下3个；9个9个地数，最后余下4个，请设计一种算法，求出这把围棋子至少有多少个？2.一个大油瓶装8kg油.还有两个空油瓶，一个能装5kg，另一个能装3kg.请设计一种算法，将这8kg油平均分成两份.,CompanyLogo,课堂练习答案,解（1）首先确定最小的除以9余4的正整数为：4，（2）依次加9得到所有除以9余4的正整数：4，13，22，31，40，49，58，67，（3）在上列数中确定最小的除以7余3的数：31（4）依次加上63得到31，94，157，220，283，346，（5）在上列数中最小的除以5余2的数为157.即157为所求.,1.有一把围棋子，5个5个地数，最后余下2个；7个7个地数，最后余下3个；9个9个地数，最后余下4个，请设计一种算法，求出这把围棋子至少有多少个？,CompanyLogo,课堂练习答案,解不妨设8kg的大油瓶为A，5kg和3kg的油瓶分别为B，C.（1）从A往C倒3kg，将C装满，此时A中剩下5kg油.（2）将C瓶中的3kg油倒进B瓶.（3）再从A往C倒3kg油.（4）从C往B倒2kg油，既将B瓶装满.（5）将B中的油全部倒入A.（6）将C中的油全部倒入B.（7）从A往C倒油，将C装满，此时A中油为4kg.（8）将