新编计算机导论 课件 5-问题求解-问题求解思想

新编计算机导论问题求解问题求解思想01算法的描述03算法基础02算法的评价05本章CAPACITY内容2算法与程序设计04常用算法061.问题求解思想3普适的问题求解第一步，理解问题明确未知量、数据、条件是什么？条件有可能满足吗？条件是否足以决定未知量？引入符号、把条件分割为多个部分，以图形或文字的形式进行描述第二步，设计方案考虑以前是否见过此问题，或者是否见过形式稍有不同的同类问题？第三步，执行方案第四步，分析方案著名数学家GeorgePolya在其经典著作《HowtoSolveIt:ANewAspectofMathematicalMethod》一书中描述了通用的问题求解策略，并将问题的求解过程概括为以下四个步骤

波利亚（1887-1985），美籍匈牙利人，著名数学家、教育家，法国科学院、美国国家科学院和匈牙利科学院院士，以他的名字命名的波利亚计数定理是近代组合数学的重要工具，1963年获美国数学协会(MAA）数学杰出贡献奖。4计算机问题求解分析和说明阶段此阶段输出的是关于问题的清晰描述算法开发阶段输出上一阶段定义的问题的通用解决方案实现和维护阶段输出的是可以在计算机上运行的程序，即“算法”的实现计算机求解问题的过程可分为三个阶段若在程序运行过程中出现了错误，或需要修改程序，则需重复上述工作，直至得到正确的结果1.问题求解思想5问题转换为方案的两种方法此方法把问题分解为若干易于处理的子问题，然后再把子问题进一步分解为子问题（称为模块），直到不再需要进一步分解为止。分析问题编写主要模块编写其它模块根据需要进行调整或修改自顶向下设计面向对象设计用被称为对象的独立实体生成解决方案，对象由数据和处理数据的操作构成此方法的设计重点是对象及其在问题中的交互作用，一旦收集到问题中的所有对象，就能构成问题的解决方案1.问题求解思想例1：输入某个班级全体学生的成绩，计算学生平均成绩并输出结果输入成绩计算平均成绩输出平均成绩6问题可分解为三部分计算并输出全班平均成绩输入各学生成绩计算平均成绩计算每个学生平均成绩计算全班各门课平均成绩输出全班平均成绩输出每个学生平均成绩输出各科平均成绩1.问题求解思想2.算法基础7算法的定义操作算术运算：加、减、乘、除等关系运算：大于、小于、等于…逻辑运算：与、或、非等其他运算：输入、输出、赋值等计算机算法是指一个能够被计算机处理的，有限长的操作序列算法由操作、控制结构、数据结构三要素组成控制结构顺序结构选择结构循环结构数据结构算法的处理对象是数据，数据之间的逻辑关系、数据的存储与处理方式就是数据结构常见的数据结构有：线性、树状、网状/图结构实例8割圆术计算圆周率对于某个圆形，寻找一个内接正3×2n（n为整数）边形判断该多边形和圆之间的面积是否充分接近于0；如果是，则利用内接正多边形的边长和面积值计算圆周率；否则，增加内接正多边形的边数，重复上述过程，直至内接正多边形和圆重合魏晋时期数学家刘徽发明，即用圆的内接正多边形的面积去无限逼近圆面积并以此计算圆周率，算法可简单描述为刘徽首先计算了圆的内接正192边形的周长和面积，得出圆周率为3.14，后又计算到了正3072边形，得出圆周率为3.14162.算法基础9算法的特征确定性—要求算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的，只要输入数据和初始状态相同，则无论执行多少遍，每次的结果都相同。有穷性—指算法应包含有限的操作步骤，在有限的时间内完成，而不能是无限的。输入—所谓输入是指算法在执行时需要从外界取得的必要信息，一个算法有0或多个输入。输出—算法的目的是为了求解，“解”就是输出，一个算法需有一个或多个输出。输出与输入有关，不同的输入会对应不同结果的输出，没有输出的算法是没有意义的。可行性—算法中的每一个步骤都应当通过有限次基本运算实现，即算法中的每一步操作计算机都可以执行。算法和程序设计技术的先驱、图灵奖获得者唐纳德.E.克努斯在其经典巨著《TheArtofComputerProgramming》中对算法的特征给出了如下描述：DonaldErvinKnuth（1938-），中文名高德纳，美国计算机科学家，算法和程序设计技术的先驱者，所著多本巨著被认为与欧几里得、牛顿、狄拉克等经典巨著相比肩。3.算法的描述10算法的描述方式有以下几种自然语言流程图伪代码程序语音自然语言用自然语言表示通俗易懂，但文字冗长，容易出现歧义用自然语言描述包含分支和循环的算法，不很方便除了很简单的问题外，一般不用自然语言11比如：求一元二次方程的根；“张先生对李先生说他的孩子考上了大学”3.算法的描述流程图流程图就是以特定的图形符号加上说明，用来表示算法的图，也称框图12起止框输入输出框处理框判断框流程线连接点注释框3.算法的描述131ii>50开始i+1i结束NY输入ni、gi1i开始gi≧80输出ni、gii+1ii>50NYYN如果包括输入数据部分①有50个学生，要求将成绩在80分以上的学生的学号和成绩输出例：141ii>50开始i+1i结束NY输入ni、gi1igi≧80输出ni、gii+1ii>50NYYN如果包括输入数据部分①①伪代码用介于自然语言和计算机语言之间的文字和符号来描述算法不拘泥于具体的编程语言，无需固定的、严格的语法规则具有结构清晰，表述简单，可行性好等优点15例：用伪代码描述日程安排If

9点以前

then处理私人事务；If

9点到18点

then工作；Else下班；End

If3.算法的描述4.算法与程序设计算法与程序分析问题并建立问题处理的数学模型；考虑待处理数据的组织及存储形式，设计合适的算法；选取某种程序设计语言来实现算法；上机调试程序并验证结果计算机的一切操作都是由程序控制的，离开程序，计算机将一事无成算法是程序的核心，程序是用某种计算机程序设计语言对某一算法的具体实现程序设计是沟通算法与计算机的桥梁，其基本目标是应用算法对问题的原始数据进行处理，以解决问题并获得期望的结果，该过程大致包含以下步骤164.算法与程序设计计算机科学界的著名公式数据结构+算法=程序算法相当于解决某一类问题的公式与思想数据结构就是数据的表示程序则是计算机处理问题的一系列指令图灵奖获得者，Pascal语言之父尼古拉斯•沃斯（NiklausWirth）提出17

尼古拉斯·沃斯（NiklausWirth，1934-），瑞士计算机科学家。创建与实现了当时世界上最受欢迎的语言之一Pascal语言，提出了“结构化程序设计(structureprogramming)”的概念。4.算法与程序设计算法的控制结构顺序结构就是按照操作的先后顺序，从头到尾逐条顺序地执行；分支结构也称选择结构，包括简单分支结构和多分支结构，此种结构可以根据给定条件满足与否而选择执行不同的操作；循环又称重复，它根据给定条件的满足与否来判断是否需要重复执行某一段程序无论规模如何，算法中的操作步骤都是基于顺序、分支和循环三种控制结构来执行1819AB4.算法与程序设计顺序结构20ABYpNAYpN4.算法与程序设计选择结构（a）（b）21AYp1NYx<5N0x输出x的值x+1x输出0,1,2,3,44.算法与程序设计当型循环结构22AYp2NYx≧5N0x输出x的值x+1x输出1,2,3,4,54.算法与程序设计直到型循环结构235.算法的评价算法的正确性算法的正确性指算法能正确完成所要求解的问题，就目前的研究来看，要想通过理论方式证明一个算法的正确性是非常复杂和困难的，一般采用测试的方法结构内不存在“死循环”常用的方法是选定一些有代表性的输入数据进行测试经过一定范围的测试和程序改正，不再发现新的错误后，程序就可以交付使用245.算法的评价算法的复杂度算法复杂度的高低主要体现在算法运行所需占用的时间和空间资源的多少方面，包含时间复杂度和空间复杂度在对算法的复杂度进行分析时，对时间复杂度的分析考虑得更多算法的时间复杂度指依据算法编写出程序后在计算机上运行时所耗费的时间度量空间复杂度指依据算法编写出程序后在计算机上运行时所需内存空间大小的度量二者都和问题规模n有关255.算法的评价算法的时间复杂度在分析算法的时间复杂度时，不是分析算法对应程序的具体执行时间，而是抛开计算机软硬件环境，分析算法相对于问题规模n所耗费时间的数量级具体是以算法中基本运算的执行次数来度量计算工作量基本运算反映了算法运算的主要特征算法耗费的时间与算法中的基本运算执行次数成正比比如，汉诺塔问题中的基本运算是盘子的移动，排序问题中的基本运算是数据间的比较265.算法的评价算法时间复杂度的表示算法复杂度分析中常用的一种方法是大O记法，其中O是英文单词Order（数量级）的首字母，表示当问题规模n充分大时，该程序运行时间的一个数量级设f(n)和g(n)是表示与问题规模n相关的计算量的函数，两个函数f(n)和g(n)在大O概念上相同，是指当n趋近于无穷大时，它们的比值只差一个常数比如f(n)=n*logn，g(n)=100*n*logn，二者被视为