程序设计算法概述

《程序设计算法概述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法概述杨秋妹yqmbegonia@163.com程序=数据结构+算法乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？建立解题模型——数据结构解决方法什么是算法算法是一个有穷的解决问题的指令序列。每条指令都必须有清楚的含义并且在有穷长的时间内用有穷的动作完成。一个算法无论接受任何输入，都必须在有穷步内停止。排序问题输入：由n个数构成的一个序列输出：对输入序列的一个排列（重排）

2、an’>，使得a1’<=a2’<=…<=an’算法：插入排序，冒泡排序，快速排序，合并排序等算法的几个特性算法是指解决问题的一种方法或一个过程。满足性质：(1)输入：有零个或多个外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。什么是程序程序是算法用某种程序设计语言的具体实现程序可以不满足算法的有穷性算法的描述自然语言；程序设计语言；类程序语言算法可以

3、解决的问题人类基因的目标是找出人类DNA的所有十万种基因，确定构成人类DNA的30亿种化学基对的各种序列，将这些信息存储在数据库中，并开发出用于进行这方面数据分析的工具。因特网——快速地访问和检索大量的信息电子商务——保持信用卡号、密码、银行结单等信息的私密性，公共密钥加密技术和数字签名技术制造业和其他商业应用中，是否能最有效地分配稀有资源，例如，石油公司确定在何处打井，以求最大化预期效益；美国总统候选人希望确定该把宣传的资金花在何处，以求赢得竞选的可能性最大；常用的算法设计方法递归法（Recu

4、rsion）分治法(Divide-andConquer)、贪心法(Greedy)动态规划(DynamicProgramming)、回溯（Backtracking）分支限界法（BranchandBound）近似算法(Approximation)问题求解证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法算法的设计目标算法应易于理解、编程和调试算法应尽可能有效地利用计算机的资源，特别地，应尽可能快地运行好算法的判断标准1.正确性2.健壮性3.时间复杂性4.空间复杂性5.可

5、读性6.灵活性（Flexibility）、可重用性(Reuseabale)等算法复杂度分析算法复杂性体现在运行该算法所需要的计算机资源多少上所需资源越多，该算法的复杂性越高所需资源越少，该算法的复杂性越低时间复杂性：算法执行需要的时间资源空间复杂性：算法执行需要的空间资源百鸡问题公元5世纪末,我国古代数学家张丘建在他所撰写的《算经》中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”a：公鸡数b：母鸡数c：小鸡数a+b+c=1005a+

6、3b+c/3=100c%3=0voidchicken_question(intn,int&k,intg[],intm[],ints[]){inta,b,c;k=0;for(a=0;a<=n;a++)for(b=0;b<=n;b++)for(c=0;c<=n;c++){if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){g[k]=a;m[k]=b;s[k]=c;k++;}}}算法有三重循环内循环体的执行次数为(n+1)(n+1)(n+1)voidchicken_p

7、roblem(intn,int&k,intg[],intm[],ints[]){inti,j,a,b,c;k=0;i=n/5;j=n/3;for(a=0;a<=i;a++)for(b=0;b<=j;b++){c=n-a-b;if((5*a+3*b+c/3==n)&&(c%3==0)){g[k]=a;m[k]=b;s[k]=c;k++;}}}算法有两重循环内循环体执行次数为(n/5+1)(n/3+1)货郎担问题货郎担问题是一个经典问题。某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货

8、员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最短。用图的顶点代表城市，边的权重表示城市间的距离，这个问题可以转化为求一个图的最短哈密顿回路哈密顿回路可以定义为n＋1个相邻节点vi0,…,vin-1,vi0的一个序列可以通过生成n－1个中间城市的组合来得到所有的旅行路线，计算这些路线的长度，然后求得最短的线路算法时间复杂度O（n！）nn!nn!nn!nn!5120μs9362ms131.72h1711.27year6720μs103.62s1424h18203y