(27)--3 算法基础大学计算机.ppt

《(27)--3 算法基础大学计算机.ppt》由会员分享，可在线阅读，更多相关《(27)--3 算法基础大学计算机.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法程序设计的一般步骤问题分析：明确定义程序的目标、输入输出方式及数据类型、范围、精度等计算需求算法设计：算法就是为解决某一问题而采取的一系列方法和步骤编写代码：将算法用程序设计语言描述出来调试与运行：消除语法错误和逻辑错误程序设计语言机器语言int x;/Time New Romanfloat y;char z;算法广义上讲，算法是为解决某一问题而采取的一系列方法和步骤。更确切地说，算法就是一个有限规则的集合，其中的规则规定了解决某一特定类型问题的一个运算序列，即算法规定了任务执行或问题解决的一系列步骤。计算机科学中，算法不仅应用于数值性问题的求解中，它更广泛地应用于各类非数值性问题的求解中

2、。因此分为数值类算法、非数值类算法。数值类算法【例1】对于两个正整数m和n，求其最大公约数。Step1：输入m和n的值。Step2：m除以n，设余数为r。Step3：如果r为0，则n为所求，算法终止；否则执行Step4。Step4：令m=n，n=r，转移至Step1继续执行。上述算法也称辗转相除算法或欧几里德算法。非数值类算法【例2】4枚硬币中有1枚假币，它的重量与真币不同。请使用一架没有刻度的简易天平，用最少的次数找出那枚假币。Step1：将4枚硬币分别编号为1、2、3、4。Step2：用天平比较1、2号硬币。若重量相等，转移至Step4继续执行；若重量不等，执行Step3。Step3：用天

3、平比较1、3号硬币。若重量相等，则2号为假币；若重量不等，则1号为假币。算法终止。Step4：用天平比较1、3号硬币。若重量相等，则4号为假币；若重量不等，则3号为假币。使用上述算法，只需两次称重就能找4枚硬币中的那枚假币算法的基本特征有穷性：指一个算法应包含有限的操作步骤，而不能是无限的确定性：确定性是指算法中的每一个步骤都应当是确定的，不能出现二义性的描述有效性：也称为可行性，算法中的每一个步骤都应当能够有效地执行，并得到确定的结果有0个或多个输入有1个或多个输出算法的描述-程序流程图程序流程图（PFD，Program Flow Diagram）又称程序框图，它使用不同的图框来表示不同的操

4、作类型，并用流程线规定了算法中各步骤执行的先后顺序算法的描述-N-S图1973年，美国学者Nassi和Shneiderman提出了一种新的算法描述工具N-S图。N-S图不再使用流程线，而是将全部算法写在一个矩形框中，因而又称盒图算法的描述-PAD图1974年，日本日立公司提出了一种称为PAD图（Problem Analysis Diagram）的结构化算法描述工具。PAD图采用二维树形结构表示算法的执行流程，图中最左边的竖线是主线，即算法的第一层控制结构，每增加一个层结构，PAD图就向右扩展出一条竖线。算法的描述-伪代码伪代码（Pseudo）使用介于自然语言和和程序设计语言之间的符号来描述算法

5、。一般情况下，伪代码都是将程序设计语言语句的关键字与自然语言结合起来，自上而下书写。伪代码没有严格的语法规定，只要将算法清晰地表示出来就可以了，因此书写格式比较自由算法的衡量时间复杂度时间复杂度：指根据该算法编写的程序在运行过程中从开始到结束所需要的时间。通常以元操作重复执行的次数作为算法的时间度量NP-hard问题：NP是指非确定性多项式（non-deterministic polynomial，缩写NP），指数复杂度，随着n的增大，所需时间迅速增大算法的衡量空间复杂度空间复杂度：指算法运行中对存储空间的需求。随着计算机存储容量的增加，人们对算法的空间复杂度分析的重视程度要小于时间复杂度的分

6、，但在网络传输中，算法产生的文件大小问题成为重点问题常用算法穷举穷举法：法：如百鸡百钱问题、背包问题递推法：递推法：如斐波那契数列（黄金分割数列）递归法：递归法：如汉诺塔问题回溯法：回溯法：如走迷宫，八皇后问题迭代法：迭代法：如辗转相除求最大公约数分分治治法：法：如归并排序，折半查找贪心法：贪心法：从局部最优最终求整体最优解动态规划法：动态规划法：数学和计算机科学中由于求最优化 其他算法蒙特卡罗方法：蒙特卡罗方法：利用概率统计的思想求解 计算问题。在金融工程学、宏观经济学、计算物理学等领域有着广泛的应用蚁蚁群群算法：算法：灵感来源于蚂蚁在寻找食物的过程中发现路径的行为，在图中寻找优化路径遗传算法：遗传算法：遗传算法是计算数学中用于求解最优化方案的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为采用计算机模拟