资源描述：
《精密机械课程设计2008》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析DesignandAnalysisofAlgorithmsInC++主讲王海艳计算机学院wanghy@njupt.edu.cn教材：陈慧南.算法设计与分析-C++语言描述先修课：面向对象程序设计语言C++，数据结构性质：计算机科学与技术中处于核心地位的一门专业基础课。南京邮电大学计算机学院目的：通过学习掌握算法设计的主要方法，并对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构和设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。基本任务:介绍算法的基本概念、算法设计的基本策略和方法，同时介绍算法复杂性的概念
2、、性能分析的具体方法和技巧。教学重点:算法设计的基本思想和策略，以及算法性能分析的方法等。南京邮电大学计算机学院难点:如何将算法优化的思想贯穿在设计过程中，以及算法平均性能的分析技巧。总学时：48学时。成绩考核办法：平时成绩30%，期末考试70%。南京邮电大学计算机学院第1章算法问题求解基础基本要求：本章概述算法问题、求解方法等重要概念和方法。掌握算法的基本概念，了解使用计算机求解问题的过程和方法。南京邮电大学计算机学院1.1算法概述1.2问题求解方法1.3算法设计与分析1.4递归和归纳南京邮电大学计算机学院1.1算法概述南京邮电大学计算机学院“计算机科学是一门研究算法的科学”计算机
3、的运算速度很高，但是速度再高也有它的极限。为了充分发挥计算机的高速特点，应在计算机求解问题的过程中，尽量减少人工干预。为使计算机的计算过程能够解决某一特定问题，必须为计算机设定解决方案中的每个详细步骤，并将此过程完整的描述出来。——算法Algorithm南京邮电大学计算机学院算法是数据结构的灵魂。不了解施加于数据上的算法就无法决定如何构造数据。反之，数据结构又是算法的基础。算法的结构和选择又常常在很大程度上依赖于数据结构。算法+数据结构=程序南京邮电大学计算机学院1.1.1什么是算法算法（algorithm）一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。南京邮电大学计算
4、机学院输入(input)：算法有零个或多个输入量；输出(output)：算法至少产生一个输出量；确定性(definiteness)：算法的每一条指令都有确切的定义，没有二义性；能行性(effectiveness)：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；有穷性(finiteness)：算法必须总能在执行有限步之后终止。算法的五个特征:南京邮电大学计算机学院程序(Program)是算法用某种程序设计语言的具体实现。算法必须可终止，程序却没有这一限制。即：程序可以不满足算法的性质(5)—“有穷性”。例如：操作系统是一个在无限循环中执行的程序，却不是算
5、法。因此操作系统是使用计算机语言描述的一个计算过程，而不是一个算法。南京邮电大学计算机学院求最大公约数计算两个整数m和n(0≤m＜n)的最大公约数，记为gcd(m,n)。南京邮电大学计算机学院欧几里德算法(辗转相除法)gcd(24,60)=gcd(60mod24,24)=gcd(24mod12,12)=12反复执行：gcd(m,n)=gcd(nmodm,m)直到：nmodm=0时的n=gcd(12,24)=gcd(0,12)南京邮电大学计算机学院【程序1-1】欧几里德递归算法intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}i
6、ntGcd(intm,intn){if(m>n)Swap(m,n);//保证m＜nreturnRGcd(m,n);}南京邮电大学计算机学院【程序1-2】欧几里德迭代算法intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;if(m>n)Swap(m,n);while(m>0){intc=n%m;n=m;m=c;}returnn;}gcd(m,n)=gcd(nmodm,m)南京邮电大学计算机学院gcd的连续整数检测算法最大公约数不会超过两数中的较小者，即不会超过t=min{m,n}(确定初值)执行while(m%t
7、
8、n%t)t--;gcd
9、(9,27),gcd(4,6)如t=4,(4%4
10、
11、6%4)<>0,t--t=3，(4%3
12、
13、6%3)<>0,t--t=2,(4%2
14、
15、6%2)==0,故最大公约数为2南京邮电大学计算机学院【程序1-3】Gcd的连续整数检测算法1、一个问题可以设计不同的算法；如欧几里德，连续整数检测。2、一个算法可以采用不同的形式；如递归，迭代。intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;intt=m>n?n:m;/
