1、参考学时为参考学时为6072学时学时n建议采用理论教学与上机实践相结合的教学模式建议采用理论教学与上机实践相结合的教学模式;n第第1至第至第9章分别为章分别为68学时学时,第第10章作为自学提高章作为自学提高（含上机实践，具体由任课教师根据教学实际确定）（含上机实践，具体由任课教师根据教学实际确定）n各常用算法的概念与设计要点。各常用算法的概念与设计要点。n重点讲授应用算法设计求解基本的典型案例，重点讲授应用算法设计求解基本的典型案例，并通过相关程序，引导设计变通。并通过相关程序，引导设计变通。n在基本案例引导下自学相关联案例求解。在基本案例引导下自学相关联案例求解。n小组讨论与基本案例相关的
2、拓展与引申案例求小组讨论与基本案例相关的拓展与引申案例求解，为解，为“课程设计课程设计”作准备。作准备。n学会归纳、总结和提炼；n自觉调整学习状态：培养案例求解兴趣培养案例求解兴趣自觉完成布置的作业自觉完成布置的作业加深对算法应用的理解加深对算法应用的理解善于变通、拓展与改进善于变通、拓展与改进n注重算法设计，提高解决实际案例的能力。注重算法设计，提高解决实际案例的能力。上机环境：上机环境：VC+6.0VC+6.0上机通过每章指定的案例求解程序与习题上机通过每章指定的案例求解程序与习题按要求填写实验报告按要求填写实验报告 教学要求教学要求 了解了解算法概念、算法特征及算法的描述算法概念、算法特
3、征及算法的描述 建立建立算法复杂性概念算法复杂性概念 掌握结构化掌握结构化程序设计程序设计的基本方法的基本方法 本章重点本章重点 应用应用 c c 语言描述算法语言描述算法 基本掌握算法时间复杂度分析基本掌握算法时间复杂度分析1.1 算法及其描述算法是程序设计的基础，是计算机科学的核心。算法是程序设计的基础，是计算机科学的核心。1.1.1 1.1.1 算法概念算法概念 算法是计算机解决问题的过程，是解决某一问算法是计算机解决问题的过程，是解决某一问题的运算序列。或者说算法是题的运算序列。或者说算法是问题求解过程的运问题求解过程的运算描述。算描述。当面临某一问题时，需要找到用计算机解决这个当面临
4、某一问题时，需要找到用计算机解决这个问题的方法与步骤，算法就是问题的方法与步骤，算法就是解决这个问题的方解决这个问题的方法与步骤的描述。法与步骤的描述。1.算法的三要素 算法由操作、控制结构与数据结构算法由操作、控制结构与数据结构三者组成。三者组成。(1)(1)操作：算术运算，关系运算，逻辑运算；输入、操作：算术运算，关系运算，逻辑运算；输入、输出、赋值等操作。输出、赋值等操作。(2)(2)控制结构：顺序结构，选择结构，循环结构，控制结构：顺序结构，选择结构，循环结构，模块调用。模块调用。(3)(3)数据结构：数据之间的逻辑关系。数据结构：数据之间的逻辑关系。2.算法的基本特征 一个算法由有限
5、条可完全机械地执一个算法由有限条可完全机械地执行的、有确定结果的指令组成，具行的、有确定结果的指令组成，具有以下特性：有以下特性：(1)(1)确定性确定性 (2)(2)可行性可行性 (3)(3)有穷性有穷性 (4)(4)算法有零个或多个输入算法有零个或多个输入 (5)(5)算法有一个或多个输出算法有一个或多个输出 1.1.2 算法描述 （1 1）一个问题可以设计不同的算法来求解；）一个问题可以设计不同的算法来求解；同一个算法可以采用不同的形式来表述。同一个算法可以采用不同的形式来表述。（2 2）描述算法可以有：）描述算法可以有：自然语言方式、流程图方自然语言方式、流程图方式、伪代码方式、计算机
6、语言表示方式与表格式、伪代码方式、计算机语言表示方式与表格方式方式等等。（3 3）当一个算法使用计算机程序设计语言描述时，）当一个算法使用计算机程序设计语言描述时，就是程序。就是程序。本书采用本书采用C C语言与自然语言相结合来描述算法。语言与自然语言相结合来描述算法。例1-1 求两个整数m,n的最大公约数的欧几里德算法(1)(1)数数 m m 除以除以 n n 得余数得余数 r r；若；若r=0r=0，则，则n n为为所求的最大公约数。所求的最大公约数。(2)(2)若若 r0r0，以，以n n为为m m，r r为为n n，继续，继续(1).(1).欧几里德算法具体描述如下：欧几里德算法具体描
7、述如下：input(input(m,nm,n)；/输入的简略表示输入的简略表示r=r=m%nm%n;while(r!=0)while(r!=0)/实施辗转相除实施辗转相除 m=n;n=r;r=m=n;n=r;r=m%nm%n;print(n);print(n);/输出的简略表示输出的简略表示 1.2 算法的复杂性分析 算法的复杂性越高，所需的计算机资源越多。算法的复杂性越高，所需的计算机资源越多。最重要的计算机资源是时间资源与空间资源。最重要的计算机资源是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。需要计
8、算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效时间复杂度与空间复杂度集中反映算法的效率。率。1.2.1 时间复杂度 要想充分理解算法并有效地应用算法求解实际案要想充分理解算法并有效地应用算法求解实际案例，关键是对算法的分析。通常我们可以利用例，关键是对算法的分析。通常我们可以利用实实验对比方法、数学方法验对比方法、数学方法来分析算法来分析算法。实验对比分析很简单，两个算法相互比较求解时实验对比分析很简单，两个算法相互比较求解时间间 。数学方法能在严密的逻辑推理基础上判断算法的数学方法能在严密的逻辑推理基础上判断算法的优劣。优劣。在算法分析中，我们往往采用能近似表达性能的
9、在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。方法来展示某个算法的性能指标。一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。一条语句的数量级即执行它的频数，一个算一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。法的数量级是指它所有语句执行频数之和。在分析算法时，隐藏细节的数学表示方法为在分析算法时，隐藏细节的数学表示方法为大写字母大写字母“OO”记法，它可以帮助我们简化算记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主
10、要成分法复杂度计算的许多细节，提取主要成分。2个语句各执行1次，共执行2次。时间复杂度为O(1)(1)x=x+1;s=s+x;n(2)for(k=1;k=n;k+)n x=x+y;n y=x+y;n s=x+y;“k=1”“k=1”执行执行1 1次；次；“k=n”k=n”与与“k+”k+”各执行各执行n n次；次；3 3个赋值语句，个赋值语句，每个赋值语句各执行每个赋值语句各执行n n次；共执行次；共执行5n+15n+1次次.时间复杂度为时间复杂度为O(n).O(n).(3)for(t=1,k=1;k=n;k+)(3)for(t=1,k=1;k=n;k+)n t=t t=t*2;2;n for
11、(j=1;j=t;j+)for(j=1;j=t;j+)n s=s+j;s=s+j;“t=1”“t=1”与与“k=1”k=1”各执行各执行1 1次；次；“k=n”k=n”与与“k+”k+”各各执行执行n n次；次；“t=t=t t*2”2”执行执行n n次；次；“j=1”j=1”执行执行n n次；次；“j=t”j=t”、“j+”j+”与内循环的赋值语句与内循环的赋值语句“s=s=s+js+j”各各执行频数为执行频数为:总的执行频数为：总的执行频数为：n 在估算算法的时间复杂度时，为简单计，以后在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算只考虑内循环语句的执行频
12、数，而不细致计算各循环设计语句及其它语句的执行次数，这样各循环设计语句及其它语句的执行次数，这样简化处理不影响算法的时间复杂度。简化处理不影响算法的时间复杂度。n例例1-3 估算以下程序段所代表算法的时间复杂度。估算以下程序段所代表算法的时间复杂度。nfor(k=1;k=n;k+)nfor(j=1;j=k;j+)n x=k+j;n s=s+x;每个赋值语句执行频率为每个赋值语句执行频率为n(n+1)/2,该算法该算法的时间复杂度为的时间复杂度为:O(n2)一个算法的运行时间，与问题的规模相关，也一个算法的运行时间，与问题的规模相关，也与输入的数据相关。与输入的数据相关。n例如对给定的例如对给定
13、的n n个整数个整数a(1),a(2),a(n)a(1),a(2),a(n)排序：排序：n for(i=1;i=nfor(i=1;i=n1;i+)1;i+)n for(j=i+1;j=n;j+)for(j=i+1;jaj)h=ai;ai=aj;aj=h;if(aiaj)h=ai;ai=aj;aj=h;3个赋值语句的执行频数之和，最理想的情形下个赋值语句的执行频数之和，最理想的情形下为零（当所有为零（当所有n个整数已从小到大排列时），最坏情个整数已从小到大排列时），最坏情形下为形下为3n(n1)/2（当（当n个整数为从大到小排列时）。个整数为从大到小排列时）。按平均情形来分析，其时间复杂度为按平
14、均情形来分析，其时间复杂度为O(n2)。对于一个实用算法，我们通常不必深入研究它对于一个实用算法，我们通常不必深入研究它时间复杂度的上界和下界，只需要了解该算法时间复杂度的上界和下界，只需要了解该算法的特性，然后在合适的时候应用它。的特性，然后在合适的时候应用它。对算法的改进与优化，主要表现在有效缩减对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。算法的运行时间与所占空间。n一个程序运行所需的存储空间通常包括固定空间一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。需求与可变空间需求两部分。1.固定空间需求包括程序代码、常量与静态变固定空间需求包括程序代码、常
15、量与静态变量等所占的空间。量等所占的空间。2.可变空间需求包括局部作用域非静态变量所可变空间需求包括局部作用域非静态变量所占用的空间、从堆空间中动态分配的空间与占用的空间、从堆空间中动态分配的空间与调用函数所需的系统栈空间等。调用函数所需的系统栈空间等。算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。从应用的角度看，因空间所限影响算法运行的情形较为少见。因而在设计算法时，应把降低算法的时间复杂度作为首要的考虑因素。1.3 算法设计与分析示例 例1-5 最大公约数 前面例1-1给出了欧几里德算法.1.应用最大公约数的定义设计要点：设置c循环枚举从n开始递减至1，在循环中逐
16、个检测c是否满足条件:m%c=0 and n%c=0 最先满足的c即为所求.2.应用定义算法描述 main()long m,n,c;printf(请输入正整数m,n:);scanf(%ld,%ld,&m,&n);/输入正整数m,n if(mn for(c=n;c=1;c-)/c枚举循环 if(m%c=0&n%c=0)break;/按定义判定 printf(%ld,%ld)=%ldn,m,n,c);/输出结果 3.两个算法时间复杂度比较 按最大公约数定义的枚举算法运算频数按平均情形其运算频数估值为n/2，或为n/3等，算法的时间复杂度为O(n)。欧几里德算法的时间复杂度平均情形可按每次辗转相除的
17、余数减半估算，时间复杂度为O(logn)。显然欧几里德算法的时间复杂度较低，其求解效率较高。1.3.3 平方根不等式例1-7 对指定的正数d，试求满足以下平方根不等式的正整数n。1.按n递增循环设计（1）若sd，n增1后继续按上式求和判别。直至上述sd时,输出不等式的解。12nnnd（2）算法描述 scanf(%lf,&d);/输入任意正数 n=0;while(1)n+;s=0;for(i=n;i=d)break;else s1=s;/为以下注明提供依据 printf(不等式的解为:n%ldn,n);2.应用递推设计求解（1）递推关系 对于n-1与n,累加和s(n-1)与s(n)显然满足如下递
18、推关系：（2）初始条件 （3）算法描述 n scanfscanf(%(%lf,&dlf,&d);/);/输入任意正数输入任意正数nn=1;s=1.0+sqrt(2);/s(1)n=1;s=1.0+sqrt(2);/s(1)赋初值赋初值ndodon n+;n+;n s=s-s=s-sqrtsqrt(n-1)+(n-1)+sqrtsqrt(2(2*n-1)+n-1)+sqrtsqrt(2(2*n);n);n /递推计算递推计算n while(sd);while(sd);n printfprintf(不等式的解为不等式的解为:n%:n%ldld n,nn,n););3.两个算法时间复杂度比较对于前面
19、按对于前面按n n递增设置双重循环，时间复杂度递增设置双重循环，时间复杂度为为O(n2)O(n2)；而按递推设计简化为单循环，时间复杂度降低而按递推设计简化为单循环，时间复杂度降低为为O(n)O(n)。显然后者的求解效率大大高于前者，从以上实显然后者的求解效率大大高于前者，从以上实际运行示例可具体比较两者效率的明显差异。际运行示例可具体比较两者效率的明显差异。计算机的一切操作都是由程序控制的，离开了程序，计算机的一切操作都是由程序控制的，离开了程序，计算机将一事无成。从这个意义来说，计算机的本计算机将一事无成。从这个意义来说，计算机的本质是程序的机器，程序是计算机的灵魂。质是程序的机器，程序是
20、计算机的灵魂。算法是程序的核心。程序是某一算法用计算算法是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。机程序设计语言的具体实现。程序设计反映了利用计算机解决问题的全过程，程序设计反映了利用计算机解决问题的全过程，包括包括:建立数学模型建立数学模型;数据的组织方式数据的组织方式;设计合适设计合适的算法的算法;编写程序来实现算法编写程序来实现算法;上机调试程序，上机调试程序，使之运行后能产生求解问题的结果。使之运行后能产生求解问题的结果。一个程序应包括对数据的描述与对运算操一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。作的描述两个方面的内容。数据结构数据结构+算法算法=
21、程序程序 数据结构是对数据的描述数据结构是对数据的描述;算法是对运算操作的描述。算法是对运算操作的描述。顺序结构、选择结构和循环结构 结构化程序设计方法是目前国内外普遍采用的一结构化程序设计方法是目前国内外普遍采用的一种程序设计方法。种程序设计方法。结构化程序设计方法在实践中不断发展和完善，结构化程序设计方法在实践中不断发展和完善，已成为软件开发的重要方法讨论。已成为软件开发的重要方法讨论。n（1）自顶向下，逐步求精自顶向下，逐步求精n（2）模块化设计模块化设计n（3）结构化编码结构化编码/实现欧几里德算法的函数实现欧几里德算法的函数/求求n n个整数的最大公约数个整数的最大公约数在设计好一个
22、结构化的算法之后，还在设计好一个结构化的算法之后，还需进行结构化编码，将已设计好的算需进行结构化编码，将已设计好的算法用计算机语言来表示，编写出能在法用计算机语言来表示，编写出能在计算机上进行编译与运行的程序。计算机上进行编译与运行的程序。结构化程序设计的过程就是将问题结构化程序设计的过程就是将问题求解由抽象逐步具体化的过程。这种求解由抽象逐步具体化的过程。这种方法符合人们解决复杂问题的普遍规方法符合人们解决复杂问题的普遍规律，可以提高程序设计的质量和效率。律，可以提高程序设计的质量和效率。第1章作业习题习题1:1,2,3,4,51:1,2,3,4,5 上机通过本章例上机通过本章例1-5,1-6,1-71-5,1-6,1-7；通过数据测试比较不同算法的效率。通过数据测试比较不同算法的效率。上机通过本章例上机通过本章例1-101-10；上机通过习题上机通过习题 1-6:1-6:输出输出n=15,n=21n=15,n=21的对称方阵的对称方阵;参考附录参考附录A A 部分习题求解提要部分习题求解提要参见附录参见附录B B 在在VC+6.0VC+6.0环境环境下运行下运行C C程序方法简介程序方法简介 返回返回
