资源描述：
《《算法设计与分析》第01章23260》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法设计与分析DeSignandAnalysisofAlgorithmsInC++“十一五”国家级规划教材陈慧南编著电子工业出版社南京邮电大学计算机学院2008年3月课程简介课程名称：算法设计与分析DesignandAnalysisofAlgorithms先修课程：面向对象程序设计语言C++，数据结构南京邮电大学计算机学院2008年3月第1部分算法和算法分析南京邮电大学计算机学院2008年3月第1章算法问题求解基础南京邮电大学计算机学院2008年3月1.1算法概述1.2问题求解方法1.3算法设计与分析1.4递归和归纳南京邮电大学计算机学院2008年3月1.1
2、算法概述南京邮电大学计算机学院2008年3月1.1.1什么是算法算法（algorithm）一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。此外，算法具有下列5个特征:南京邮电大学计算机学院2008年3月输入（input）：算法有零个或多个输入量；输出（output）：算法至少产生一个输出量；确定性（definiteness）：算法的每一条指令都有确切的定义，没有二义性；能行性（effectiveness）：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；有穷性（finiteness）：算法必须总能在执行有限步之后终止
3、。南京邮电大学计算机学院2008年3月欧几里德算法(辗转相除法)计算两个整数m和n（0≤m＜n)的最大公约数，记为gcd(m,n)。南京邮电大学计算机学院2008年3月【程序1-1】欧几里德递归算法intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}南京邮电大学计算机学院2008年3月【程序1-1】欧几里德递归算法intRGcd(intm,intn){if(m==0)returnn;returnRGc
4、d(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}南京邮电大学计算机学院2008年3月【程序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;}南京邮电大学计算机学院2008年3月【程序1-3】Gcd的连续整数检测算法intGcd(intm,intn){if(m==0)returnn;if(n==0)ret
5、urnm;intt=m>n?n:m;while(m%t
6、
7、n%t)t--;returnt;}南京邮电大学计算机学院2008年3月1.1.2为什么学习算法算法是计算机科学的基础，更是程序的基石，只有具有良好的算法基础才能成为训练有素的软件人才。对于计算机专业的学生来说，学习算法的理由是非常充分的。因为你必须知道来自不同计算领域的重要算法，你也必须学会设计新的算法、确认其正确性并分析其效率。随着计算机应用的日益普及，各个应用领域的研究和技术人员都在使用计算机求解他们各自专业领域的问题，他们需要设计算法，编写程序，开发应用软件，所以学习算法对于越来越多的人来说变得
8、十分必要。南京邮电大学计算机学院2008年3月1.2问题求解方法南京邮电大学计算机学院2008年3月1.2.1问题和问题求解问题求解（problemsolving）是寻找一种方法来实现目标。问题求解过程（problemsolvingprocess）是人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识去选择和使用适当的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。计算机求解问题的关键之一是寻找一种问题求解策略（problemsolvingstrategy），得到求解问题的算法，从而得到问题的解。南京邮电大学计算机学院2008年3月1
9、.2.2问题求解过程理解问题（understandtheproblem）设计方案（deviseaplan）实现方案（carryouttheplan）回顾复查（lookback）南京邮电大学计算机学院2008年3月1.2.3系统生命周期一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程（softwareengineering）将软件开发和维护过程分成若干阶段，称为系统生命周期（systemlifecycle）或软件生命周期。南京邮电大学计算机学院2008年3月软件生命周期划分为:分析（analysis）设计（design）编码（codingorpr
10、ogramming）测试（testing）维护（ma
