《武汉理工大学算法设计题(考试专用)(共4页).doc》由会员分享，可在线阅读，更多相关《武汉理工大学算法设计题(考试专用)(共4页).doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 算法2.3 二分检索 /给定一个按非降次序排列的元素数组A(1:n),n1,判 断x是否出现。若是，置j，使得x=A(j),若非，j=0/BINSEARCH(A,n,x)1 low 12 high nwhile lowhigh，数组A中没有找到x，返回j04 do5 6 /取处于low和high之间的中间值7 if x=Amid/找到值为x的元素，mid即为其下标，返回mid8 thenreturn mid9 else if x Amid/如果x Amid，则x可能位于low与mid之间，10 /否则x可能位于mid与high之间11 then high mid -
2、 112 else low mid + 113 14 retrun 0一种二分检索的变形BINSEARCH1。BINSEARCH1(A,n,x,j)1 low 12 high n+13 while low high4do56 mid (low + high) / 27 if (x Amid)/在循环中只比较一次8 then high mid9else lowmid10 11 if x = Alow12 then j low/x出现13 else j=0 / x不出现14 return j算法2.5 直接找最大和最小元素maxmin(A,n) /将A(1:n)中的最大元素置于max，最小元素置于
3、min/1 max A12 min A1;3 for i 2 to n4 do5 6 if max Ai 7 then min Ai8 用下面的语句代替for循环中的语句： if A(i)max then maxA(i) else if A(i)min then minA(i) endif endif最好情况将在元素按递增次序排列时出现，元素比较数是n-1；最坏情况将在递减次序时出现，元素比较是 2（n-1）；至于在平均情况下,A(i)将有一半的时间比max大，因此平均比较数是3/2(n-1)。算法.递归求取最大和最小元素float An;maxmin（i, j, fmax, fmin）/最大
4、和最小元素赋给fmax和fmin1 if i = j 2 then3 4 fmax Ai;5 fmin Ai;6 7 else if i = j-18 then if Ai rmax25 then fmax lmax;26 else fmax rmax27 if lmin rmin28 then fmin rmin;29 else fmin lmin;30 算法3.3 背包问题的贪心算法Knapsack(ElemtypeW pn, ElemtypeP wn, float yn, ElemtypeW C, int n) /pn和wn分别含有按piwi，pi1wi+1排序的n件物品的效益值和容量。
5、M是背包的容量大小，而yn是解向量/1 for i1 to n 2 do yi0;/将解向量初始化为0；3 cu C;/cu是背包中剩余的空间；4 for i1 to n 5 do/依次考察下一个物品是否可以放入背包；6 if wi cu break;/物品i无法全部放入背包, 退出for循环；7 else yi1; 8 cu cu - wi;9 10 if in 11 then yi cu/wi; /不能完全装入的物品的部分装入量算法3.4 带有限期和效益的单位时间的作业排序贪心算法GreedyJob(int n , int d , int &J)/d1,dn是期限值。n1。作业已按p1p2
6、pn被排序。Ji是最优解中的第i个作业，1ik。终止时，dJi dJi+1，1ik/1k1;2d0 0;3J0 0;4J1 1;/首先将作业1插入第一个位置；5for i2 to n /按p的非增次序依次考虑剩下的作业；6 do7 rk;8 while dJr di and dJr r9 do/while循环用来确定正在考虑的作业可能要插入的位置；10rr - 1;11 12if dJrdi and di r/判断此作业是否可以插入J；13then14 for j k to r+1 /j是递减的15 do/将第k到第r+1个作业依次后移一位以插入新的作业；16 Jj + 1 Jj;17 18J
7、r + 1 i;/将作业插入位置r+1；19k k + 1;/记入J的作业数加1;20 21 22return k;/返回记入J中的作业数。算法JS所需要的总时间是O（sn）。由于sn (s为包含在解中的作业数)，因此JS的最坏计算时间为O（n2）。算法4.1 多段图的向前处理算法 FGRAPH(Elemtype E,int k, int n, Elemtype Pk) /输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，cij是边的成本。Pk是最小成本路径/输入：多段图的顶点编号表，各顶点的边表和各边的成本函数c(i，j)的表。输出：从s到t的一条最小成本路径上的各顶点以及成本CO
8、ST(l，s)。1 COST n0;2 for jn-1 to 1 by -1 /计算COST j；3 do 设r是这样一个结点， 且使cjr+ COSTr 取最小值；4 COSTj cjr+ COSTr;5 Djr;6 /找一条最小成本路径；7 P 11；P kn;8 for j2 to k-1 /找路径上的第j个结点。9 do 10 P jDP j-1;11 第3-6行的for循环的时间是(n+e)，第9-11行的for循环时间是 。总的计算时间在 以内。算法6.1 回溯的一般方法BackTrack(n) /这是对回溯法控制流程的抽象描述。每个解都在Xn中生成，一个解一经确定就立即打印出。
9、在X1，,Xk-1已被选定的情况下，R（X1，,Xk-1）给出Xk的所有可能的取值。限界函数C（X1，,Xk）判断哪些元素Xk满足隐式约束条件/ 1 k1 /变量k用来记录树的层数，初始化为1 2 while k0 do 3 4 if 还剩有没检验过的Xk使得 5 XkR(X1,Xk-1) and C(X1,Xk)=true6 then if (X1,Xk) 是一条抵达一答案结点的路径7 then print (X1,Xk);8 kk+1;9 10 else kk-1;/说明不剩没有检验的X(k)或Ck(X(1).X(k)=false11 算法6.2 递归回溯算法 RBackTrack(k)
10、/此算法是对回溯算法的抽象递归描述。进入算法时，解向量Xn的前k-1个分量X1,Xk-1已赋值/while 满足下式的每个X(k) XkR(X1,Xk-1) and C(X1,Xk)=true do if(X1,Xk)是一条已抵达一答案结点的路径 then print(X1,Xk) ; RBackTrack(k+1) 算法6.4 可以放置一个新皇后吗？ 以下函数Place(k)，用来判定将皇后k放在棋盘的第xk 列是否可行，如果皇后k可以放在第xk 列，那么Place(k)的返回值为真，否则返回值为假，显然，在进入该函数前，前k-1皇后已经放置好，即xn已确定k-1个值。 Place(int
11、k)1 i 1;/设置i值；2 while i 04 do5 xk xk + 1;/将第k行的皇后k后移一列；6 while xkn and Place(k)=FALSE /确定皇后k的列数xk；7 do xkxk + 1;8 if xkn9 then10 if k = n/n个皇后的位置都已经确定，输出；11 then for i 1 to n12 do print（xi）;13 else/n个皇后的位置还没全确定，考虑下一个皇后的位置；14 k k + 1;15 xk 0;16/xkn17 else /当前行皇后无位置放，将上一行的皇后的位置重新安排；18 k k 1; /回溯/19/wh
12、ile算法6.6 子集和数问题的递归回溯算法SumOfSub(int s , int k , int r) /找W(1:n)中和数为M的所有子集。进入此过程时X(1),X(k-1)的值已确定。 且 。这些W(j)按非降次序排列。假定W(1)M， /生成左儿子。注意，由于Bk-1=true,因此s+W(k) M/1 xk 1;/将第k个正数计入解向量；2if (s + wk) = M/将第k个正数计入解向量后，得到一个可行解；3then for i1 to k 4 do print(xi);/输出这个可行解；5else/第k个正数可以计入解向量，递归调用SumOfSub()算法；6 if (s
13、+ wk + wk + 1)M)7 then SumOfSub(s + wk , k + 1 , r wk); /以下生成右儿子和计算Bk的值8 if (s + r wk)M and (s + wk+1)M)9 then /第k个正数不可以计入解向量，递归调用SumOfSub()算法。10 xk 0;11 SumOfSub(s , k + 1 , r - wk);12 LC-检索算法LC(Elemtype T，Elemtype c)的描述LC(Elemtype T，Elemtype c)/为找一个答案结点检索T；/书上的算法有错，请修改LC(Elemtype T，Elemtype c)1if(
14、 T是答案结点)2then 输出T；return;3ET； /扩展结点；4 将活结点表初始化为空;5 while (1) do6 7 for (E的每个儿子X) 8 do if (X是答案结点) 9 then 输出从X到T的那条路径;10 return;11 ADD(X); /X是新的活结点；12 PARENT(X) E; /指示到根的路径。13 if (不再有活结点)14 then 输出“no answer node”;stop;15 LEAST(E);16 算法7.2 最小成本的答案节点的LC搜索Line procedure LC(T,C)/为找到最小成本答案节点搜索T 1 E-T 2 置活节点表为空 3 while (1) do 4 if (E 是答案结点) 5 then 输出 从E到T的路径; 6 return; 7 for (E 的每个儿子X) do 8 call ADD(X);PARENT(X)-E 9 10 if (不再有活结点) 11 then print(no answer node); 12 stop; 13 14 LEAST(E) 15 专心-专注-专业