1、第六章第六章 算法与程序设计基础算法与程序设计基础大学计算机基础大学计算机基础 主要内容主要内容 6.1 6.1 程序设计概述程序设计概述6.2 6.2 算法基础算法基础 6.3 6.3 数据的组织结构数据的组织结构 6.4 6.4 问题求解与程序设计方法问题求解与程序设计方法 6.5 Raptor6.5 Raptor可视化工具可视化工具 1.1.什么是程序什么是程序 程序程序（programprogram）是指按照一定的顺序安排工作的操作序）是指按照一定的顺序安排工作的操作序列，即完成某些工作的具体步骤。列，即完成某些工作的具体步骤。6.1.1 6.1.1 程序设计的概念程序设计的概念6.1
2、 6.1 程序设计概述程序设计概述 计算机程序是计算机为完成某一任务所必须执行的一系计算机程序是计算机为完成某一任务所必须执行的一系列指令的有序集合，是用计算机语言对所要解决问题进行完列指令的有序集合，是用计算机语言对所要解决问题进行完整而准确的描述。程序表达了人的思想，体现了程序员要求整而准确的描述。程序表达了人的思想，体现了程序员要求计算机执行的操作，也是程序设计的最终结果。计算机执行的操作，也是程序设计的最终结果。程序设计程序设计算法算法数据结构数据结构程序设计应该包括两个方面的内容:算法：为解决某个问题而采取的方法和步骤的描述。算法：为解决某个问题而采取的方法和步骤的描述。数据结构：对
3、程序中数据的描述。数据结构：对程序中数据的描述。程序设计的一般过程:分析问题分析问题 建立数据模型建立数据模型 确定确定数据结构和算法数据结构和算法 编写程序编写程序 运行和调试程序运行和调试程序 目的性目的性 程序有明确的编写目的，运行时完成赋予它的功能。程序有明确的编写目的，运行时完成赋予它的功能。分步性分步性 程序由一系列计算机可执行的步骤组成，执行这些步骤可以程序由一系列计算机可执行的步骤组成，执行这些步骤可以完成其复杂的功能。完成其复杂的功能。有序性有序性 程序的执行步骤是有序的，必须严格按其执行顺序执行，不程序的执行步骤是有序的，必须严格按其执行顺序执行，不可随意改变。可随意改变。
4、有限性有限性 程序是有限的指令序列，所包含的步骤是有限的。程序是有限的指令序列，所包含的步骤是有限的。操作性操作性 有意义的程序能对某些对象进行操作，使其改变状态，完成有意义的程序能对某些对象进行操作，使其改变状态，完成其功能。其功能。2 2.程序的特性程序的特性 （1 1）变量、运算符、表达式）变量、运算符、表达式 变量：程序中定义的、存储参与运算的数据和中间结果的单元变量：程序中定义的、存储参与运算的数据和中间结果的单元 运算符：程序中规定的进行各种运算的描述符号。运算符：程序中规定的进行各种运算的描述符号。如如 +、-、*、/、=10)x=a;print x;如：if(ab)x=a;el
5、se x=b;print x;（3 3）循环结构）循环结构 在给定条件下，反复执行循环体，直到条件在给定条件下，反复执行循环体，直到条件不满足为止。如，不满足为止。如，重复做某事重复做某事，小学生抄写单词。，小学生抄写单词。1 1)当当型循环型循环结构结构不成立不成立 PA成立成立 当当P P条件成立时，反复执行条件成立时，反复执行A,A,直到直到P P不成立不成立为止为止。如：如：while(i=10)s=s+i;i+;2 2)直到直到型循环型循环结构结构先执行先执行A A操作，再判断操作，再判断P P是否成立，若是否成立，若P P成立，再执成立，再执行行A A，直到，直到P P不成立为止。
6、不成立为止。AP成立成立不成立不成立 5 5.程序设计语言程序设计语言程序设计语言分类程序设计语言分类:机器语言机器语言 汇编语言汇编语言 高级语言高级语言面向过程的语言：面向过程的语言：BasicBasic、C C语言、语言、FORTRANFORTRAN、PascalPascal面向对象的语言：面向对象的语言：VBVB、C+C+、JavaJava、DelphiDelphi、PythonPython语言处理程序语言处理程序 高级语言的翻译程序有两种工作方式：一种是解释方式，高级语言的翻译程序有两种工作方式：一种是解释方式，另一种是编译方式。另一种是编译方式。（1）解释方式）解释方式 解释方式的
7、翻译工作由解释程序来完成。在这种方式下，解释方式的翻译工作由解释程序来完成。在这种方式下，解释程序对源程序逐条地进行分析，若没有发现错误，则将解释程序对源程序逐条地进行分析，若没有发现错误，则将该语句翻译成一个或多个机器指令，然后立即执行这些指令；该语句翻译成一个或多个机器指令，然后立即执行这些指令；当发现错误时，会立即停止并给出错误提示。解释方式边解当发现错误时，会立即停止并给出错误提示。解释方式边解释边执行，不产生目标程序。其工作过程如图所示。释边执行，不产生目标程序。其工作过程如图所示。计算结果计算结果解释程序解释程序高级语言源程序高级语言源程序（2）编译方式）编译方式 编译方式的翻译工
8、作由编译程序完成。编译程序对源程序编译方式的翻译工作由编译程序完成。编译程序对源程序进行编译处理，产生一个与源程序等价的目标程序。进行编译处理，产生一个与源程序等价的目标程序。目标程序不能直接运行，需要使用连接程序将目标程序与目标程序不能直接运行，需要使用连接程序将目标程序与程序中用到一些库函数或调用其他程序段组装在一起，才能程序中用到一些库函数或调用其他程序段组装在一起，才能够形成一个完整的可执行程序。够形成一个完整的可执行程序。产生的可执行程序可以脱离编译程序和源程序独立存在，产生的可执行程序可以脱离编译程序和源程序独立存在，并可以反复运行。并可以反复运行。编译方式执行速度快，但修改源程序
9、后必须重新编译。编译方式执行速度快，但修改源程序后必须重新编译。大多数高级语言都采用编译方式。大多数高级语言都采用编译方式。高级语言高级语言源程序源程序 编译编译程序程序 机器语言机器语言目标程序目标程序 目标程序目标程序+运行子程序运行子程序 运行运行结果结果 数据数据 编译阶段编译阶段 执行阶段执行阶段 生成机器语言目标程序的编译方式（2）编译）编译方式方式编译方式的工作过程示意图：1.1.算法的定义算法的定义算法算法(algorithm)是对特定问题求解步骤的一种是对特定问题求解步骤的一种描述，描述，是是一一组如何做某件事情的指令，是一组有序的动作。算法是处理组如何做某件事情的指令，是一
10、组有序的动作。算法是处理解决问题的思路及解决问题的思路及办法，是程序的灵魂。办法，是程序的灵魂。6.2.1 6.2.1 算法的概念与特征算法的概念与特征6.2 6.2 算法基础算法基础算法无处不在算法无处不在 小学生作业小学生作业 DIYDIY家具的组装说明家具的组装说明 洗衣机使用说明洗衣机使用说明 飞机安全出口上的说明飞机安全出口上的说明 问路问路算法的分类算法的分类 在计算机领域中，将解决不同性质问题的算法划分成为不在计算机领域中，将解决不同性质问题的算法划分成为不同的类型。同的类型。数值算法数值算法：主要解决一些工程上的数值计算问题，其特点：主要解决一些工程上的数值计算问题，其特点是运
11、算复杂且有少量的输入、输出。例如数值积分、数值求是运算复杂且有少量的输入、输出。例如数值积分、数值求解微分方程等。解微分方程等。非数值算法非数值算法：用于对大量数据的处理，其特点是运算简单：用于对大量数据的处理，其特点是运算简单且有大量的输入、输出。例如对图书检索、工资管理等。且有大量的输入、输出。例如对图书检索、工资管理等。2.2.算法的基本特征算法的基本特征 算法是一个有穷规则的集合，算法是一个有穷规则的集合，它产生结果并在有限的时它产生结果并在有限的时间内终止。间内终止。这些规则确定了解决某类问题的一个运算序列这些规则确定了解决某类问题的一个运算序列。算法的基本特征算法的基本特征：v有有
12、穷性穷性：算法必须在执行有限个操作后终止；算法必须在执行有限个操作后终止；v确定性确定性：算法中每一步的含义必须是确切的，不能出现算法中每一步的含义必须是确切的，不能出现任何任何二义性；二义性；v有效性有效性：算法中的每一步操作都应该能有效执行，一个算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的；不可执行的操作是无效的；v有零个或多个输入有零个或多个输入：执行算法时，从外界获得必要的执行算法时，从外界获得必要的信信息；息；v有一个或多个输出有一个或多个输出：算法算法的结果就是输出，可以是返回的结果就是输出，可以是返回的数值，或某些操作（例如打印输出）。的数值，或某些操作（例如打
13、印输出）。算法的评价标准v正确性(Correctness)-程序中不含语法错误；程序中不含语法错误；-程序对于合法的输入数据都能够得出满足要求的结果。程序对于合法的输入数据都能够得出满足要求的结果。v可读性(Readability)-算法应该易于人的算法应该易于人的理解理解 -晦涩难读的算法易于隐藏较多错误而难以调试。晦涩难读的算法易于隐藏较多错误而难以调试。v健壮性(Robustness)-当当输入数据非法时，输入数据非法时，算法恰当的做出反应或进行相算法恰当的做出反应或进行相 应处理，而不是产生莫名其妙的输出结果。应处理，而不是产生莫名其妙的输出结果。-处理出错的方法，不是中断程序，而是返
14、回一个表示处理出错的方法，不是中断程序，而是返回一个表示 错误或错误性质的值，以便进行处理。错误或错误性质的值，以便进行处理。v高效率和低存储量 -对于相同规模的问题，执行时间短、占用空间少。对于相同规模的问题，执行时间短、占用空间少。6.2.2 6.2.2 算法的性能评价算法的性能评价1.1.时间复杂时间复杂度度 时间复杂度是指算法所需的时间复杂度是指算法所需的时间随着时间随着问题问题规模规模n变大而增加变大而增加的程度，同一问题可用不同算法解决，各种算法中，语句执行次的程度，同一问题可用不同算法解决，各种算法中，语句执行次数越多，则该算法耗费的时间越长。数越多，则该算法耗费的时间越长。一个
15、算法中一个算法中语句执行语句执行的次数，也称作语句频度或时间频度，的次数，也称作语句频度或时间频度，记为记为T(n)。算法的算法的基本基本操作重复执行操作重复执行的次数一般是问题规模的次数一般是问题规模n的的一个函数一个函数f(n)，f(n)是是和和 T(n)同数量级（同阶）的函数同数量级（同阶）的函数。算法的时间复杂度记做：算法的时间复杂度记做：T(n)=O(f(n)随随问题规模问题规模n n的增大，算法执行时间的的增大，算法执行时间的增长率和增长率和f(n)的的增长率增长率相同，相同，f(n)越小越小，算法的时间复杂度越低，效率越高算法的时间复杂度越低，效率越高。该方法该方法可独立于机器的
16、软件、硬件系统来分析算法在效率方面的优劣。可独立于机器的软件、硬件系统来分析算法在效率方面的优劣。T(n)的同数量级（从小到大）：的同数量级（从小到大）：1，Log2n，n，n Log2n，n2，n3，2n，n！算法的性能评价算法的性能评价T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)例例 x=0;y=0;for(k=0;k 2*n;k+)x+;for(i=0;i n;i+)for(j=0;j n;j+)y+;频度最大频度最大语句重复执行次数的语句重复执行次数的阶数阶数=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2)例例 ：两个：两个n nn
17、 n阶矩阵相乘阶矩阵相乘 for(for(i i=0;in;=0;in;i i+)+)for(j=0;j for(j=0;jn;jn;j+)+)c ci ij=0;j=0;for(k=0;k for(k=0;k=80输出输出gii+1 ii50结束结束成立成立不成立不成立不成立不成立成立成立传统流程图用流传统流程图用流程线指出各框的程线指出各框的执行顺序，对流执行顺序，对流程线的使用没有程线的使用没有严格限制。严格限制。2 2）NSNS流程图流程图 NSNS流程图流程图 由美国学者由美国学者I.I.N Nassiassi和和B.B.S Shneidermanhneiderman提出表示提出表示
18、算法的图形工具。基本单元是矩形框算法的图形工具。基本单元是矩形框,用不同的形用不同的形状线分割状线分割,表示三种结构。只有一个入口表示三种结构。只有一个入口,一个出口一个出口,没有流程线。没有流程线。N-SN-S图的优点图的优点 比文字描述直观、形象、比文字描述直观、形象、易于理解；比传统易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，法结构是由各个基本结构按顺序组成的，N-SN-S流程流程图中的上下顺序就是执行时的顺序。图中的上下顺序就是执行时的顺序。三种基本程序结构的三种基本程序结构的NSNS流程图
19、流程图条件条件TF语句1 语句2选择结构选择结构语句语句1 1语句语句2 2顺序结构顺序结构循环结构循环结构 循环体循环体循环体循环体当条件成立时当条件成立时 直到条件成立直到条件成立循环结构一循环结构一循环结构二循环结构二0t,1ii+1i t+it直到直到 i100输出输出 t 的值的值传统流程图与传统流程图与N-SN-S流程图的比较流程图的比较i100 NY开始开始 0t,1ii+1i t+it输出输出 t 的值的值结束结束例例1 1：1+2+3+1+2+3+加到加到100100为止为止 伪代码是介于自然语言和计算机语言之间的、用文字伪代码是介于自然语言和计算机语言之间的、用文字和符号来
20、描述算法的工具。伪代码不能被计算机理解，但接和符号来描述算法的工具。伪代码不能被计算机理解，但接近某种语言编写的程序，便于转换为编程语言。近某种语言编写的程序，便于转换为编程语言。根据编程语言的不同，有不同的描述语言。根据编程语言的不同，有不同的描述语言。例：求例：求 用用VBVB的伪代码。的伪代码。niisum1Proc PsumProc Psum Input n Input n 0=sum 0=sum 1=i 1=i While i=n While isum i+sum=sum i+1=i i+1=i Print sum Print sumEnd End 6.2.4 6.2.4 典型算法设
21、计典型算法设计1.1.基本算法基本算法 为了进一步理解算法和设计算法，本节介绍为了进一步理解算法和设计算法，本节介绍求和、乘积、最大、最小、排序、查找求和、乘积、最大、最小、排序、查找几个基几个基本算法。本算法。（1）求和算法）求和算法 在用计算机解决实际问题中，在用计算机解决实际问题中，经常涉及到求一系列数之和，经常涉及到求一系列数之和，例如求学生成绩的平均值，例如求学生成绩的平均值，首选就需要把所有学生成绩累加首选就需要把所有学生成绩累加起来。起来。求和算法是计算机科学中经常用到的一种算法，为了把一求和算法是计算机科学中经常用到的一种算法，为了把一系列数据加起来，需要重复进行加法操作，即在
22、循环中使用系列数据加起来，需要重复进行加法操作，即在循环中使用加法操作。加法操作。求和算法可分为如下的三个逻辑部分求和算法可分为如下的三个逻辑部分：将存储和值的变量（将存储和值的变量（sum）初始化。）初始化。循环，在每次迭代中将一个新数加到和（循环，在每次迭代中将一个新数加到和（sum）上。）上。退出循环后返回结果。退出循环后返回结果。求和算法流程图求和算法流程图（2）乘积算法）乘积算法 与求和类似，乘积也是常用算法。例如求整数的阶乘、求与求和类似，乘积也是常用算法。例如求整数的阶乘、求xn。其方法就是在循环中使用乘法操作。其方法就是在循环中使用乘法操作。乘积算法可分为三个逻辑部分：乘积算法
23、可分为三个逻辑部分：将存储乘积值的变量（将存储乘积值的变量（product）初始化。）初始化。循环，在每次迭代中将一个新数与乘积（循环，在每次迭代中将一个新数与乘积（product）相乘。）相乘。退出循环后返回结果。退出循环后返回结果。乘积算法流程图乘积算法流程图（3）求最大值和求最小值算法）求最大值和求最小值算法 有很多问题需要求最大值和最小值。例如大奖赛评分问题，有很多问题需要求最大值和最小值。例如大奖赛评分问题，需要求最高分和最低分。需要求最高分和最低分。其方法就是在循环中使用选择结构，而通过选择结构，可其方法就是在循环中使用选择结构，而通过选择结构，可以找到两个数中的较大值（或较小值）
24、。以找到两个数中的较大值（或较小值）。（3）求最大值和求最小值算法）求最大值和求最小值算法在在n个数中找最大值算法可分为三个逻辑部分：个数中找最大值算法可分为三个逻辑部分：将最大值变量（将最大值变量（max）初始化）初始化:将最大值设为第一个数。将最大值设为第一个数。循环循环n-1次：如果当前数比最大值大，将最大值设为当前数。次：如果当前数比最大值大，将最大值设为当前数。退出循环后返回结果。退出循环后返回结果。在在n个数中找最小值算法可分为三个逻辑部分：个数中找最小值算法可分为三个逻辑部分：将最小值变量（将最小值变量（min）初始化）初始化:将最小值设为第一个数。将最小值设为第一个数。循环循环
25、n-1次：如果当前数比最小值小，将最小值设为当前数。次：如果当前数比最小值小，将最小值设为当前数。退出循环后返回结果。退出循环后返回结果。（4）排序）排序 计算机科学中一个最普遍的应用是排序，即根据数据的值计算机科学中一个最普遍的应用是排序，即根据数据的值对它们进行排列，一个有序的数列更便于查找。对它们进行排列，一个有序的数列更便于查找。排序算法有的比较简单但效率低，如插入排序、选择排序、排序算法有的比较简单但效率低，如插入排序、选择排序、冒泡排序。冒泡排序。有的排序算法效率高，属于高级排序算法，如快速排序、有的排序算法效率高，属于高级排序算法，如快速排序、堆排序、希尔排序、桶式排序、合并排序
26、等。堆排序、希尔排序、桶式排序、合并排序等。插入排序插入排序在插入排序中，排序列表被分为两部分：已排序的和未排在插入排序中，排序列表被分为两部分：已排序的和未排序的。序的。在每次扫描过程中，未排序子列表中的第一个元素被取出在每次扫描过程中，未排序子列表中的第一个元素被取出来，在已排序子列表中找到插入位置，使得插入后的序列来，在已排序子列表中找到插入位置，使得插入后的序列仍然保持按值有序。仍然保持按值有序。具体方法是：待排序的元素，从已排序子列表的末端开始，具体方法是：待排序的元素，从已排序子列表的末端开始，由后向前，依次与已排序子列表中的元素进行比较，直到由后向前，依次与已排序子列表中的元素进
27、行比较，直到找到合适的插入位置。找到合适的插入位置。插入排序示例插入排序示例（5）查找）查找 查找又称为检索，是计算机的最重要的应用之一。所谓查查找又称为检索，是计算机的最重要的应用之一。所谓查找就是在列表中确定目标所在位置的算法。找就是在列表中确定目标所在位置的算法。对于列表有两种基本的查找方法：对于列表有两种基本的查找方法：顺序查找和折半查找。顺序查找和折半查找。顺序查找可以在任何列表中查找，折半查找则要求列表的顺序查找可以在任何列表中查找，折半查找则要求列表的数据元素是有序的。数据元素是有序的。查找查找u 顺序查找顺序查找 顺序查找又称线性查找。顺序查找的过程是：对给定的目顺序查找又称线
28、性查找。顺序查找的过程是：对给定的目标元素，从列表的一端开始，逐个与目标元素比较，直到找到标元素，从列表的一端开始，逐个与目标元素比较，直到找到或到达表尾时结束。或到达表尾时结束。u折半查找折半查找 如果列表很大，高效的查找方法是首先把列表排序，然后采如果列表很大，高效的查找方法是首先把列表排序，然后采用折半查找的方法。用折半查找的方法。折半查找是从一个列表的中间元素开始测试，判断要找的折半查找是从一个列表的中间元素开始测试，判断要找的元素是在列表的前半部分还是后半部分，以便在缩小列表的一元素是在列表的前半部分还是后半部分，以便在缩小列表的一半范围内查找，提高了查找效率。半范围内查找，提高了查
29、找效率。重复这个过程直到找到目标或目标不在这个列表里，查找结重复这个过程直到找到目标或目标不在这个列表里，查找结束。束。折半查找折半查找n比较次数顺序查找顺序查找折半查找折半查找算法设计非常重要！算法设计非常重要！时间复杂度时间复杂度顺序顺序查找：查找：T(n)=O(n)折半折半查找：查找：T(n)=O(Log2n)2.穷举法穷举法算法算法 穷举法也叫枚举法，它的基本思想是：穷举法也叫枚举法，它的基本思想是：根据题目的部分条件确定答案的大致范围，然后在此范围根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。内对所有可能的情况逐一验证，直到所有
30、情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。情况验证完后均不符合题目的条件，则问题无解。特点特点:算法简单，容易理解，运算量大。算法简单，容易理解，运算量大。穷举法（枚举法）穷举法（枚举法）如：百元买百鸡问题。假定小鸡每只如：百元买百鸡问题。假定小鸡每只0.50.5元，公元，公鸡每只鸡每只2 2元，母鸡每只元，母鸡每只3 3元。现在有元。现在有100100元钱要求买元钱要求买100100只鸡，问共有几种购鸡方案？只鸡，问共有几种购鸡方案？根据题目，设母鸡、公鸡、小鸡各为根据题目，
31、设母鸡、公鸡、小鸡各为x,y,zx,y,z只，列只，列出方程为：出方程为：x+y+z=100 x+y+z=100，3x+2y+0.5z=1003x+2y+0.5z=100 利用穷举法，将各种可能的组合一一测试，输出利用穷举法，将各种可能的组合一一测试，输出符合条件的组合。即在各个变量的取值范围内不断变符合条件的组合。即在各个变量的取值范围内不断变化化x,y,zx,y,z的值，穷举的值，穷举x,y,zx,y,z全部可能的组合，若满足方全部可能的组合，若满足方程组则是一组解。程组则是一组解。伪代码如下伪代码如下:Exhaustion()x0 while(x=33)y0 while(y=50)z10
32、0-x-y if(3*x+2*y+0.5*z)=100)print x y z yy+1 xx+1 穷举法：穷举法：百元买百鸡问题#include stdio.h#include stdio.hmain()main()int x,y,z;int x,y,z;printf(printf(母鸡母鸡 公鸡公鸡 小鸡小鸡););for(x=0;x=33;x+)for(x=0;x=33;x+)for(y=0;y=50;y+)for(y=0;y=1)xn-1(xn+1)*2;xnxn-1 print xn-1 /*第 i天的桃子数*/ii-1#include stdio.h#include stdio.h
33、main()main()int i,x;int i,x;x=1;x=1;printf(printf(第第 7 7 天的桃子数为：天的桃子数为：1 1只只n);n);for(i=6;i=1;i-)for(i=6;i=1;i-)x=(x+1)x=(x+1)*2;2;printf(printf(第第%d%d 天的桃子数为：天的桃子数为：%d%d只只,i,x);,i,x);printf(n);printf(n);猴子吃桃子猴子吃桃子C语言程序：语言程序：4.4.递归法递归法 递归是算法递归是算法自我调用自我调用的过程，将问题逐层分解，将复杂的过程，将问题逐层分解，将复杂问题归结为一些最简单的问题进行处
34、理，然后再沿着分解的问题归结为一些最简单的问题进行处理，然后再沿着分解的逆过程逐步进行综合。逆过程逐步进行综合。如如根据求根据求n!n!的定义的定义n!=n(n-1)!n!=n(n-1)!，进行求解。该定义可给，进行求解。该定义可给出具体形式如下出具体形式如下:1 (n=0,1)1 (n=0,1)n!=n!=n(n-1)n(n-1)！(n1)(n1)从求从求n!n!逐层递推为求逐层递推为求(n-1)!(n-1)!，求，求(n-2)!.(n-2)!.最后成为求最后成为求1!1!这个这个简单问题，再沿着原来分解地逆过程逐层相乘进行回归，得简单问题，再沿着原来分解地逆过程逐层相乘进行回归，得出结果。
35、出结果。递归求阶乘（3！）的过程阶乘递归算法的伪代码阶乘递归算法的伪代码Factorial(n)if(n=0)|(n=1)return 1 else return n*Factorial(n-1)递归法与迭代法的对比阶乘递归算法的伪代码阶乘递归算法的伪代码Factorial(n)if(n=0)|(n=1)return 1 else return n*Factorial(n-1)阶乘迭代算法的伪代码阶乘迭代算法的伪代码Factorial(n)F=1 i=1 while(iBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历:二叉树的遍历ADBCL D RBL D RL D RADC
36、L D R中序遍历序列：中序遍历序列：B D A C中序遍历:二叉树的遍历ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C A后序遍历:B二叉树的遍历二叉树的遍历二叉树的遍历DLR:ABCDEFLDR:CBEDFALRD:CEFDBAFBADCE中中序遍历序遍历序列：序列：C B ED F AABCDEF结束结束图图是一种比线性表和树更为复杂的非线性数据是一种比线性表和树更为复杂的非线性数据结构，图中任意两个数据元素之间都可能相关结构，图中任意两个数据元素之间都可能相关。图在。图在实际中有广泛的应用，在数学、化学、实际中有广泛的应用，在数学、化学、
37、物理、工程和计算机科学中有大量使用图来表物理、工程和计算机科学中有大量使用图来表示的关系。示的关系。例如，著名的格尼斯堡例如，著名的格尼斯堡“七桥七桥”问题就是将连接两个岛屿和陆问题就是将连接两个岛屿和陆地的七座桥的地图抽象为点与线连接的图，将如何判断不重复地的七座桥的地图抽象为点与线连接的图，将如何判断不重复走遍所有道路的问题转换为图的形式的数学问题进行处理走遍所有道路的问题转换为图的形式的数学问题进行处理。又如，最优邮递路线问题也是采用图的方式进行处理。一个邮又如，最优邮递路线问题也是采用图的方式进行处理。一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，递员从邮局出发，到所管辖
38、的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短线使所走的路程最短。在计算机网络中的搜索引擎通常采用网络爬虫，爬虫所走的路在计算机网络中的搜索引擎通常采用网络爬虫，爬虫所走的路线是在网络中的各网站进行搜索，也是要考虑经过的路线问题。线是在网络中的各网站进行搜索，也是要考虑经过的路线问题。5.5.图形结构图形结构6.4.1 6.4.1 问题的描述与抽象问题的描述与抽象6.4 6.4 问题求解问题求解-基于计算机的问题求解策略要借助于计算机解决问题，必须要对问题进行清晰的描述要借助于计算机解
39、决问题，必须要对问题进行清晰的描述和抽象。和抽象。在在现实生活中，有不少问题可以利用图形化方法进行抽象，现实生活中，有不少问题可以利用图形化方法进行抽象，把实际问题抽象成数学问题，从而利用数学方法解决实际问把实际问题抽象成数学问题，从而利用数学方法解决实际问题题.欧拉解决哥尼斯堡七桥问题就是应用图形化方法的典型范欧拉解决哥尼斯堡七桥问题就是应用图形化方法的典型范例例.BDACABCD6.4.1 6.4.1 问题的描述与抽象问题的描述与抽象6.4 6.4 问题求解问题求解-基于计算机的问题求解策略著名的四色定理的证明也是典型的抽象例子。著名的四色定理的证明也是典型的抽象例子。即即“每幅地图都可以
40、用每幅地图都可以用4种颜色着色，使得相邻的国家或行政区不种颜色着色，使得相邻的国家或行政区不重色重色”。四色问题用地图表示现实中的不同区域，忽略区域中的。四色问题用地图表示现实中的不同区域，忽略区域中的人、物、房屋、道路等因素，得到只有区域边界的地图，然后对人、物、房屋、道路等因素，得到只有区域边界的地图，然后对地图再进行抽象，用圆圈表示区域，用线表示区域之间的相邻关地图再进行抽象，用圆圈表示区域，用线表示区域之间的相邻关系，就得到了问题的图形表示。系，就得到了问题的图形表示。6.4.1 6.4.1 问题的描述与抽象问题的描述与抽象6.4 6.4 问题求解问题求解-基于计算机的问题求解策略 在
41、在现实生活中，有不少问题可以利用方程化函数化的数学方现实生活中，有不少问题可以利用方程化函数化的数学方法进行抽象，然后通过方程组或函数图来解决实际问题法进行抽象，然后通过方程组或函数图来解决实际问题.例如，假定小鸡每只0.5元，公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，问共有几种购鸡方案？分析：根据题目，设母鸡、公鸡、小鸡各为x,y,z只，列出方程为：x+y+z=100 3x+2y+0.5z=1006.4.2 6.4.2 基于程序设计的问题求解基于程序设计的问题求解6.4 6.4 问题求解问题求解-基于计算机的问题求解策略 求三角形面积为例，介绍基于程序设计求解问题的一般求
42、三角形面积为例，介绍基于程序设计求解问题的一般过程。过程。例：例：编写程序计算三角形面积。要求先输入三条边的长度，编写程序计算三角形面积。要求先输入三条边的长度，然后求由这三条边所构成的三角形的面积。然后求由这三条边所构成的三角形的面积。6.4.2 6.4.2 基于程序设计的问题求解基于程序设计的问题求解（1）问题分析）问题分析 根据题意分析，采用计算三角形面积公式进行计算，计算过根据题意分析，采用计算三角形面积公式进行计算，计算过程中要求程序中输入三条边的值。设程中要求程序中输入三条边的值。设a，b，c为任意三角形的三为任意三角形的三条边，条边，d为三角形周长的一半。为三角形周长的一半。（2
43、）确定数学模型）确定数学模型 采用计算三角形面积公式，即可得到计算的数学模型。采用计算三角形面积公式，即可得到计算的数学模型。d=(a+b+c)/2（3）算法描述（自然语言描述）算法描述（自然语言描述）S1：输入三条边长度：输入三条边长度a，b，c；S2：判断三条边长度是否均大于零。是，则执行：判断三条边长度是否均大于零。是，则执行S3，否则执行，否则执行S6；S3：判断是否两边之和大于第三边。是，则执行：判断是否两边之和大于第三边。是，则执行S4，否则执行，否则执行S6；S4：根据公式求三角形面积：根据公式求三角形面积S；S5：输出三角形面积，转：输出三角形面积，转S7；S6：打印：打印“无
44、解无解”；S7：结束。：结束。（4）编写程序）编写程序 采用采用C语言编写的程序语言编写的程序#include#include int main()int a,b,c;double d,area;scanf(%d%d%d,&a,&b,&c);d=(a+b+c)/2.0;area=sqrt(d*(d-a)*(d-b)*(d-c);printf(area=%6.2f,area);return 0；（5）调试运行程序）调试运行程序 在在VC+6.0环境输入程序，编译源程序，修改语法错误，连环境输入程序，编译源程序，修改语法错误，连接并运行程序，输入接并运行程序，输入a,b,c三条边的值，检查程序结果
45、是否正三条边的值，检查程序结果是否正确，不正确，修改源程序，再进行编译、连接、运行，结果正确，不正确，修改源程序，再进行编译、连接、运行，结果正确，结束程序运行。确，结束程序运行。程序设计的步骤程序设计的步骤 分析问题，建立数学模型分析问题，建立数学模型 确定数据结构确定数据结构 确定算法，描述算法确定算法，描述算法 编制程序，调试程序编制程序，调试程序 运行结果运行结果xnns16.4.3 6.4.3 程序设计方法程序设计方法1 1结构化程序设计结构化程序设计结构化程序设计方法的主要原则可以概括为结构化程序设计方法的主要原则可以概括为:自顶向下，逐步自顶向下，逐步求精，模块化，限制使用求精，
46、模块化，限制使用goto语句。语句。自顶向下:程序设计时，应先考虑总体，后考虑细节;先考虑全局目标，后考虑局部目标。避免一开始就过多的考虑细节，应先从顶层开始设计，逐步使问题具体化。逐步求精:对复杂问题，应确定一些子目标作为过渡，然后逐步细化。模块化:一个复杂问题，一定是由若干稍简单的问题组成。模块化是把程序要解决的总目标分解成为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。限制使用GOTO语句。6.4.3 6.4.3 程序设计方法程序设计方法2 2面向对象程序设计面向对象程序设计用面向对象的方法解决问题，是将问题分解为对象。将对象的属性和方法封装成一个整体称为类，通过发消息来
47、实现对象之间的相互联系和作用。面向对象的程序设计方法日益受到人们的重视和使用，成为流行的软件开发方法，源于面向对象方法有以下突出的优点：与人们习惯的思维方法一致，便于解决复杂问题。软件的可维护性好。可重用性好，能用继承的方式缩短程序开发所花的时间。稳定性好，易修改。可视化可视化 基于流程图基于流程图 无需编程无需编程 算法设计和运行验证算法设计和运行验证 可生成可生成c+c+、JavaJava等等高级语言代码高级语言代码 可导出流程图可导出流程图 初学者的好帮手初学者的好帮手95RAPTOR（the Rapid Algorithmic Prototyping Tool for Ordered
48、Reasoning-用于有序推理的用于有序推理的快速算法原型工具）快速算法原型工具）6.5 Raptor可视化工具96Raptor语句/符号初始界面初始界面6种Raptor基本符号运行逐句运行RaptorRaptor只支持只支持英文字符，不支英文字符，不支持中文字符持中文字符程序由Start模块开始运行至End模块结束 作用是为一个变量赋一个特定作用是为一个变量赋一个特定值或将变量值改为一个新的值值或将变量值改为一个新的值 图例是一个矩形，内有赋值语图例是一个矩形，内有赋值语句，语法为句，语法为VariableVariable Expression Expression 97Raptor语句/
49、符号赋值（赋值（AssignmentAssignment）语句语句/符号符号对变量进行赋值，可以对变量进行赋值，可以是数值也可以是公式是数值也可以是公式 作用是将用户输入的数据赋作用是将用户输入的数据赋值给变量值给变量 图例是一个平行四边形，在图例是一个平行四边形，在左边有一个指向其的箭头左边有一个指向其的箭头 形内是将要接收用户输入值形内是将要接收用户输入值的变量的变量98Raptor语句/符号输入（输入（InputInput）语句语句/符号符号输入提示文本时要加双输入提示文本时要加双引号，提示信息中的变引号，提示信息中的变量不需要加引号，文本量不需要加引号，文本和变量可以用和变量可以用+连
50、接连接99Raptor语句/符号调用调用（CallCall）语句）语句/符符号号既可以调用个人创建的子既可以调用个人创建的子图（图（subchartsubchart），也可以），也可以对对RaptorRaptor自自带的过程带的过程（procedureprocedure）进行调用）进行调用100Raptor语句/符号输出（输出（OutputOutput）语句语句/符号符号输出时，文本要加双引输出时，文本要加双引号（输出结果中不显示号（输出结果中不显示引号），输出变量不需引号），输出变量不需要加引号，文本和变量要加引号，文本和变量可以用可以用+连接连接101顺序控制语句（Sequence）按从上
