武汉理工大学算法设计题(考试专用)

算法2.3二分检索//给定一个按非降次序排列的元素数组A(1:n),n≥1,判断x是否出现。若是，置j，使得x=A(j),若非，j=0//BINSEARCH(A,n,x)1low12highnwhilelow=high//如果lowhigh，数组A中没有找到x，返回j＝04do5{6//取处于low和high之间的中间值7ifx==A[mid]//找到值为x的元素，mid即为其下标，返回mid8thenreturnmid9elseifxA[mid]//如果xA[mid]，则x可能位于low与mid之间，10//否则x可能位于mid与high之间11thenhighmid-112elselowmid+113}14retrun0一种二分检索的变形BINSEARCH1。BINSEARCH1(A,n,x,j)3whilelowhigh4do5{67if(xA[mid])//在循环中只比较一次8910}11ifx==A[low]//x出现13elsej=0//x不出现14returnj算法2.5直接找最大和最小元素maxmin(A,n)//将A(1:n)中的最大元素置于max，最小元素置于min//1maxA[1]2minA[1];3fori2ton4do5{6ifmaxA[i]5thenmaxA[i]6ifminA[i]7thenminA[i]8}用下面的语句代替for循环中的语句：elseifendifendif最好情况将在元素按递增次序排列时出现，元素比较数是n-1；最坏情况将在递减次序时出现，元素比较是2（n-1）；至于在平均情况下,A(i)将有一半的时间比max大，因此平均比较数是3/2(n-1)。算法２.６递归求取最大和最小元素floatA[n];maxmin（i,j,fmax,fmin）//最大和最小元素赋给fmax和fmin1ifi==j2then3{456}7elseifi==j-18thenifA[i]A[j]9then10{11；1213}14else15{1617;18}19else20{2122maxmin(i，mid，lmax，lmin)23maxmin(mid+1，j，rmax，rmin）24iflmaxrmax2527iflminrmin2829el30}算法3.3背包问题的贪心算法Knapsack(ElemtypeWp[n],ElemtypePw[n],floaty[n],ElemtypeWC,intn)//p[n]和w[n]分别含有按p[i]／w[i]，p[i＋1]／w[i+1]排序的n件物品的效益值和容量。M是背包的容量大小，而y[n]是解向量//1fori←1ton2doy[i]←0;//将解向量初始化为0；3cu←C;//cu是背包中剩余的空间；4fori←1ton5do{//依次考察下一个物品是否可以放入背包；6ifw[i]cubreak;//物品i无法全部放入背包,退出for循环；7elsey[i]←1;8cu←cu-w[i];9}10ifi≤n11theny[i]←cu/w[i];//不能完全装入的物品的部分装入量算法3.4带有限期和效益的单位时间的作业排序贪心算法GreedyJob(intn,intd[],int&J[])//d[1],…,d[n]是期限值。n≥1。作业已按p1≥p2≥…pn被排序。J[i]是最优解中的第i个作业，1≤i≤k。终止时，d[J[i]]≤d[J[i+1]]，1≤i＜k//1k←1;2d[0]←0;3J[0]←0;4J[1]←1;//首先将作业1插入第一个位置；5fori←2ton//按p的非增次序依次考虑剩下的作业；6do{7r←k;8whiled[J[r]]d[i]andd[J[r]]≠r9do{//while循环用来确定正在考虑的作业可能要插入的位置；10r←r-1;11}12ifd[J[r]]≤d[i]andd[i]r//判断此作业是否可以插入J；13then{14forj←ktor+1//j是递减的15do{//将第k到第r+1个作业依次后移一位以插入新的作业；16J[j+1]←J[j];17}18J[r+1]←i;//将作业插入位置r+1；19k←k+1;//记入J的作业数加1;20}21}22returnk;//返回记入J中的作业数。算法JS所需要的总时间是O（sn）。由于s≤n(s为包含在解中的作业数)，因此JS的最坏计算时间为O（n2）。算法4.1多段图的向前处理算法FGRAPH(ElemtypeE[],intk,intn,ElemtypeP[k])//输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c[i][j]是边i,j的成本。P[k]是最小成本路径//输入：多段图的顶点编号表，各顶点的边表和各边的成本函数c(i，j)的表。输出：从s到t的一条最小成本路径上的各顶点以及成本COST(l，s)。1COST[n]0;2forjn-1to1by-1//计算COST[j]；3do{设r是这样一个结点，j,r且使c[j][r]+COST[r]取最小值；4COST[j]c[j][r]+COST[r];5D[j]r;6}//找一条最小成本路径；7P[1]1；P[k]n;8forj2tok-1//找路径上的第j个结点。9do{10P[j]D[P[j-1]];11}第3-6行的for循环的时间是(n+e)，第9-11行的for循环时间是。总的计算时间在以内。算法6.1回溯的一般方法BackTrack(n)//这是对回溯法控制流程的抽象描述。每个解都在X[n]中生成，一个解一经确定就立即打印出。在X[1]，…,X[k-1]已被选定的情况下，R（X[1]，…,X[k-1]）给出X[k]的所有可能的取值。限界函数C（X[1]，…,X[k]）判断哪些元素X[k]满足隐式约束条件//1k←1//变量k用来记录树的层数，初始化为12whilek0do3{4if还剩有没检验过的X[k]使得5X[k]∈R(X[1],…,X[k-1])andC(X[1],…,X[k])=true6then{if(X[1],…,X[k])是一条抵达一答案结点的路径7thenprint(X[1],…,X[k]);9}-1;//说明不剩没有检验的X(k)或Ck(X(1)..X(k))=false11}算法6.2递归回溯算法RBackTrack(k)//此算法是对回溯算法的抽象递归描述。进入算法时，解向量X[n]的前k-1个分量X[1],…X[k-1]已赋值//while满足下式的每个X(k)X[k]∈R(X[1],…,X[k-1])andC(X[1],…,X[k])=truedo{if(X[1],…,X[k])是一条已抵达一答案结点的路径thenprint(X[1],…,X[k]);RBackTrack(k+1)}算法6.4可以放置一个新皇后吗？以下函数Place(k)，用来判定将皇后k放在棋盘的第xk列是否可行，如果皇后k可以放在第xk列，那么Place(k)的返回值为真，否则返回值为假，显然，在进入该函数前，前k-1皇后已经放置好，即x[n]已确定k-1个值。Place(intk)1i←1;//设置i值；2whileik//把第k行皇后的位置与前k-1行的皇后的位置进行比较；3do{4ifx[i]=x[k]orabs(k-i)=abs(x[k]–x[i])//若皇后i和k相互攻击，5thenreturnFALSE;//返回FALSE6i←i+1//准备与下一行的皇后进行比较；7}8returntrue;算法6.5n-皇后问题的所有解//此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//nQueens(intn)1x[1]←0;2k←1;3whilek04do{5x[k]←x[k]+1;//将第k行的皇后k后移一列；6whilex[k]≤nandPlace(k)=FALSE//确定皇后k的列数x[k]；7dox[k]←x[k]+1;8ifx[k]≤n9then{10ifk=n//n个皇后的位置都已经确定，输出；11thenfori←1ton12doprint（x[i]）;13else{//n个皇后的位置还没全确定，考虑下一个皇后的位置；14k←k+1;15x[k]←0;}16}//x[k]≤n17else//当前行皇后无位置放，将上一行的皇后的位置重新安排；18k←k–1;//回溯//19}//while算法6.6子集和数问题的递归回溯算法SumOfSub(ints,intk,intr)//找W(1:n)中和数为M的所有子集。进入此过程时X(1),…,X(k-1)的值已确定。且。这些W(j)按非降次序排列。假定W(1)≤M，//生成左儿子。注意，由于Bk-1=true,因此s+W(k)≤M//1x[k]←1;//将第k个正数计入解向量；2if(s+w[k])=M//将第k个正数计入解向量后，得到一个可行解；3thenfori←1tok4doprint(x[i]);//输出这个可行解；5else{//第k个正数可以计入解向量，递归调用SumOfSub()算法；6if(s+w[k]+w[k+1])≤M)7thenSumOfSub(s+w[k],k+1,r–w[k]);}//以下生成右儿子和计算Bk的值8if(s+r–w[k])≥Mand(s+w[k+1])≤M)9then{//第k个正数不可以计入解向量，递归调用SumOfSub()算法。10x[k]←0;11SumOfSub(s,k+1,r-w[k]);12}LC-检索算法LC(ElemtypeT，Elemtypec[])的描述LC(ElemtypeT，Elemtypec[])//为找一个答案结点检索T；//书上的算法有错，请修改LC(ElemtypeT，Elemtypec[])1if(T是答案结点)2then{输出T；return;}3ET；//扩展结点；4将活结点表初始化为空;5while(1)do6{7for(E的每个儿子X)8do{if(X是答案结点)9then{输出从X到T的那条路径;10return;}11ADD(X);//X是新的活结点；12PARENT(X)E;}//指示到根的路径。13if(不再有活结点)14then{输出“noanswernode”;stop;}15LEAST(E);16}算法7.2最小成本的答案节点的LC搜索LineprocedureLC(T,C’)//为找到最小成本答案节点搜索T1E〈-T2置活节点表为空3while(1)do{4if(E是答案结点)5then{输出从E到T的路径;6return;}7for(E的每个儿子X)do8{callADD(X);PARENT(X)-E9}10if(不再有活结点)11then{print(‘noanswernode’);12stop;13}14LEAST(E)15}