算法合集之《用改进算法的思想解决规模维数增大的问题》.ppt

《算法合集之《用改进算法的思想解决规模维数增大的问题》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用改进算法的思想解决规模维数增大的问题广东韶关一中张伟达一、概述本文主要讨论如何解决规模维数增大的问题二、引子：从一道IQ题说起有两根完全相同但分布不均匀的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间二、引子：从一道IQ题说起有两根完全相同但分布不均匀的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间二、引子：从一道IQ题说起有两根完全相同但分布不均匀的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间二、引子：从一道IQ题说起有两根完全相同但分布不均匀的香，

2、每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间二、引子：从一道IQ题说起有两根完全相同但分布不均匀的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间模型A.不减小每根香的计时，两根香加在一起计时是45分钟；二、引子：从一道IQ题说起显然不成立！模型A.不减小每根香的计时，两根香加在一起计时是45分钟；二、引子：从一道IQ题说起模型B.只用一根香，使其计时减小，直接计时45分钟；模型C.把两根香的计时都减小，使两根香加起来是45分钟。既然都必须把计时减小，不难看出有两头烧的方法：模型A.不

3、减小每根香的计时，两根香加在一起计时是45分钟；二、引子：从一道IQ题说起模型B.只用一根香，使其计时减小，直接计时45分钟；模型C.把两根香的计时都减小，使两根香加起来是45分钟。既然都必须把计时减小，不难看出有两头烧的方法：模型A.不减小每根香的计时，两根香加在一起计时是45分钟；二、引子：从一道IQ题说起模型B.只用一根香，使其计时减小，直接计时45分钟；模型C.把两根香的计时都减小，使两根香加起来是45分钟。既然都必须把计时减小，不难看出有两头烧的方法：如果我们两头一起烧，用一根香就能够计时30分钟。模型A.不减小每根香

4、的计时，两根香加在一起计时是45分钟；二、引子：从一道IQ题说起模型B.只用一根香，使其计时减小，直接计时45分钟；模型C.把两根香的计时都减小，使两根香加起来是45分钟。再看模型B，显然30+30是不可能等于45分钟的排除！二、引子：从一道IQ题说起C.模型+两头烧的方法(*&)@#(@^改进两头烧的方法：能够计时1小时计时30分钟能够计时间t计时t/2二、引子：从一道IQ题说起1。分别点燃第一根的两头和第二根的一头；二、引子：从一道IQ题说起1。分别点燃第一根的两头和第二根的一头；二、引子：从一道IQ题说起1。分别点燃第一根

5、的两头和第二根的一头；二、引子：从一道IQ题说起2。第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；1。分别点燃第一根的两头和第二根的一头；二、引子：从一道IQ题说起2。第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；1。分别点燃第一根的两头和第二根的一头；二、引子：从一道IQ题说起3。当第二根也烧完了，即时间又过了15分钟。那么我们计出的总的时间就为45分钟了。2。第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；1。分别点燃第一根的两头和第二根

6、的一头；二、引子：从一道IQ题说起C.模型+两头烧的方法(*&)@#(@^C.模型+改进的两头烧的方法成功解决问题二、引子：从一道IQ题说起小结一：做这类问题的主要流程：1.找出原始解法和可能改进的方向（即分析成A、B、C模型）；2.分析算法的原理（由烧一根香计时半小时，引申为烧剩t的时候点两头就能计时t/2）；3.改进算法（改进的过程中，往往不是依靠算法改进算法本身，反而是利用算法的内涵、实质，结合问题，构造算法）；4.解决问题（我们得出了正确的解法）。三、改进算法的途径1.直接增加算法的规模，解决问题2.用枚举处理增加的规模

7、，从而解决问题3.用贪心解决增加的规模，从而解决问题4.多种途径的综合运用为了能够简单明了地解释改进算法的途径，我们直接进入第4种情况，用一道例题详细讲解可以如何改进算法解决问题。【例题】TeamSelection(BalkanOI2004Day1)【题目大意】IOI要来了，BP队要选择最好的选手去参加。幸运地，教练可以从N个非常棒的选手中选择队员，这些选手被标上1到N(3≤N≤500000)。为了选出的选手是最好的，教练组织了三次竞赛并给出每次竞赛排名。每个选手都参加了每次竞赛并且每次竞赛都没有并列的。当A在所有竞赛中名次都比

8、B前，我们就说A是比Bbetter。如果没有人比Abetter，我们就说A是excellent。求：excellent选手的个数。如数据：例如5，没有选手次次竞赛都比5强，因为5在第一次竞赛中只输给了2，但是2又在第三次竞赛中输给了5，所以5是excellen