第5章问题求解与算法scx

第5章问题求解与算法5.15.2计算思维算法2Contents目录5.1计算思维“计算思维是运用计算科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动”，“其本质就是抽象与自动化，即在不同层面进行抽象，以及将这些抽象机器化”。计算思维（设计与构造）、理论思维（推理与演绎）和实验思维（观察与总结）称为三大思维。4计算思维1哥斯堡七桥问题“寻找走遍这7座桥且只许走过每座桥一次最后又回到原出发点的路径”5计算思维2计算思维的特征①计算思维是人类求解问题的一条途径。②计算思维的过程可以由人执行也可以由计算机执行。③计算思维是思想。④计算思维是概念化，不是程序化。计算思维在计算机学科中的体现①“0和1”的思维。②“指令”与“程序”的思维。③“递归”的思维。6计算思维特征冯·诺依曼计算机体现了存储程序与程序自动执行的基本思维，实现了在存储体系环境下，程序在操作系统管理下的执行的基本思维。并行与分布计算环境应用于局域网/广域网的计算系统的构建，体现了在复杂环境程序如何被硬件并行、分布执行的思维。云计算环境实现了由高性能计算结点和大容量磁盘存储结点结合，体现是计算资源虚拟化服务化的思维。7计算系统发展中的进化思维其它学科均可应用计算手段进行学科问题的研究和创新。学科融合是计算思维带给广泛的学科问题求解的一种思想、策略、方法和手段上的变化，为科学研究和科学应用提供新的思路、方法和技术，融合正在促进各学科的突破性发展。思维是由一系列知识所构成的完整的解决问题的思路，其每个环节都需要知识的铺垫，基于一定的知识可理解每一个环节，通过“贯通”各个环节进而解决问题。计算思维是学科的灵魂、学科的重要思想，计算思维对各学科专业的影响是深远的。8计算思维对其他学科的影响5.2算法概念指解题方案准确而完整的描述，是一系列解决问题的方法步骤或清晰指令的陈述。代表着用系统的方法描述解决问题的策略机制。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。要素：由操作与控制结构两个要素组成。性质：确定性、可实现性、具有数据输入、具有数据输出、有穷性描述方法有如：自然语言、流程图、伪代码和计算机语言。10算法1步骤描述法，即用人们日常使用的语言和数学语言描述算法的步骤。例如：sum=1+2+3+4+…+n求和问题的算法描述Startofthealgorithm(算法开始)(1)输入N的值；(2)设i的值为1；sum的值为0；(3)如果i=N，则执行第(4)步，否则转到第(7)步执行；(4)计算sum+i，并将结果赋给sum；(5)计算i+1，并将结果赋给i;(6)返回到第3步继续执行；(7)输出sum的结果。Endofthealgorithm(算法结束)1.自然语言(步骤描述法)自然语言表示的算法容易出现二义性、不确定性等问题算法描述流程图的基本表示符号矩形框：表示一组顺序执行的规则或者程序语句。菱形框：表示条件判断，并根据判断结果执行不同的分支。圆形框：表示算法或程序的开始或结束。箭头线：表示算法或程序的走向。矩形框表示一组顺序执行的语句菱形框表示判断语句，决定下一步程序的走向圆形框表示程序的起始和结束带箭头的线段表示程序的走向开始以n除m，并令所得余数为rr=0?输出n将n置换为m，r置换为n结束是2.程序流程图三种控制结构的流程图表示方法示意开始第1条规则或语句第n条规则或语句结束顺序结构的流程图开始条件成立否？是否条件成立时执行的规则或语句结束条件不成立时执行的规则或语句分支结构的流程图循环结构的流程图初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句。即：循环体结束是否循环结束3.伪代码4.计算机语言也叫枚举法，就是通过把需要解决问题的所有可能情况逐一试验来找出符合条件的解的方法。基本思想是按照问题要求确定问题解的大致范围，然后在此范围内对这些可能解列举，再判断所列举的可能问题解满足不满足问题的要求，直到所有可能解列举完毕。在实际生活中，只有很少的一些问题是真正意义上的“毫无规律”，大多数仍有内在规律可循，所以使用穷举法在效率上就显得比较低下。如求100以内的素数，需逐个判断。15穷举法使一组数据，按照其中的某个或某些关键字的大小，按递增或递减的顺序排列起来的操作。在大量数据的处理方面，一个优秀的算法可以节省大量的资源。①直接插入排序将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列有序为止。16排序算法1②希尔排序先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。17排序算法2[初始关键字]：4939669875122849560449123928664998567504一趟排序结果1228495604493966987512563975280466494998二趟排序结果12044939284966569875三趟排序结果04122839494956667598③简单选择排序在要排序的一组数中，选出最小（大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（大）的与第2个位置的数交换，依次类推，直到第n-1个元素和第n个元素比较为止。18排序算法3初始值：49396698751228495604第1趟：04396698751228495649第2趟：04126698753928495649第3趟：04122898753966495649第4趟：04122839759866495649第5趟：04122839499866755649第6趟：04122839494966755698第7趟：04122839494956756698第8趟：04122839494956667598第9趟：04122839494956667598④冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻两数进行比较，每当两相邻数比较后发现顺序与要求相反时，互换两数。19排序算法4[初始关键字]：49396698751228560449第一趟排序后39496675122856044998第二趟排序后394966122856044975第三趟排序后3949122856044966第四趟排序后39122849044956第五趟排序后122839044949第六趟排序后1228043949第七趟排序后12042839第八趟排序后041228递归算法是一种直接或者间接地调用自身算法的过程。特点：①递归就是在过程或函数里调用自身。②在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。③递归算法解题虽然很简洁，但解题的运行效率较低。所以一般不提倡用递归算法设计程序。④在递归调用的过程当中，系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以在实际编程中要注意栈溢出问题。20递归算法1斐波那契数列1,1,2,3,5,8,13,21,34,55,89,144,…特别指出：第0项是1，第1项是1。这个数列从第二项开始，每一项都等于前两项之和。斐波那契数列递归法实现：21递归算法2F(n)=1𝑛=11𝑛=2𝐹𝑛−1+𝐹𝑛−2𝑛≥3一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。是序列计算中的一种常用算法。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复。递推法的解题步骤：①按次序研究集合中最初最原始的若干问题。②按次序寻求集合中问题间的转换规律即递推关系，使问题逐次转化成较低层级或简单的且能解决问题的或已解决的问题。22递推算法1斐波那契数列1,1,2,3,5,8,13,21,34,55,89,144,…特别指出：第0项是1，第1项是1。这个数列从第二项开始，每一项都等于前两项之和。斐波那契数列递推算法实现：F(0)=1;F(1)=1;F(2)=F(0)+F(1)=2;F(3)=F(1)+F(2)=3;F(4)=F(2)+F(3)=5;……F(n)=F(n-1)+F(n-2)23递推算法2利用计算机的高性能来穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索算法提供一种数据模型技术，并在此基础上进行优化改造，从而实现具有特色的个性化搜索功能。(1)暴力搜索暴力搜索有称为枚举法，指的是从可能的解集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的，能使命题成立，即为其解。注意：仅当问题的所有可能解不太多的时候，才可以使用枚举法。24搜索算法1(2)二分搜索又称折半查找，它是种效率较高的查找方法。要求：线性表是有序表，即表中结点接关键字有序，并且要用向量作为表的存储结构。基本思想：（设R[low,high]是当前的查找区间）确定该区间的中点：mid=⌊(low+high)/2⌋待查K值=R[mid]，则查找成功返回此位置，若R[mid].keyK，则新的查找区间是[low,mid]若R[mid].keyK，则新的查找区间为[mid,high]下一次查找是针对新的查找区间进行的。过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空（即查找失败）时为止。25搜索算法25.高级问题初探:算法分析与计算复杂性5.2算法的计算时间有多长?算法分析与计算复杂性算法复杂性分析示例sum=0；（1次）for(i=1;i=n;i++)（n次）{for(j=1;j=n;j++)（n2次）{sum++；}（n2次）}解：T(n)=2n2+n+1=O(n2)主要关注点：循环的层数