5.《算法设计与分析》试题库

1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n) 5.procedure MAX(A,n,j) xmax?A(1);j?1 for i?2 to n do if A(i)>xmax then xmax?A(i); j?i;endif repeat end MAX 解:xmax?A(1);j?1 时间为:O(1) for i?2 to n do 循环最多n-1次 所以 总时间为: T(n)=O(1)+ (n-1)O(1)= O(n) 6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low?1;high?n while low?high do mid?|_(low+high)/2_| case :xA(mid):low?mid+1 :else:j?mid; return endcase repeat j?0 end BINSRCH 解:log2n+1 三、算法理解 1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 2 5 1 3 6 8 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 4 7 各边的代价如下: C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1 C(5,8)=4， C(6,8)=5 ，C(7,8)=6 解:Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 ，D[5]=8 Cost(3,6)= C(6，8)+0=5, D[6]=8 Cost(3,5)= C(5，8)+0=4 D[7]=8 Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)} = min{1+ 5, 2+4}=6 D[4]=6 Cost(2,3)= min{C(3，6)+ Cost(3,6) } = min{4+5}=9 D[3]=5 Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)} = min{8+5, 4+6}=10 D[2]=7 ost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ C Cost(2,4)} = min{3+10, 5+9,2+6}= 8 D[1]=4 1?4?6?8 2、写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=(48,12,61,3,5,19,32,7) 解:写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=() 1、 48,12,61,3, 5,19,32,7 2、48,12 61,3 5,19 32,7 3、 48,61, 12,3 19,32，5,7 4、 61,32 3,5 5、 61 3 3、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分 割的过程。 A=(65,70,75,80,85,55,50,2) 解:第一个分割元素为65 (1) (2) (3) (4) (5) (6) (7) (8) i p 65 70 75 80 85 55 50 2 2 8 65 2 75 80 85 55 50 70 3 7 65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 55 70 75 80 85 65 50 2 4、 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7) 解: 48,12,61,3 5,19,32,7 48,12 61,3 5,19 32,7 12,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，32 3,5, 7,12，19，32，48,61 5、写出图着色问题的回溯算法的判断X[k]是否合理的过程。 解:i?0 while iCU: x[3]?CU/ W[3]=3/8; 实例的解为:(1，1，3/8，0) 11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。 解:有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。 一共要要执行四次才能找到值为82的数。 12、使用prim算法构造出如下图G的一棵最小生成树。 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 1 2 4 3 6 5 dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 解:使用普里姆算法构造出如下图G的一棵最小生成树。 1 2 4 3 6 5 dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 1 1 1 4 3 3 3 6 6 1 1 4 2 2 4 3 3 5 6 6 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 13、有如下函数说明 int f(int x,int y) { f=x Mod y +1; } 已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细 过程。 解:有如下函数说明 int f(int x,int y) { f=x Mod y +1; } 已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细 过程。 } K的值是5 14、McCathy函数定义如下: 当x>100时 m(x)=x-10; 当x<=100时 m(x)=m(m(x+11)); 编写一个递归函数计算给定x的m(x)值。 解:McCathy函数定义如下: 当x>100时 m(x)=x-10; 当x<=100时 m(x)=m(m(x+11)); 编写一个递归函数计算给定x的m(x)值。 int m(int x) { int y; if(x>100) return(x-100); else { y=m(x+11); return (m(y)); } } 15、 设计一个算法在一个向量A中找出最大数和最小数的元素。 解:设计一个算法在一个向量A中找出最大数和最小数的元素。 Void maxmin(A,n) Vector A; int n; { used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional int max,min,i; max=A[1];min=A[1]; for(i=2;i<=n;i++) if(A[i]>max)max=A[i]; else if(A[i]cu then exit endif X(i) ?1 cu?cu-W(i) repeat end GREEDY-KNAPSACK 根据算法得出的解: X=(1,1,1,1,1,0,0)获利润52， 而解 (1,1,1,1, 0, 1,0)可获利润54 因此贪心法不一定获得最优解。 4. 设计只求一个哈密顿环的回溯算法。 解:Hamiltonian(n) {k?1; x[k] ?0; While k>0 do x[k] ? x[k]+1; while B(k)=false and x[k]?n do x[k] ? x[k]+1; repeat If x[k]?n then if k=n then {print x; return} else {k? k+1; x[k]?0;} endif else k? k-1 endif repeat end procedure B(k) { G[x[k-1],x[k] ]?1 then return false; for i?1 to k-1 do if x[i]=x[k] then return false;endif repeat return true; } 5(利用对称性设计算法，求n为偶数的皇后问题所有解。 解:利用对称性设计算法，求n为偶数的皇后问题所有解。 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional procedure NQUEENS1(n) a?0 //计数器清零 X(1)?0;k?1 //k是当前行;X(k)是当前列// While k>0 do //对所有的行执行以下语句// 1) { X(k)?X(k)+1 //移到下一列// While X(k)?n and not PLACE(k) do 2) X(k)?X(k)十l if X(k)?n then if k=n / then {print(X)，a?a+1 //找到一个解计数器a加1// if a=n/2 then return // 找到n/2个解算法结束 3) else {k?k+1;X(k)?0;} 4) else k?k,1 //回溯// } end NQUEENS 《算法分析与设计》试题库(三) 1、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或或f(n),,(g(n)) ，并简述理由。(12分) f(n),,(g(n)) 2(1) f(n),logn;g(n),logn，5; n2(2) f(n),2;g(n),100n; nn(3) f(n),2;g(n),3; 解:简答如下: 2n2nn (1)，(2)，(3) logn,,(logn，5)2,,(100n)2,;(3) R,{r,r,...,r)n2、试用分治法实现有重复元素的排列问题:设是要进行排列的12n Rr,r,...,r个元素，其中元素可能相同，试计算的所有不同排列。(13分) 12n 解:解答如下: Template used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional void Perm(Type list[],int k,int m) { if(k= =m){ for(int i=0;i<=m;i++) cout< int ok(Type list[],int k,int i) { if(i>k) for(int t=k;t int BinarySearch(Type a[],const Type& x,int n) {//假定数组a[]已按非递减有序排列，本算法找到x后返回其在数组a[]中 的位置，//否则返回-1 int left=0,right=n-1; while(left<=right){ int middle=(left+right)/2; ……………………………..(4分) if(x= =a[middle]) return middle+1; if(x>a[middle]) left=middle+1; ……………………………..(8分) else right=middle-1; } return -1; }……………………………..(12分) 4、试用动态规划算法实现0-1闭包问题。(15分) 解:解答如下: Template void Knapsack(Type v,int w,int c,int n,Type **m) { used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional Int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; ……………………………..(5分) for(int i=n-1;i>1;i--){ jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); …………..(8分) }; m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); …………..(10分) } Template Void Traceback(Type **m,int w,int c,int n,int x) { for(int i=1;ia[k]){ k++; a[k]=a[k-1]+1; n-=a[k]; };……………………………..(10分) if(n= =a[k]){ a[k]++;n--;}; for(int i=0;isum) sum=max; } } return sum; ……………………………..(10分) } int MaxSum(int n,int *a) { int sum=0,b=0; for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } Return sum; ……………………………..(15分) } i7、试用回溯法解决下列整数变换问题:关于整数的变换和g定义如下:f 。对于给定的两个整数和，要求用最少的变换和g变f(i),3i;g(i),i/2nmf，， 换次数将变为。(18分) nm 解:解答如下: void compute() { k=1; while(!search(1,n)){ k++; if(k>maxdep) break; init(); };……………………………..(6分) if(found) output(); else cout<<”No Solution!”<k) return false; for(int i=0;i<2;i++){ used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional int n1=f(n,i);t[dep]=i; ……………………………..(12分) if(n1= =m||search(dep+1,n1)){ Found=true; Out(); return true; } return false; ……………………………..(18分) } 《算法分析与设计》试题库(四) 一、 排序和查找是经常遇到的问题。按照要求完成以下各题:(20分) (1) 对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法 将其排成递减序。 (2) 请描述递减数组进行二分搜索的基本思想，并给出非递归算法。 (3) 给出上述算法的递归算法。 (4) 使用上述算法对(1)所得到的结果搜索如下元素，并给出搜索过程: 18，31，135。 答案:(1)第一步:15 29 135 18 32 1 27 25 5 第二步:29 135 18 32 27 25 15 1 5 【1分】 第三步:135 32 29 18 27 25 15 5 1 【1分】 第四步:135 32 29 27 25 18 15 5 1 【1分】 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional n，，(2)基本思想:首先将待搜索元素v与数组的中间元素进行比较，如果A,,2，， nn，，，，，则在前半部分元素中搜索v;若，则搜索成功;否则在后半vA,vA,,,,,22，，，， 部分数组中搜索v。【2分】 非递归算法: 输入:递减数组A[left:right]，待搜索元素v。【1分】 输出:v在A中的位置pos，或者不在A中的消息(-1)。【1分】 步骤:【3分】 int BinarySearch(int A[],int left,int right,int v) { int mid; while (left<=right) { mid=int((left+right)/2); if (v==A[mid]) return mid; else if (v>A[mid]) right=mid-1; else left=mid+1; } return -1; } (3)递归算法: [left:right]，待搜索元素v。【1分】 输入:递减数组A 输出:v在A中的位置pos，或者不在A中的消息(-1)。【1分】 步骤:【3分】 int BinarySearch(int A[],int left,int right,int v) { int mid; if (left<=right) { mid=int((left+right)/2); if (v==A[mid]) return mid; else if (v>A[mid]) return BinarySearch(A,left,mid-1,v); else return BinarySearch(A,mid+1,right,v); } else return -1; } (4)搜索18:首先与27比较，18<27，在后半部分搜索;再次与18比较，搜索到，返回5。【1分】 搜索31:首先与27比较，31>27，在前半部分搜索;再次32比较，31<32，在后半部分搜索，与29比较，31>29，此时只有一个元素，未找到，返回-1。【2used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 分】 搜索135:首先与27比较，135>27，在前半部分搜索;再次32比较，135>32，在前半部分搜索;与135比较，相同，返回0。【2分】 二、 对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。(20分)。 beg2 221 323ad 821 2cfh 答案:用V表示已经找到最短路径的顶点，V表示与V中某个顶点相邻接且121 不在V中的顶点;E表示加入到最短路径中的边，E为与V中的顶点相邻接1121 且距离最短的路径。【1分】 步骤 V V E E 1212 1. {a} {b} {} {ab} {a,b} {d} {ab} {bd} 2. 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh} 8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 【以上每步2分】 结果:从a到h的最短路径为abdfegh,,,,,,，权值为18。【1分】 三、 假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M,150，使用回溯方法求解此背包问题。请写出状态空间搜索树(20分)。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 答案:求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】 三、按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它们的序号分别记为1,7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional ax,11x,01ajx,12x,02aix,13 ax,03x,14x,04 ade x,14x,0x,054 behx,15x,0x,065egcx,06x,07fQ1 【状态空间搜索树及其计算过程17分，每个节点1分】 150115,7a( 4040305035190.625，，，，，,(1,1,1,1,,0,0)408 150115,7b. 4040305030177.5，，，，，,(1,1,1,1,0,,0)6012 c(4040305010170，，，，,(1,1,1,1,0,0,1) 150105,3d. 4040303530167.5，，，，，,(1,1,1,0,1,,0)604 150130,1e. 4040503530175，，，，，,(1,1,0,1,1,,0)603 150130,f. 44040503510170.71，，，，，,(1,1,0,1,1,0,)357 40405030160，，，,g. (1,1,0,1,0,1,0) 150140,2h. 4040353010146.85，，，，，,(1,1,0,0,1,1,)357 150125,5i. 4030503530167.5，，，，，,(1,0,1,1,1,,0)6012 150145,1j. 4030503530157.5，，，，，,(0,1,1,1,1,,0)6012 在Q处获得该问题的最优解为，背包效益为170。即在背包中装入(1,1,1,1,0,0,1)1 物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】 ()kAa,()四、 已知，k=1，2，3，4，5，6，r=5，r=10，r=3，r=12，1234kijrr*ii，1 r=5，r=50，r=6，求矩阵链积A×A×A×A×A×A的最佳求积顺序。(要567123456求:给出计算步骤)(20分) used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 答案:使用动态规划算法进行求解。 求解矩阵为:【每个矩阵18分】 1 2 3 4 5 6 1 0 150 330 405 1655 2010 2 0 360 330 2430 1950 3 0 180 930 1770 4 0 3000 1860 5 0 1500 6 0 1 2 3 4 5 6 1 0 1 2 2 4 2 2 0 2 2 2 2 3 0 3 4 4 4 0 4 4 5 0 5 6 0 因此，最佳乘积序列为(AA)((AA)(AA))，共执行乘法2010次。【结123456 论2分】 五、回答如下问题:(20分) (1) 什么是算法,算法的特征有哪些, (2) 什么是P类问题,什么是NP类问题,请描述集合覆盖问题的近似算 法的基本思想。 答案:(1)算法是解决某类问题的一系列运算的集合【2分】。具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出【8分】。 (2)用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题【2分】。用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。【2分】 集合覆盖问题的近似算法采用贪心思想:对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。【6分】 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 《算法分析与设计》试题库(五) 一、 填空题(本题15分，每小题1分) 1、算法就是一组有穷的 ，它们规定了解决某一特定类型问题 的 。 2、在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模 型。3个基本计算模型是 、 、 。 3、算法的复杂性是 的度量，是评价算法优劣的重要依据。 4、计算机的资源最重要的是 和 资源。因而，算法的复杂性有 和 之分。 n25、f(n)= 6×2+n，f(n)的渐进性态f(n)= O( ) 6、贪心算法总是做出在当前看来 的选择。也就是说贪心算法并不从整 体最优考虑，它所做出的选择只是在某种意义上的 。 7、许多可以用贪心算法求解的问题一般具有2个重要的性质: 性质 和 性质。 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 二、简答题(本题25分，每小题5分) 1、 简单描述分治法的基本思想。 2、 简述动态规划方法所运用的最优化原理。 3、 何谓最优子结构性质, 4、 简单描述回溯法基本思想。 5、 何谓P、NP、NPC问题 三、算法填空(本题20分，每小题5分) 1、n后问题回溯算法 (1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0 值,否则值为0。 (2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是 否放有棋子，有则值为1,否则值为0。 for(j=0;j=0;r--) //自底向上递归计算 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) 2 ; else 3 ; 3、Hanoi算法 Hanoi(n,a,b,c) if (n==1) 1 ; else { 2 ; 3 ; Hanoi(n-1,b, a, c); } 4、Dijkstra算法求单源最短路径 d[u]:s到u的距离 p[u]:记录前一节点信息 Init-single-source(G,s) for each vertex v?V[G] do { d[v]=?; 1 } d[s]=0 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional Relax(u,v,w) if d[v]>d[u]+w(u,v) then { d[v]=d[u]+w[u,v]; 2 } dijkstra(G,w,s) 1. Init-single-source(G,s) 2. S=Φ 3. Q=V[G] 4.while Q<> Φ do u=min(Q) S=S?{u} for each vertex 3 do 4 四、算法理解题(本题10分) 根据优先队列式分支限界法，求 下图中从v1点到v9点的单源最 短路径，请画出求得最优解的解 空间树。要求中间被舍弃的结点 用×标记，获得中间解的结点用 单圆圈?框起，最优解用双圆圈 ◎框起。 五、算法理解题(本题5分) k设有n=2个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表: ?每个选手必须与其他n-1名选手比赛各一次; ?每个选手一天至多只能赛一次; ?循环赛要在最短时间内完成。 k(1)如果n=2，循环赛最少需要进行几天; 3(2)当n=2=8时，请画出循环赛日程表。 六、算法设计题(本题15分) 分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求:说明所使 用的算法策略;写出算法实现的主要步骤;分析算法的时间。 七、算法设计题(本题10分) 通过键盘输入一个高精度的正整数n(n的有效位数?240)，去掉其中任意s个 数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s， 寻找一种方案，使得剩下的数字组成的新数最小。 【样例输入】 178543 S=4 【样例输出】 13 标准答案 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 一、填空题(本题15分，每小题1分) 1. 规则 一系列运算 2. 随机存取机RAM(Random Access Machine);随机存取存储程序机RASP(Random Access Stored Program Machine);图灵机(Turing Machine) 3. 算法效率 4. 时间、空间、时间复杂度、空间复杂度 n (2 5 6(最好 局部最优选择 7. 贪心选择 最优子结构 二、简答题(本题25分，每小题5分) 6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题， 这些子问题互相独立且与原问题相同;对这k个子问题分别求解。如果子 问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去， 直到问题规模足够小，很容易求出其解为止;将求出的小规模的问题的解 合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 7、“最优化原理”用数学化的语言来描述:假设为了解决某一优化问题，需要 依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任 何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策 只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…， Dn也是最优的。 8、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性 质。 9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度 优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结 点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解， 则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过 程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在 搜索过程，逐步构造出状态空间树，即边搜索，边构造。 10、 P(Polynomial问题):也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的 非确定性问题。 NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之 后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问 题。 三、算法填空(本题20分，每小题5分) 1、n后问题回溯算法 (1) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional (5) M[j]=L[i+j]=R[i-j+N]=0 2、数塔问题。 (1)c<=r (2)t[r][c]+=t[r+1][c] (3)t[r][c]+=t[r+1][c+1] 3、Hanoi算法 (1)move(a,c) (2)Hanoi(n-1, a, c , b) (3)Move(a,c) 4、(1)p[v]=NIL (2)p[v]=u (3) v?adj[u] (4)Relax(u,v,w) 四、算法理解题(本题10分) 五、(1)8天(2分); 3=8时，循环赛日程表(3分)。 (2)当n=2 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 六、算法设计题(本题15分) (1)贪心算法 O(nlog(n)) , 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽 可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包 后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽 可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 , 具体算法可描述如下: void Knapsack(int n,float M,float v[],float w[],float x[]) used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional {Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } (2)动态规划法 O(nc) m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优 值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。 j,wmax{m(i，1,j),m(i，1,j,w)，v},iiim(i,j),,0,j,wm(i，1,j)i, j,wv,nnm(n,j),,0,j,w0n, void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c); for (j=0;j<=jMax;j++) /*m(n,j)=0 0==w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0==w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } n(3)回溯法 O(2) cw:当前重量 cp:当前价值 bestp:当前最优值 void backtrack(int i) //回溯法 i初值1 { if(i> n) //到达叶结点 { bestp = cp; return; } used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional if(cw + w[i] <= c) //搜索左子树 { cw += w[i]; Cp += p[i]; backtrack(i+1); cw -= w[i]; cp -= p[i]; } if(Bound(i+1)>bestp) //搜索右子树 backtrack(i+1); } 七、算法设计题(本题10分) 为了尽可能地逼近目标，我们选取的贪心策略为:每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。 具体算法如下: 输入s, n; while( s > 0 ) { i=1; //从串首开始找 while (i < length(n)) && (n[i]1)&& (n[1]=„0?) delete(n,1,1); //删去串首可能产生的无用零 输出n; used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 《算法分析与设计》试题库(六) 一(填空题(每空2分，共30分) 1(算法的时间复杂性指算法中 的执行次数。 ,,2(在忽略常数因子的情况下，O、和三个符号中， 提供了算法运 行时间的一个上界。 (设D3表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)n 表示输入I出现的概率，则算法的平均情况下时间复杂性 A(n)= 。 4(分治算法的时间复杂性常常满足如下形式的递归方程: f(n),d , n,n,0 ,f(n)af(n/c)g(n) , nn,，,0, used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 其中，g(n)表示 。 5. 分治算法的基本步骤包括 。 6(回溯算法的基本思想是 。 7(动态规划和分治法在分解子问题方面的不同点是 。 8(贪心算法中每次做出的贪心选择都是 最优选择。 9(PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级 越 。 10(选择排序、插入排序和归并排序算法中， 算法是分治算法。 11(随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 的结果。 12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步 骤 ，就可得到一个随机化快速排序算法，该 随机化步骤的功能是 。 算法 QUICKSORT 输入:n个元素的数组A[1..n]。 输出:按非降序排列的数组A中的元素。 1. quicksort(1, n) end QUICKSORT 过程 quicksort(A, low, high) // 对A[low..high]中的元素按非降序排序。 2. if low0 then output i else output “no solution” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i的一个下标并返回，若 不存在，//则返回0。 if (2) then return 0 else mid= (low，high)/2，， if (3) then return mid else if A[mid]high (3) A[mid]=mid (4) mid+1, high (5) find(low, mid-1) 2. (1) 0 (2) i+d (3) C[i, k-1]+C[k, j]+r[i]*r[k]*r[j+1] (4) C[i, j] (5) C[1, n] 3. (1) i>=1 (2)k[i]+1 (3) 1 (4) i+1 (5) k[i]=0 (6) tag[x, y]=0 (7) x=x-dx[k[i]]; y=y-dy[k[i]] 四. 算法设计题: 1. 贪心选择策略:从起点的加油站起每次加满油后不加油行驶尽可能远，直至 油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。 算法 MINSTOPS 输入:A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行 驶的公里数m，存储各加油站离起点A的距离的数组d[1..n]。 输出:从A地到B地的最少加油次数k以及最优解x[1..k](x[i]表示第i次 加油的加油站序号)，若问题无解，则输出no solution。 d[n+1]=s; //设置虚拟加油站第n+1站。 for i=1 to n if d[i+1]-d[i]>m then output “no solution”; return //无解，返回 end if end for k=1; x[k]=1 //在第1站加满油。 s1=m //s1为用汽车的当前油量可行驶至的地点与A点的距离 i=2 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional while s1s1 then //以汽车的当前油量无法到达第i+1站。 k=k+1; x[k]=i //在第i站加满油。 s1=d[i]+m //刷新s1的值 end if i=i+1 end while output k, x[1..k] MINSTOPS 最坏情况下的时间复杂性:Θ(n) 《算法分析与设计》试题库(七) 一、 填空题(10空×2分，共20分) 1、 算法在运行时占有的机器资源的量称为算法复杂性，主要包括( 时 间 )和( 空间 )。 2222、 当一个算法的运行时间为n+n+1时，由于n+n+1与n的数量级相等，则称 2n为这个算法的( 时间复杂度 )。 m2、 多项式A(n)=a3n+…+ an+ an+ a的上界为( )。 m210 4、 递归算法设计的关键在于找出( 递归关系 )和( 最小问题的 解 )。 5、 ( 无后向性 )是问题能用贪婪算法或动态规划方法求解的前提。 6、 拆半查找、合并排序、二叉树遍历等算法中均采用了( 分而治之 ) 策略。 7、 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种走不通就掉 头的思想作为其控制结构 。 8、 用分支限界法解决布线问题时，对问题解空间搜索尝试结束的标志是 ( )。 二、 判断题(10题×2分，共20分) used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 1. 若c是正常数，则O(cf(n))=O(f(n))。v 2. 在最好情况下、最坏情况下、平均情况下的时间复杂度中，可操作性最好的 且最有实际价值的，是最坏情况下的时间复杂度。x 3. 好的算法在很大程度上取决于问题中数据所采用的数据结构。v 4. 迭代模型是通过小规模问题的解逐步求解大规模问题的解，正好与递归算法 设计相反。v 5. 用贪婪算法解决零钱兑换问题时，总能找到问题的最优解。x 6. 适用动态规划算法解决问题应该具有最优化原理和子问题重叠。x 7. 深度优先搜索算法可以搜索到问题所有可能的解方案。x 8. 解决马的遍历问题采用回溯法，对解空间树的搜索采用广度优先搜索方式v 9. 分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件 的解中找出使用某一目标函数值达到极大或极小的解。x 三、 简答题(3题×6分，共18分) 1、叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。 2、在算法设计的实际应用中，遇到的问题主要分为4类:判定性问题、计算问 题、最优化问题和构造性问题，请指出递归法、递推法、贪婪算法、分治法、 动态规划法、搜索算法各自适合解决的问题。 3、简述回溯法求解问题的一般步骤。 四、 程序填空题(6空×3分，共18分) 、找出n个自然数(1，2，3，…，n)中取r个数的组合。例如，当n=4,r=3时，1 所有的组合为: 4 3 2 4 3 1 4 2 1 3 2 1 以下是算法，请填空。 void comb(int n,int r) { int i,j; for(i=n; ? ; i--) { ? ; if(r>1) ? ; else { for(j=a[0]; j>0; j--) printf("%3d",a[j]); printf("\n"); } } } 2、走迷宫问题。迷宫是许多小方格构成的矩形，在每个小方格中有的是墙(用 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional “1”表示)有的是路(用“0”表示)。走迷宫就是从一个小方格沿上、下、左、 右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)， 出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。 数据结构:数组maze[8][8]存放迷宫;用数组fx[4]={1,-1,0,0},fy[4]={0,0,-1,1} 模拟上下左右搜索时的下标的变化过程;用迷宫原有的存储空间置元素值为“-1”时，标识已经访问过该方格。用数组做队的存储空间，队中的成员有三个:行号、列号、前一个方格在队列中的下标。 struct {int x,y,pre}sq[100]; search() { qh=0; qe=1; maze[1][1]= ? ; sq[1].pre=0; sq[1].x=1; sq[1].y=1; while( ? ) { qh=qh+1; for(k=1;k<=4;k++) { i=sq[qh].x+fx[k]; j=sq[qh].y+fy[k]; if (check(i,j)=1) //check()用来检查该方格是否可行 { ? ; sq[qe].x=i; sq[qe].y=j; sq[qe].pre=qh; maze[i][j]=-1; if(sq[qe].x=8 and sq[qe].y=8) { out(); return;} // out ()用来输出找到的路径 } } } print(“No avaliable way.”); } 五、 算法设计题(2题×12分，共24分) 1、输入一个高精度数据s和一个长整数c， 求s×c的精确值。 2、如下图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右 走，一直走到底层，要求找出一条路径，使路径上的数值和最大。 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 标准答案 一、填空题(10空×2分，共20分) 1、时间复杂度 空间复杂度 2、渐近时间复杂度或时间复杂度 m3、n 4、递归关系(递归方程) 递归终止(边界)条件 5、无后效性 6、分治算法 7、走不能就掉头 8、搜索到达b结点 或 活结点队列为空 二、 判断题(10题×2分，共20分) 1-5 ? × × ? ? 6-10 × × ? × ? 三、 简答题(3题×6分，共18分) 1、 答:两者都是递归算法思想的应用，根本策略是找出大规模问题与小规模子问题之间的关系，直到小规模的子问题容易得到解决，再由小规模子问题的解逐步导出大问题的解。 分治法能解决问题的特征: 1)问题的规模缩小到一定的程度就可以容易地解决。 2)问题可以分解为若干个规模较小的相似问题，即该问题具有最优子结构性 质。 3)利用该问题分解出的子问题的解可以合并为该问题的解。 4)该问题所分解出的各个子问题是相互独立的且子问题之间不包含公共的子问题。 当问题满足1，2，3，4条时采用分治法，当满足1、2、3条时采用动态规划方法。 2、"递推法"、"递归法"适合解决判定性问题和计算问题。 “贪婪算法”、“分治法” 、“动态规划法” 适合解决最优化问题。 “贪婪算法”、“分治法” 、“搜索算法” 适合解决 构造性问题。 3、回溯法是在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树，当算法搜索至解空间树的任一结点时，总是先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。 四、 程序填空题(6空×3分，共18分) used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 1 i>=r a[r]=i comb(i-1,r-1) 2 -1 qh<>qe qe=qe+1 五、 算法设计题(2题×12分，共24分) 1、 main( ) { long b,c,d; int a[256],i,j,n;char s1[256]; input(s1,c); n=strlen(s1); d=0; for(i=0,j=n-1;i=0;i--) print(a[i]); } 2、 main( ) { int a[50][50][3],i,j,n; print( 'please input the number of rows:'); input(n); for(i=1;i<=n;i++) for(j=1;j<=i;j++) { input(a[i][j][1]); a[i][j][2]=a[i][j][1]; a[i][j][3]=0; } for(i=n-1;i>=1;i--) for(j=1;j>=i ;j++) if(a[i+1][j][2]>a[i+1][j+1][2]) { a[i][j][2]=a[i][j][2]+a[i+1][j][2]; a[i][j][3]=0; } else { a[i][j][2]=a[i][j][2]+a[i+1][j+1][2]; used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional a[i][j][3]=1; } print(“max=“,a[1][1][2]); j=1; for(i=1;i<=n-1;i++) { print(a[i][j][1],„->?); j=j+a[i][j][3]; } print(a[n][j][1]); } 《算法分析与设计》试题库(八) 一、填空题(每小题3 分，共计30 分) 1. 用O、Ω和θ表示函数f与g之间的关系 ______________________________。 fnnngnn,,loglog ，，，， 1,1n,,2. 算法的时间复杂性为，则算法的时间fn(),,8(3/7),2fnnn，,, 复杂性的阶为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是___________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional 成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. _________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指_______________________________ ____________________________________________________________。 10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。 二、简答题(每小题10分，共计30分) 1. 试述回溯法的基本思想及用回溯法解题的步骤。 2. 有8个作业{1,2,„,8}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为: M1 10 2 8 12 6 9 4 14 M2 5 7 1 15 16 3 11 13 作业 1 2 3 4 5 6 7 8 给出一个最优调度方案，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少，并计算所需的最少时间。 3. 根据优先队列式分支限界法，求下图中从v1点到v9点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用×标记，获得中间解的结点用单圆圈?框起(如v2)，最优解用双圆圈◎框起。 ? 12v2v5v8 66233 310v1v36v9441v72 2 10v4v6 三、算法填空(每空2分，共计10分) 设R={r, r, ..., r}是要进行排列的n个元素，其中元素r, r, ..., r可能相12n12n同，试设计一个算法，列出R的所有不同排列，并给出不同排列的总数。算法如下，填写缺失的语句。 used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional template void Swap(Type &a,Type &b){ Type t=b; ________________; //1 a=t; } template bool ok(Type R[],int k,int i){ if(i>k) for(int t=k;t void Perm(Type R[],int k,int n,int &sum){ //n为元素个数，sum记录不 同排列的总数 if(k==n){ ______________________; //3 for(int i=1;i<=n;i++) cout<<___________________; //4 cout<0) { unsigned int i=0; //从串首开始找 while(i1&&n.at(0)=='0') used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional n.erase(0,1); //删除串首可能产生的无用零 return n; } used after the removal of plastic-wrapped, concrete curing period of not less than 7 days. Curing agent emulsion curing agent should be used to avoid yellowing on the surface of the concrete. Detailed rules for the implementation of specific implementation requirements 8 compliance and excellence project 8.1 standard of excellence presided over by the Chief Engineer of the project, implemented in full. 8.2 professional