第一章 算法问题求解基础

算法分析与设计

主讲：徐晓蓉

计算机科学与技术学院学习算法的必要性及目的

算法是计算机科学的基础,更是程序的基石,为了成为训练有素的软件人才,必须有良好的算法基础。

哈雷尔在他的<算法学—计算的灵魂>一书中说:”算法不仅是计算机学科的一个分支，它更是计算机科学的核心,而且可以毫不夸张地说,它和绝大多数科学、商业和技术都是相关的”

简单的说,学习算法,就是为了掌握并灵活运用已有的算法策略解决实际问题,并设计新的更有效的新算法。教材、参考书与课时安排教材

算法设计与分析--C++语言描述

陈慧南电子工业出版社参考书苏德富主编,《计算机算法设计与分析》,电子工业出版社,2000年6月；王晓东主编,《计算机算法设计与分析》(第2版),电子工业出版社，2004年7月；卢开澄主编清华大学出版社出版的《计算机指导引论－设计与分析》ThomasH.CormenCharlesE.Leiserson《算法导论（第2版）》,高等教育出版社，2002课时安排授课：48学时实验：

10学时(1次/周)课程的教学任务和目标学习并掌握各种基本的算法设计策略。学习算法分析的基本方法。学习用基本的算法设计策略解决实际问题的方法.通过对常用的、有代表性的算法的学习研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。使学生掌握算法设计过程与方法，并学会用所学知识解决实际问题,培养他们的独立科研的能力和理论联系实践的能力。主要教学内容第一章算法问题求解基础第二章算法分析基础第五章分治法第六章贪心法第七章动态规划法第八章回溯法第九章分枝限界法第十章NP完全问题课程的基本要求课前做好充分的预习保持课堂安静，头脑清醒，思维活跃重视上机实践，有效利用宝贵的上机时间,做到上机前事先对实验题目进行预习、分析并写出代码.课后认真、独立、按时完成并提交作业.本课程平时分数的组成平时分=

学习态度+

课堂考勤+

平时作业第一章算法问题求解基础算法概述问题求解方法算法设计与分析递归和归纳第一讲算法概述及算法设计与分析教学目的：1、理解并掌握算法的概念；2、理解问题求解的方法；2、理解用算法求解问题的过程。教学内容：算法的概念，算法与程序的区别与联系、问题求解的过程和方法、用算法求解问题的过程。.教学重点：算法的概念、算法与程序的区别与联系、用算法求解问题的过程。拟教课时：2（理论）教学过程：

1.1算法概述算法的概念:是对特定问题求解步骤的一种描述，是指令的有限序列。算法的特征：输入：有零个或多个外部量作为算法的输入。

输出：算法产生至少一个量作为输出。

确定性：算法的每个步骤必须有明确的意义,对每种可能的情况,算法都要给出确定的操作.能行性:算法的每一条指令必须能够实现，算法执行结果要达到预期的目的;有限性：算法必须在执行有穷个指令后终止，并且每条指令都在执行有限时间后结束。算法的三个要素：1).数据:

运算序列中作为运算对象和结果的数据.2).运算:

运算序列中的各种运算:赋值,算术和逻辑运算3).控制和转移:

运算序列中的控制和转移.1.1算法概述算法的分类:从解法上从处理方式上从解的精确程度上算法的描述方法：自然语言描述(但不够严谨)流程图(早期)和N-S图（对于复杂算法，难于建图和理解）伪代码(比自然语言精确，比程序设计语言简洁)高级程序设计语言(描述精确,但一般细节较多)—程序数值型算法:算法中的基本运算为算术运算.非数值型算法:算法中的基本运算为逻辑运算.串行算法:串行计算机上执行的算法.并行算法:并行计算机上执行的算法.精确算法:能够得到问题的精确解的算法.近似算法:只能得到问题的近似解的算法.举例:从三个数a,b,c中取最大数流程图描述N-S描述:

a>=b输入a,b,cmax=a真假max=bmax>=c真假输出max输出c开始结束a>=bmax=amax=b输入a，b，c假真max>=c输出max输出c真假输入a,b,c；If(a>=b)max=a;elsemax=bif(max<=c)max=c;输出max；自然语言描述:1,输入a,b,c2,将a和b中最大者赋值给变量max;3,将max与c比较,将两者中的大者赋值给max;4,输出max的值.1.1算法概述main(){inta,b,c,max；cin>>a>>b>>c;if(a>=b)max=a;elsemax=bif(max<=c)max=c;cout<<max；}C++语言描述伪代码描述:举例:计算写出其算法

流程图描述开始0->s1->is+i->si+1->Ii<=100？输出s结束TN-S描述:0->s1->ii<=100?s+i->si+1->i输出s的值0s1->iifi<=100s+i->si+1->Iprints自然语言描述:1,0s2,1->I3,s+i->s4,i+1->I5,判断i<=100是，转3，否则转66,输出s的值1.1算法概述伪代码描述:main(){inti,s=0;for(i=1;i<=100;i++)s=s+i;cout<<s;}C++语言描述1.1算法概述程序的概念:

当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现.程序与算法的区别：算法必须可以终止;程序则可以不满足算法的有限性,如操作系统程序，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。C++语言的特点：C++语言,类型丰富,语言精练,具有面向对象和面向过程的双重优点.C++语言既能描述算法所处理的数据结构,又能描述算法过程.用C++来描述算法可使整个算法结构紧凑、简洁明了可读性强.1.2问题求解方法1.2.1问题和问题求解问题:当前状况与目标不一致时就会产生问题问题求解:

寻找一种方法来实现目标.问题求解过程:

是人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识去选择和使用适当的问题求解策略、技术和工具,将一个问题描述转换成问题解的过程。1.2.2问题求解过程问题求解的四步法简述如下:理解问题设计方案实现方案回顾复查1.2问题求解方法1.2.3系统生命周期

计算机求解问题的过程就是一个计算机软件的开发过程，被称为软件生命周期或系统生命周期。软件生命周期可划分为如下5个阶段:分析设计编码测试维护开发期运行期1.3算法设计与分析1.3.1算法问题求解过程证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法1.3.2如何设计算法学习一些基本的算法设计策略.分析问题的特性,当该问题的特性符合于某种算法设计策略处理的问题特性时,就可使用该算法设计策略设计算法,求解问题.1.3算法设计与分析1.3.3如何确认算法（正确性）算法的正确性的定义:在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的。正确性证明的目的:确认一个算法能正确无误的工作.正确性证明的内容:方法的正确性证明——算法思路的正确性.证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序—将其分解为小的相互独立的互不相交的模块,分别验证。小模块程序—可以使用以下方法验证:数学归纳法,软件形式方法等。1.3算法设计与分析1.3.3如何确认算法（正确性）程序排错的方法程序测试定义:指对程序模块或程序总体，输入事先准备好的样本数据，检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活动目的:发现错误调试定义:诊断和纠正错误的过程1.3.4如何分析算法算法分析主要是指对算法的执行时间和所需空间的估算.小结

本次课我们主要讲解了有关算法的一些概念,算法求解问题的过程,主要理解掌握算法的概念,算法与程序之间的区别。第二讲递归和归纳教学目的：1、理解递归的概念；2、理解并掌握递归的求解问题的思想；教学内容：递归的概念，递归定义中的两个要素,递归算法举例，递归算法正确性的归纳证明.教学重点：递归的思想。教学难点：递归的思想。拟教课时：2（理论）教学过程：1.4递归和归纳什么是归纳？通过列举少量的特殊情况，经过分析，最后找出一般的关系。什么是递归？它是一个数学概念，也是一种程序设计的方法它是一种直接或间接调用自身的技术，如老和尚给小和尚讲故事。1.4.1递归定义：直接或间接引用自身的技术本质：是一种循环结构,如老和尚给小和尚讲故事.它通常是把“较复杂”的计算逐次归结为“较简单”的计算,直至归结到“最简单”的计算,并最终得到计算结果为止.如n!的递归计算。1.4递归和归纳递归求解问题的过程:类似于使用一本大词典查询一个单词的情形.如递归定义：是一种直接或间接引用自身的定义方法。

基础情况(边界条件):列举新事物的若干简单对象两个基本要素：

递归部分:给出简单对象定义新对象的条件和方法例:阶乘函数、斐波那契数列注意：只有具备这两个要素，才能在有限次计算后得到结果，否则，将会无限循环1.4递归和归纳longFib(intn){if(n<=1)return1;elsereturnFib(n-2)+Fib(n-1);}递归调用：在函数体内调用自己的做法称为递归调用递归函数定义:包含递归调用的函数.种类:直接递归、间接递归递归算法（函数）定义:直接或间接调用自身的算法，称为递归算法。Fib()函数的执行过程：Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)递归树：用以描述某一递归函数在执行过程中的调用关系的树,称为关系树.1.4递归和归纳1.4.2递归算法示例

重点掌握递归算法的设计方法.例1-2逆序输出正整数的各位数

设有正整数n=12345,要求以各位数的逆序形式输出,即输出54321。设k位正整数为d1d2…dk,为了以逆序形式输出各位数dkdk-1…d2d1,可以分成两步:(1)首先输出末位数dk;(2)如果k>1(即n>=10),则再输出由前k-1位组成的正整数d1d2…dk-1的逆序形式.voidPrintDigit(unsignedintn){cout<<n%10;if(n>=10)PrintDigit(n/10);}1.4递归和归纳例1-3汉诺塔问题

假定有三个塔座:X,Y,Z,在塔座X上有n个直径大小各不相同的圆盘，现要求依据如下原则，将此n个圆盘从X移到Z塔座:(1)每次只能移动一个盘子;(2)盘子可以放在任意一个塔座上;(3)任意时刻任意塔座都不能允许有大压小的情况.

移动过程可描述如下:(1)以塔座Z为中介，将前n-1个圆盘从X->Y;(2)将第n个圆盘移到塔座Z;(3)以塔座X为中介，将前n-1个圆盘从Y->Z.voidmove(charx,intn,chary){cout<<“Thedisk”<<n<<“ismovedfrom”<<x<<“totopoftower”<<y<<endl;}voidhanoi(intn,charx,chary,charz)

/*将塔座X上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座Z上，Y可用作辅助塔座*/

{if(n==1)move(x,1,z);/*将编号为1的圆盘从X移动Z*/elseif(n>1){hanoi(n-1,x,z,y);/*将X上编号为1至n-1的圆盘移到Y,Z作辅助塔*/move(x,n,z);/*将编号为n的圆盘从X移到Z*/

hanoi(n-1,y,x,z);/*将Y上编号为1至n-1的圆盘移动到Z，X作辅助塔*/}}1.4递归和归纳

1n=0例1-4、阶乘问题F(n)=n!=

n*(n-1)!