《算法的基本概念》PPT课件

《《算法的基本概念》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1算法设计与分析2DonaldE.Knuth：计算机科学就是算法研究3在计算机科学与技术中的地位操作系统、语言编译系统、数据库管理系统、以及各种各样的计算机应用系统软件，都用具体的算法来实现。算法的好坏，决定了所实现软件性能的优劣。在实现一个软件时，必须解决用什么方法设计算法、如何判定算法的性能。4目录第一章算法的基本概念第二章算法的复杂性分析第三章排序问题与离散集合的操作第四章递归与分治第五章贪婪法第六章动态规划第七章回溯第八章分支与限界第九章随机算法第十章图和网络问题第十一章计算几何问题第十二章NP完全问题第十三章计算复杂性第

2、十四章下界第十五章近似算法51.1引言一算法的定义和特征二算法设计的例子三算法的复杂性分析61.算法的定义算法是解某一特定问题的一组有穷规则的集合“Kitābal-jabrWa’lmuqābJla”（《复原和化简的规则》）→Algebra（代数）Abū‘AbdAllāhMuhammadibnMūsaal-Khwārizmī→Algorithm(算法)72.算法的特征1）有限性。算法在执行有限步之后必须终止。2）确定性。算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。3）输入。一个算法有0个或多个输入，它是

3、由外部提供的，作为算法开始执行前的初始值，或初始状态。算法的输入是从特定的对象集合中抽取的。4）输出。一个算法有一个或多个输出，这些输出，和输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。5）能行性。算法的能行性指的是算法中有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。8二算法设计的例子1.穷举法2.百鸡问题3.货郎担问题91.穷举法从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解102.百鸡问题令a：公鸡只数b：母鸡只数c：小鸡

4、只数约束方程：a+b+c=1005a+3b+c/3=100c%3=0a、b、c的可能取值范围：0~100对在此范围内的a，b、c、的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。把问题转化为用n元钱买n只鸡，n为任意正整数约束方程：a+b+c=n5a+3b+c/3=nc%3=0“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”方程求解？编程实现111）第一种解法：输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]1.voidc

5、hicken_question(intn,int&k,intg[],intm[],ints[])2.{inta,b,c;4.k=0;5.for(a=0;a<=n;a++)6.for(b=0;b<=n;b++)7.for(c=0;c<=n;c++){8.if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){9.g[k]=a;10.m[k]=b;11.s[k]=c;12.k++;13.}12第一种解法的执行时间：外循环：n+1次，中间循环：(n+1)(n+1)次，内循环：(n+1)(n+1)(n+

6、1)次。当n=100时，内循环的循环体执行次数大于100万次如何优化算法，减少执行次数？132）第二种解法：公鸡只数：a=0~n/5母鸡只数：b=0~n/3小鸡只数：c=n–a–b编程实现，内循环执行次数？14第二种解法程序：1.voidchicken_problem(intn,int&k,intg[],intm[],ints[])2.{inti,j,a,b,c;4.k=0;i=n/5;j=n/3;7.for(a=0;a<=i;a++)8.for(b=0;b<=j;b++){9.c=n–a–b;10.if((5*a+3*b+c/3

7、==n)&&(c%3==0)){11.g[k]=a;12.m[k]=b;13.s[k]=c;14.k++;15.}16.}15第二种解法的执行时间：外循环：n/5+1内循环：(n/5+1)(n/3+1)当n=100时，内循环的循环体的执行次数为2134=714次163.货郎担问题货郎担问题也叫推销商问题（travelingsalesmanproblem）,其一般提法为：有n个城市，用1，2，…，n表示，城i,j之间的距离为Sij，有一个货郎从城k出发到其他城市一次且仅一次，最后回到城市k，怎样选择行走路线使总路程最短？有？条线

8、路173.货郎担问题n个城市共有n!个排列，采用穷举法逐一计算每一条路线的费用，从中找出费用最小的路线，便可求出问题的解。18货郎担问题的穷举法版本输入：城市个数n,费用矩阵c[][]输出：旅行路线t,最小费用min1.voidsalesman_p