算法设计与分析部分算法伪代码
第三章蛮力法
1.选择排序
?SelectionSort(A[0..n-1])
for i=0 to n-2 do
min=i
for j=i+1 to n-1 do
if A[j] min=j swap A[i] and A[min] 2.冒泡排序 ?BubbleSort(A[0..n-1]) // 输入：数组A，数组中的元素属于某偏序集 // 输出：按升序排列的数组A for i=0 to n-2 do for j=0 to n-2-i do if A[j+1] 3.改进的冒泡算法 ?ALGORITHM BubbleSortImproved( A[0,…,n – 1] ) // 冒泡排序算法的改进 // 输入：数组A，数组中的元素属于某偏序集 // 输出：按升序排列的数组A for i ←0 to n – 2 do flag ←True for j ←0 to n – 2 – i do if A[j+1] < A[j] swap(A[j], A[j+1]) flag ←False // 如果在某一轮的比较中没有交换，则flag为True，算法结束 if flag = True return 4.顺序查找算法 算法SwquentialSearch2(A[0...n],k) //顺序查找算法的实现，它用了查找键来作限位器 //输入：一个n个元素的数组A和一个查找键K //输出：第一个值等于K的元素的位置，如果找不到这样的元素就返回-1 A[n]<--k i<--0 while A[i]!=K do i<--i+1 if i Else return -1 5.蛮力字符串匹配 算法BruteForceStringMatch(T[0...n-1],P[0...m-1]) //该算法实现了蛮力字符串匹配 //输入：一个n个字符的数组T[0...n-1]代表一段文本 // 一个m个字符的数组P[0..m-1]代表一个模式 //输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置，// 否则返回-1 For i<--0 to n-m do j<--0 While j j<--i+1 If j=m return i return -1 ?合并排序最差Θ(nlog2n) ?快速排序最优Θ(nlog2n) 最差Θ(n2) 平均Θ(1.38nlog2n) ?选择排序Θ(n2) ?冒泡排序Θ(n2) ?插入排序最差Θ(n2) ?最优Θ(n) ?平均Θ(n2) 第四章分治法 合并排序 算法MergeSort(A[0..n-1] ) // 递归调用mergesort来对数组A[0...n-1] 排序 // 输入：一个可排序数组A[0..n-1] // 输出：非降序排列的数组A[0..n-1] if n > 1 copy A[0..?n/2?-1] to B[0..?n/2?-1] copy A[?n/2?..n-1] to C[0..?n/2?-1] MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 两个数组合并的算法 算法Merge(B[0..p-1],C[0..q-1],A[0..p+q-1]) //将两个有序数组合并成一个有序的数组 //输入：两个有序数组B[0...p-1]和C[0...q-1] //输出：A[0..p+q-1]中已经有序存放了B和C中的元素 i=0,j=0,k=0; while i if B[i]≤C[j] A[k]=B[i], i=i+1 else A[k]=C[j], j=j+1 k=k+1 if i=p copy C[j..q-1] to A[k..p+q-1] else copy B[i..p-1] to A[0..p+q-1] 快速排序算法 QuickSort(A[l..r]) // 使用快速排序法对序列或者子序列排序 // 输入：子序列A[l..r]或者序列本身A[0..n-1] // 输出：非递减序列A if l < r s ←Partition( A[l..r] ) QuickSort( A[l..s-1] ) QuickSort( A[s+1..r] ) //s是中轴元素/基准点，是数组分区位置的标志 实现分区的算法 Partition( A[l..r] ) // 输入：子数组A[l..r] // 输出：分裂点/基准点pivot的位置 p ←A[l]i ←l; j ←r+1 repeat repeat i ←i + 1until A[i] ≥p repeat j ←j –1 until A[j] ≤p swap( A[i], A[j] ) until i ≥j swap( A[i], A[j] ) swap( A[l], A[j] ) return j 折半查找 BinarySearch( A[0..n-1], k ) // 输入：已排序大小为n的序列A，待搜索对象k // 输出：如果搜索成功，则返回k的位置，否则返回-1 l=0,r=n-1; While l≤r mid= ?(l+r)/2? if k = A[mid] return mid else if k < A[mid] r=m-1 else l=m+1 return -1 Strassen矩阵 ?Strassen方法 M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12) 第五章减治法 插入排序 ?ALGORITHM InsertionSort( A[0..n-1] ) // 对给定序列进行直接插入排序 // 输入：大小为n的无序序列A // 输出：按非递减排列的序列A for i ←1 to n-1 do temp ←A[i] j ←i-1 while j ≥0 and A[j] > temp do A[j+1] ←A[j] j ←j –1 A[j+1] ←temp 深度优先查找 算法BFS（G） //实现给定图的深度优先查找遍历 //输入：图G= //输出：图G的顶点，按照被DFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问” count =0//记录这是第几个访问的节点 mark each vertex with 0//标记为unvisited for each vertex v∈V do if v is marked with 0 dfs(v) dfs(v) //递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值 //根据遇到它们的先后顺序，给它们附上相应的数字 count = count + 1 mark v with count for each vertex w adjacent to v do if w is marked with 0 dfs(w) 广度优先 BFS(G) /实现给定图的深度优先查找遍历 //输入：图G= //输出：图G的顶点，按照被BFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问” count =0 mark each vertex with 0 for each vertex v∈V do bfs(v) bfs(v) //递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值 //根据遇到它们的先后顺序，给它们附上相应的数字 count = count + 1 mark v with count initialize queue with v while queue is not empty do a = front of queue for each vertex w adjacent to a do if w is marked with 0 count = count + 1 mark w with count add w to the end of the queue remove a from the front of the queue 拓扑排序 第六章变治法 Gauss消去法 ?GaussElimination(A[1..n], b[1..n]) // 输入：系数矩阵A及常数项b // 输出：方程组的增广矩阵等价的上三角矩阵 for i=1 to n do A[i][n+1] =b[i] for j= i+1 to n do for k = i to n+1 do A[j][k] = A[j][k] – A[i][k]*A[j][i]/A[i][i] 堆排序 ?堆排序主要包括两个步骤： ?对于给定的数组构造相应的堆。 ?对所构造的堆执行n-1次删除堆的根结点的操作，把删除得到的结点保存在给定数组中。 ? 1 构造堆的效率是多少？ ?O(n) ? 2 推排序的效率 ?O(nlogn) Horner法则 第七章时空权衡 计数排序 比较计数算法 算法ComparisonCountingSort(A[0...n-1]) //用比较计数法对数组排序 //输入：可排序数组A[0...n-1] //输出：将A中的元素按照升序排列的数组S[0..n-1] For i=0 to n-1 do count[i]=0 For i=0 to n-2 do For j=i+1 to n-1 do ifA[i] Count[j]=Count[j]+1 Else Count[i]=Count[i]+1 For i=0 to n-1 do S[Count[i]]=A[i] Return S C(n)=n(n-1)/2 第八章动态规划 WARSHALL算法 ?void WARSHALL（m） for (i=1; i<＝n; i++ ) for (j＝1; j<＝n; j++ ) if(m [j，i]＝T) for (k=1; i<＝n; i++ ) m [j，k] + ＝m [i，k]; (4) ?该算法由邻接矩阵在原矩阵构建传递闭包 ?WARSHALL算法的时间复杂度为O(n3)。Floyd算法 ?算法Floyd(W[1..n,1..n]) // 实现计算完全最短路径的Floyd算法 // 输入：图的权重矩阵W // 输出：包含最短路径长度的距离矩阵 伪代码 伪码（Pseudocode）是一种算法描述语言。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java等）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码，不用拘泥于具体实现。相比程序语言（例如Java, C++,C, Dephi 等等）它更类似自然语言。它是半角式化、不标准的语言。可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。 1.简介 定义 人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意：这里是实现，不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个（用其他编程语言编写的程序的）功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的描述都必须与设计结构图一起出现。伪代码是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。 应用领域 当考虑算法功能（而不是其语言实现）时，伪码常常得到应用。伪码中常被用于技术文档和科学出版物中来表示算法，也被用于在软件开发的实际编码过程之前表达程序的逻辑。伪代码不是用户和分析师的工具，而是设计师和程序员的工具。计算机科学在教学中通常使用虚拟码，以使得所有的程序员都能理解。综上，简单地说，让人便于理解的代码。不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。伪代码用来表达程序员开始编码前的想法。 2.语法规则 例如，类Pascal语言的伪码的语法规则是：在伪码中，每一条指令占一行（else if，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 4.29 算法练习讲义 1、根据如图所示的伪代码，当输入b a ,分别为2，3时，最后输出的m 的值是________ 第4题图 2．右图是一个算法流程图，则输出的k 的值是 ． 3．右图是一个算法的流程图，则输出的的值是． n 4.右图是一个算法流程图，则输出的n 的值是. 5.根据如图所示的伪代码，可知输出的结果S 为_____. 6 若输入变量N 的值为3，则输出的值为；若输出变量的S 的值为30，则变量N 的值为。 7.如果，当126,9,8.5x x P ===时3x =。 8、下图是一个算法的流程图，则输出的S的值是。 ，则判断框内可填写。 9.阅读流程图，若输出的S的值为7 10.运行如图所示的流程图，若输出的结果是62，则判断框中整数M的值是。 11.下图是某算法的流程图，则程序运行后所输出的S的值是。 12.上图是一个算法流程图，则输出的x的值是。 13.执行如图所示的流程图，输出的k的值为。 14、根据如图所示的伪代码，可知输出的结果S为________. 15、根据下图所示的伪代码，可知输出的结果S为 16.执行如图所示的程序框图，输出的x值为________． (第16题图) 17．如图，运行伪代码所示的程序，则输出的结果是____． 18．右边程序输出的结果是____． 19.如右图是一个算法流程图，则输出S的值是. 20.根据如图所示的伪代码，最后中输出的a的值为. 21.某程序框图如右上图所示，则该程序运行后输出的S值是. 22．如图是一个算法流程图，则输出的s的值是____． 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 目录 算法概论 (1) 序言 (1) 第一章 (2) 乘法 (2) 除法 (2) 两数的最大公因数 (2) 扩展 (2) RSA (3) 第二章：分治算法 (3) 整数相乘的分治算法 (3) 递推式 (3) 2.3合并排序 (3) 第三章图的分解 (4) 3.2.1寻找从给定顶点出发的所有可达顶点 (4) 3.2.2 深度优先搜索 (4) 第四章 (4) 4.2、广度优先搜索 (4) 4.4.1、dijkstra最短路径算法 (5) 4.6.1、含有负边 (5) Bellman-Ford算法 (6) 4.7、有向无环图的最短路径 (6) 第五章贪心算法 (6) 5.1 最小生成树 (6) 算法概论 序言 Fibonacci数列： 死板的算法： function Fib1(n) If n=0:return 0 If n=1:return 1 Return fib1(n-1)+fib1(n-2) (递归，很多计算是重复的，不必要) 合理的算法： functionFib2(n) If n=0:return 0 Create an array f[0…n] f[0]=0,f[1]=1 fori=2…n: f[i]=f[i-1] + f[i-2] return f[n] (随时存储中间计算结果，之后直接调用) 大O符号：若存在常数c>0，使得f(n)<=c*g(n)成立，则f=O(g)。f增长的速度慢于g。第一章 乘法： functionMultiply(x,y) If y=0:return 0 z=multiply(x,y/2)//向下取整 If y is even: //even---偶数 return 2z else: return x+2z 除法： functionDivide(x,y) If x=0: return (q,r)=(0,0) (q,r)=divide( x/2 ,y) //向下取整 q=2*q,r=2*r if x is odd:r=r+1 if r>=y :r=r-y,q=q+1 return (q,r) p22 两数的最大公因数： function Euclid(a,b) if b=0: return a return Euclid(b,a mod b) 扩展： 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 （1）用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 （2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 （3）算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 利用迭代算法解决问题，需要做好以下三个方面的工作： 一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一 伪代码的使用 伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。 下面介绍一种类Pascal语言的伪代码的语法规则。 伪代码的语法规则 1.在伪代码中，每一条指令占一行(else if例外，)，指令后不跟任何符号 （Pascal和C中语句要以分号结尾）； 2.书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于 if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进； 例如： line 1 line 2 sub line 1 sub line 2 sub sub line 1 sub sub line 2 sub line 3 line 3 而在Pascal中这种关系用begin和end的嵌套来表示， line 1 line 2 begin sub line 1 sub line 2 begin sub sub line 1 sub sub line 2 end; sub line 3 end; line 3 在C中这种关系用{ 和 } 的嵌套来表示， line 1 line 2 { sub line 1 sub line 2 { sub sub line 1 sub sub line 2 } sub line 3 } line 3 3.在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句， 有时也可省略标号。 例如： 1. line 1 2. line 2 a. sub line 1 b. sub line 2 1. sub sub line 1 2. sub sub line 2 c. sub line 3 3. line 3 4.符号△后的内容表示注释； 5.在伪代码中，变量名和保留字不区分大小写，这一点和Pascal相同，与 C或C++不同； 6.在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说 明就使用全局变量； 7.赋值语句用符号←表示，x←exp表示将exp的值赋给x，其中x是一个变 量，exp是一个与x同类型的变量或表达式（该表达式的结果与x同类型）； 多重赋值i←j←e是将表达式e的值赋给变量i和j，这种表示与j←e 和i←e等价。 例如： x←y x←20*(y+1) x←y←30 1、二分搜索算法是利用（A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解 14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法15．背包问题的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）16．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 19.回溯法的效率不依赖于下列哪些因素（ D ） 遗传算法( GA , Genetic Algorithm ) ，也称进化算法。遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。 一.进化论知识 作为遗传算法生物背景的介绍，下面内容了解即可： 种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。 个体：组成种群的单个生物。 基因 ( Gene ) ：一个遗传因子。 染色体 ( Chromosome )：包含一组的基因。 生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。 遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。 简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。 二.遗传算法思想 借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。 举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 ● 算法概述 算法性质：算法是输入、输出、有限性、确定性，若干条指令组成的有穷序列；程序可以不符合有限性是算法用某种程序设计语言的具体实现；算法复杂性：时间复杂性、空间负责性；O 阶数高，欧姆阶低，h 相等。 O 定义：存在正的常数C 和自然是N0，使得当N>=N0时，有f(N)<=Cg(N),则称f(N)当N 充分大时上有界，且g （N ）是他的一个上界，记为f(N)=O(g(N)). P 类问题：多项式时间内求解的判定问题，确定性计算模型下的已解类问题类； NP 类问题：非确定性多项式时间可解的判定问题；非确定性计算模型下的易验证问题类。 ● 递归与分治策略 递归算法定义：直接或间接调用自身的算法；用函数自身给出定义的函数称为。。；阶乘、数列 分治基本思想：将一个规模为n 的问题分解我k 个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解决这些问题，然后将各个子问题的解合并得到原问题的解。 分治法的基本步骤：（1）分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题；（2）解决：若子问题规模较小容易被解决则直接解决，否则递归递归解决各个子问题；（3）合并：将各个自问的解合并为原问题的解。 分治法解决问题的基本特征：（1）该问题缩小到一定的程度就可以很容易的解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题可以合并为该问题的解。（4）原问题分解出来的子问题是相互独立的，问题之间不包含公共子问题。 二分搜索描述：（分治策略的典型）将n 个元素分成个数大致相同的两半，取a[n/2 ]与x 相比较，如果x=a[n/2 ]，找到x 算法终止；如果x 华南农业大学期末考试试卷（A卷） 2004学年第二学期(2005.6)考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟 学号姓名年级专业 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了。 （A）二义性（B）有限性（C）正确性（D）可终止性 2、解决一个问题通常有多种方法。若说一个算法“有效”是指。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是。 （A）5n （B）20log2n（C）2n2（D）3nlog3n 4、渐进算法分析是指。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？ （A）大O表示法（B）大Ω表示法 （C）Θ表示法（D）小o表示法 6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是。 （A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用来实现。 （A）有序的线性表（B）队列（C）栈（D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。 （A）问题规模相同，问题性质相同 （B）问题规模相同，问题性质不同 （C）问题规模不同，问题性质相同 （D）问题规模不同，问题性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解 11、关于回溯搜索法的介绍，下面是不正确描述。 （A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 12、关于回溯算法和分支限界法，以下是不正确描述。 （A）回溯法中，每个活结点只有一次机会成为扩展结点 伪代码 伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码, 不用拘泥于具体实现。相比程序语言（例如Java, C++,C, Dephi 等等）它更类似自然语言。它是半角式化、不标准的语言。可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。 定义 人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意:这里是实现,不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个(用其他编程语言编写的程序的)功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的描述都必须与设计结构图一起出现。伪代码是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。 应用领域 当考虑算法功能（而不是其语言实现）时，伪代码常常得到应用。伪码中常被用于技术文档和科学出版物中来表示算法，也被用于在软件开发的实际编码过程之前表达程序的逻辑。伪代码不是用户和分析师的工具，而是设计师和程序员的工具。计算机科学在教学中通常使用虚拟码，以使得所有的程序员都能理解。综上，简单的说，让人便于理解的代码。不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。伪代码用来表达程序员开始编码前的想法。 语法规则 例如，类Pascal语言的伪代码的语法规则是：在伪代码中，每一条指令占一行（else if，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进。 伪代码实例 伪代码：是用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法。【简单示例】输入3个数，打印输出其中最大的数。可用如下的伪代 伪代码及其实例讲解 伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。 它以编程语言的书写形式指明算法的职能。相比于程序语言（例如Java, C++,C, Dephi 等等）它更类似自然语言。它是半角式化、不标准的语言。我们可以将整个算法运行过程的结构用接近自然语言的形式（这里，你可以使用任何一种你熟悉的文字，中文，英文等等，关键是你把你程序的意思表达出来）描述出来. 使用伪代码, 可以帮助我们更好的表述算法, 不用拘泥于具体的实现. 人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意:这里是实现,不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个(用其他编程语言编写的程序的)功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。 当考虑算法功能（而不是其语言实现）时，伪代码常常得到应用。计算机科学在教学中通常使用虚拟码，以使得所有的程序员都能理解。 综上，简单的说，让人便于理解的代码。不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。 语法规则 例如，类Pascal语言的伪代码的语法规则是：在伪代码中，每一条指令占一行（else if，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进。 算法的伪代码语言在某些方面可能显得不太正规，但是给我们描述算法提供了很多方便，并且可以使我们忽略算法实现中很多麻烦的细节。通常每个算法开始时都要描述它的输入和输出，而且算法中的每一行都给编上号码，在解释算法的过程中会经常使用算法步骤中的行号来指代算法的步骤。算法的伪代码描述形式上并不是非常严格，其主要特性和通常的规定如下： 1) 算法中出现的数组、变量可以是以下类型：整数、实数、字符、位串或指针。通常这些类型可以从算法的上下文来看是清楚的，并不需要额外加以说明。 2) 在算法中的某些指令或子任务可以用文字来叙述，例如，"设x是A中的最大项"，这里A是一个数组；或者"将x插入L中"，这里L是一个链表。这样做的目的是为了避免因那些与主要问题无关的细节使算法本身杂乱无章。 3) 算术表达式可以使用通常的算术运算符（+，-，*，/，以及表示幂的^）。逻辑表达式可以使用关系运算符=,≠,<,>,≤和≥，以及逻辑运算符与(and),或（or），非（not）。 4) 赋值语句是如下形式的语句：a<-b 。 这里a是变量、数组项，b是算术表达式、逻辑表达式或指针表达式。语句的含义是将b的值赋给a。 5) 若a和b都是变量、数组项，那么记号a<->b 表示a和b的内容进行交换。 var int[64] r, k //r specifies the per-round shift amounts r[ 0..15]：= {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} r[16..31]：= {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} r[32..47]：= {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} r[48..63]：= {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21} //Use binary integer part of the sines of integers as constants: for i from 0 to 63 k[i] := floor(abs(sin(i + 1)) × 2^32) //Initialize variables: var int h0 := 0x67452301 var int h1 := 0xEFCDAB89 var int h2 := 0x98BADCFE var int h3 := 0x10325476 //Pre-processing: append "1" bit to message append "0" bits until message length in bits ≡ 448 (mod 512) append bit length of message as 64-bit little-endian integer to message //Process the message in successive 512-bit chunks: for each 512-bit chunk of message break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15 //Initialize hash value for this chunk: var int a := h0 var int b := h1 var int c := h2 var int d := h3 //Main loop: for i from 0 to 63 if 0 ≤ i ≤ 15 then f := (b and c) or ((not b) and d) g := i else if 16 ≤ i ≤ 31 f := (d and b) or ((not d) and c)伪代码
中科院陈玉福计算机算法设计与分析期末简答题答案
算法设计与分析试卷(2010)
4.29 算法伪代码练习讲义
计算机算法设计与分析期末考试复习题
《算法概论》-伪代码
算法设计与分析期末试题答案解析
算法设计与分析试卷及答案.doc
算法题__计算机算法设计与分析期末试题4套(含答案)
伪代码的使用规范
计算机算法设计与分析期末考试复习题
遗传算法解释及代码(一看就懂)
算法设计与分析考试题及答案
算法设计与分析期末总结
2005.6算法设计与分析课程期末试卷
伪代码定义及实例
伪代码及其实例讲解
MD5算法的伪代码