《算法分析与设计习题集答案》由会员分享，可在线阅读，更多相关《算法分析与设计习题集答案（32页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计习题集算法分析与设计习题集基础篇基础篇1、 算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：特点：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算书上定义特征：特征：输入、输出、有穷性、明确性、有效性区别：区别：算法算法是完成特定任务的有限指令集。程序程序是用电脑语言编写的写成特定任务的指令序列。2、 算法的时间复杂度指的是什么？如何表示？算法的时间复杂度是一个函数， 它定量描述了该算法的运行时间。 这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述，不包括这个函数的低阶项和首项系数。 百度百科3、 算法的空间复杂度指的是什么
2、？如何表示？一个程序的空间复杂度是指运行完一个程序所需内存的大小。 利用程序的空间复杂度， 可以对程序的运行所需要的内存多少有个预先估计。 一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。1固定部分。这部分空间的大小与输入 /输出的数据的个数多少、数值无关。主要包括指令空间即代码空间 、数据空间常量、简单变量等所占的空间。这部分属于静态空间。2可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的
3、存储空间用f(n)表示。S(n)=O(f(n)其中 n 为问题的规模，S(n)表示空间复杂度。4、 什么是最坏时间复杂性？什么是最好时间复杂性？答：最坏情况时间复杂性：最好情况时间复杂性：I*是 DN 中使 T(N, I*)到达 Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I 的概率5、 什么是递归算法？什么是递归函数？递归算法包括直接递归和间接递归子程序 都是通过自己调用自己， 将求解问题转化成性质相同的子问题，最终到达求解的的。 递归算法充分地利用了电脑系统内部机能， 自动实现调用过程中对相关且必要的信息的保存与恢复，从而省略了求解过程中的许多细节的描述。【课本】直接递归子程
4、序在运行完成前调用它们自己。间接递归子程序在运行过程中调用其它子程序，其他子程序反过来调用这个调用子程序。递归函数， 把直接或间接地调用自身的函数称为递归函数。 函数的构建通常需要一个函数或者一个过程来完成。网上：答：1递归算法:直接或间接地调用自身的算法；2递归函数:用函数自身给出递归定义的函数。6、 分治法的设计思想是什么？将整个问题分成假设干个小问题后分而治之给定一个有 n 个输入的函数，分治策略建议将输入分为 k 个不同的子集，1kn，从而产生 k 个子问题。当输入规模 n 取值较大时，可以将这n 个输入分成 k1100递归体是：MMx+11 x 100实现此题功能的递归函数如下：in
5、tm ( intx ) int y;if ( x100 )return(x-10 );else y =m(x+11) ;return (m (y );procedure M( (x) )ifif x 100 thenreturnreturn( (x 10) )elseelsereturnreturn M( (M( (x+ +11) endifend M12、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。此题的算法思想是： 由于顺序表中元素已按元素值非递减有序排列， 值相同的元素比为相邻的元素，因此依次比较相邻两个元素，假设值相等，则删除其中一个，否则继续
6、向后查找，直到最后一个元素。实现此题功能的函数如下：voiddel ( seqlist*a )inti=0, j;while ( ilength)if ( a-datai!= a-datai+1)i+;elsefor ( j=i; jlength; j+)a-dataj=a-dataj+1;a-length-;procedure del( (A, ,LINK, ,n) )/A(1:n)是元素按元素值非递减有序排列的顺序表，LINK(1:n)每个数的下一个数所在的下标，等于 0 时表示后面再没有数了，初始时为 2，3，4n,0 global integer A ( (1: :n),),LINK(
7、 (1: :n) ) integer i , ,j i 1whilewhile LINK( (i)0 dodo j LINK( (i) )whilewhile j lchild=Null&rooot-rchild=Null)return(1);elsenum1=CountNode(root-lchild);num2=CountNode(root-rchild);return(num1+num2+1);procedure COUNTNODE( (T) )/T 是一棵二元树。T 的每个结点有三个信息段：LCHILD、DATA、RCHILD integer num1 , ,num2ifif T!=!
8、=0 thenifif LCHILD( (T)=)=0 and RCHILD( (T)=)=0 then/既没有左孩子，也没有右孩子，则为叶子节点returnreturn( (1) )elseelse num1= =COUNTNODE( (LCHILD( (T) num2= =COUNTNODE( (RCHILD( (T)returnreturn( (num1+ +num2+ +1) ) /将左右子树的结点数加起来，再加本身，相当时树的后序遍历 endfi endifreturnreturn( (0) )end COUNTNODE计算叶子总数int CountLeafs(BinTree *ro
9、ot)int num1,num2;if(root=Null) return(0);else if(root-lchild=Null&root-rchild=Null)return(1);elsenum1=CountLeafs(root-lchild);num2=CountLeafs(root-rchild);return(num1+num2);procedure COUNTLEAFS( (T) )/T 是一棵二元树。T 的每个结点有三个信息段：LCHILD、DATA、RCHILD integer num1 , ,num2ifif T!=!=0 thenifif LCHILD( (T)=)=0
10、and RCHILD( (T)=)=0 then/既没有左孩子，也没有右孩子，则为叶子节点returnreturn( (1) )elseelse num1= =COUNTLEAFS( (LCHILD( (T) num2= =COUNTLEAFS( (RCHILD( (T)returnreturn( (num1+ +num2) ) /将左右子树的结点数加起来，再加本身，相当时树的后序遍历 endfi endifreturnreturn( (0) ) /T 为空时，没有结点end COUNTLEAFS分治术分治术14、有金币 15 枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假
11、的金币找出来，试设计一种算法方案 ，使在最坏情况下用天平的次数最少。procedure SELECKP( (p, ,q) )/A 是一个全程数组，分别表示 n 个硬币的重量，在此题中表示 15 个硬币；p 和 q 表示假币所在的一组硬币的起始和终止编号；最后返回硬币的编号；在主程序中调用SELECKP(1,15)ifif p=q thenreturnreturn( (p);); endif ; ; global ingeger A ( (p: :q););integer a, ,b, ,c, ,d, ,m; ;ap; ;/第一组数的起始编号dq; ;/第二组硬币的终止编号m0; ;/最多余的一
12、个硬币所在的编号ifif( (ISODD( (q- -p+ +1)/如果该组硬币数量为 d 奇数 the n mq; ;/最后一个数不作比较dd- -1; ; edifc( (a+ +d+ +1)/)/2; ;/第二组硬币的起始编号编号bb- -1; ;/第一组硬币的终止编号/将该组硬币分为平均分为两组， 然后用天平比较两组重量，将轻的一组递归调用本方法IfIf WEIGHT( (a, ,b)WEIGHT( (c, ,d) ) thenreturnreturn( (SELECKP( (c, ,d););elseelse ifif m!=!=0/假设两组硬币重量相等，则剩下一个为假币return
13、return( (m););elseelse/如果两组硬币重量相等，且没有不比较的硬币，即本次检查的硬币总数为偶数，表示没有硬币 print ( (没有假币););returnreturn( (0);); endifend SELECKP15、利用分治策略，在 n 个不同元素中找出第 k 个最小元素。procedure SELECT( (A, ,n, ,k) )/在数组 A(1),A(n)中找出第 k 小元素 s 并把它放在位置 k， 假设 1=k=n。 将剩下的元素按如下方式重新排列，使 A(k)=t,有 A(m)=t，有 A(m)=t;对于 km=t.A(n+1)=+/ integer n
14、 , ,k, ,m, ,r, ,j; ;m1rn+ +1; ;A( (n+ +1) )+ +; ; loop/每当进入这一循环时，1=m=r=n+1/jr/将剩下的元素的最大下标加 1 后置给 j/ call PARTITION ( (m, ,j) ) /返回 j，它使得 A(j)，它使得 A(j)是第 j 小的值casecase: :k= =j: :returnreturn/找到该元素该元素为 A(j): :k )=v repeat /i 由左向右移loop pp- -1 until A( (p)=v repeat /p 由左向右移ifif i p- -1 then call A( (i)
15、)A( (p) ) /A(i)和 A(p)换位elseelse exit endif repeat A ( (m) )A( (p););A( (p) )v /划分元素在位置 p/end PARTITION16、设有 n 个运发动要进行网球循环赛。设计一个满足以下要求的比赛日程表。1每个选手必须与其它n-1 选手各赛一次；2每个选手一天只能赛一次。procedure TOURNAMENT( (n) )/A(1:n,1:n)为全程数组，A(i,j)表示第 i 天第 j 个队所比赛的对手,假设轮空则为 0 globel integer A ( (1: :n, ,1: :n) )ifif n= =1
16、then A ( (1, ,1)=)=1; ;returnreturn; ; endififif ISODD( (n) ) then/当队数为奇数时，增加一个虚拟队员 TOURNAMENT ( (n+ +1););returnreturn; ; endif TOURNAMENT ( (n/ /2););/是偶数时，递归调用，返回时合并 call MAKECOPY ( (n););/主要是将左上角的递归计算出的小块中的所有数字按照其相对位置抄写到右下角，将左上角小块中的所有数字加 n/2 后按照其相对位置抄写到左下角，将左下角小块中的所有数字按照相对位置抄到右上角。end COUNTLEAFS1
17、7、已知序列503，87，512，61，908，170，897，275，652，462，写一个自底向上的归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。voidMerge(ElemType *r，ElemType *rf，int u，int v，int t)for(i=u，j=v，k=u；iv&j=t；k+) if(ri.keyrj.key) rfk=ri；i+；else rfk=rj；j+；if(iv) rfkt=riv-1；if(jelem；for(len=1；lenlength；len=2*len)/*从 q2 归并到 q1*/ for(i=1；i+2*len-1leng
18、th；i=i+2*len) Merge(q2，q1，i，i+len，i+2*len-1)；/*对等长的两个子表合并*/if(i+len-1length) Merge(q2，q1，i，i+len，p-length)；/*对不等长的两个子表合并*/else if(ilength) while(ilength)/*假设还剩下一个子表，则直接传入*/ q1i=q2i；q1q2；/*交换，以保证下一趟归并时，仍从 q2 归并到 q1*/if(q1!=p-elem)/*假设最终结果不在*p 表中，则传入之*/ for(i=1；ilength；i+) p-elemi=q1i；Procedure MERGES
19、ORT( (low, , high) )/A(low : high)是一个全程数组，它含有 high-low+10 个待分类的元素/ Integer low , , high If low high thenmid int(low+ +high)/)/2) )/求这个集合的分割点/ call MERGESORT ( (low, , mid) )/将一个子集合分类/ call MERGESORT ( (mid+ +1, , high) )/将另一个子集合分类/ cal MERGE ( (low, ,mid, ,high) )/归并两个已分类的子集合/ EndifendMERGESORTProce
20、dure MERGE( (low, , mid, , high) )/A(low : high)是一个全程数组，它含有两个放在 Alow : mid和 Amid+1 : high中的已分类的子集合。 目标是将这两个已分类的集合归并成一个集合， 并存放到 A(low : high)中/使用一个辅助数组 B(low : high)/ Integer h , , I, , j, , k, , low, , mid, , high/lowmid mid then/处理剩余的元素/forfor kj to high dodo/第二队列未处理完 B( (i) ) A( (k) ) ii+ +1 repea
21、t Elseforfor kh to mid dodo/第一队列未处理完 B( (i) ) A( (k) )ii+ +1 repeat endifforfor k low to high dodo/将已归并的集合复制到 A/ A ( (k) ) B( (k) ) repeatendMERGE归并过程黄色底纹的是每次归并的数0 01 12 23 34 45 56 67 78 89 91 15038787876161616161612 2875035035038787878787873 35125125125125035035035035031704 46161616151251251251251
22、22755 59089089089089089089089089084626 61701701701701701701701701705037 78978978978978978972752752755128 82752752752752752758978974626529 96526526526526526526524626528971010462462462462462462462652897908贪心法贪心法18、设有 n 个文件 f1，f2，fn要求存放在一个磁盘上，每个文件占磁盘上1 个磁道。这n 个文件的检索概率分别是p1，p2，pn，且np=1。磁头从当前磁道移到被检索信ii1息
23、磁道所需的时间可用这两个磁道之间的径向距离来度量。 如果文件 fi存放在第 i 道上，1in 则检索这 n 个文件的期望时间是1i jnppd(i,j)。其中 d(i，j)是第 i 道与第 jij道之间的径向距离。 磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间到达最小。试设计一个解此问题的算法，并分析算法的正确性与计算复杂性。/*磁盘文件最优存储问题具有贪心选择性质：先将 n 个文件从大到小按概率进行排序。假设排序后有 p1=p2=pn。贪心选择性质表示每次所选择加入的对象文件，都能得到当前的最优值，即使得期望检索时间到达最小。在磁盘最优存储问题中，要想使期望检索
24、时间到达最小。 那么就要使两个概率较大者的径向距离越小越好。 因此第一次从 p1=p2=pn 中选取 P1 所对应的文件 f1 置于中心磁道上。随后从剩余概率队列中选取概率最大和次最大者所对应的文件放在靠着 f1 的左磁道，和 f1 的右磁道。这将得到初始的最优值。同样地，继续选择剩余概率队列中概率最大和次最大者所对应的文件分别置于靠着刚刚所得最优位置的左磁道和右磁道上， 将得到新的最优值。所以磁盘最优存储问题具有贪心选择性质。最优子结构性质：按照这 n 个文件的排序概率(p1=p2=pn)假设排序后的理想最优序列为：fn-1,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,
25、f(j)f(n-2),fn。n 为奇数。假设 n 为偶数个，则补上一个数 0。那么不管 n 为奇数或者是偶数，其理想最优序列都可以表示为 f n-1 ,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。因为加上一个 0，对其到达最小期望检索时间无影响，所以可以进行此处理。利用反证法思想假设存在一个fn-1,f(n-3),f(n-5),f(j)f4,f2,f1,f3,f5,f(i)f(n-2),fn。该序列是原序列对调 f(i)与 f(j)的位置所得。 该序列所得到的期望检索时间小于上面的贪心策略时间。经验证发现，该序列所获得的期望检索时间原所获得的期
26、望检索时间。与最优值相矛盾。故贪心解为最优解。*/procedure GreedySearch( (P, ,A, ,n) )/P(1:n)是按照 P(i)=P(i+1)排序的 n 个文件读取的概率； A(1:n)表示对应的文件序号；X(1:n)表示 n 个文件分别所放的在磁盘上的存储位置，即所要求的解 integer P ( (1: :n),),A( (1: :n) ) integer i , ,k, , n k n/ /2/取中间位置,除法为向下取整/ X ( (k) )A( (1) )/中间位置放概率最大的文件/forfor i2 to n by + +2 dodo X ( (k+ +i/
27、 /2) )A( (i) ) repeatforfor i3 to n by + +2 dodo X ( (k i/ /2) )A( (i) ) repeatend GreedySearch19、设有 n 个正整数，编写一个算法将他们连接成一排，组成一个最大的多位整数。用贪心法求解此题。procedure MAXINT( (A, ,n) )/A(1:n)是由 n 个整数组成的数组，S(1:n)是将 A 中每个数转化为字符串得到的数组 integer A ( (1:,:,i, ,j, ,a, ,b string B ( (1: :n),),sforfor i1 to n 1 dodoforfor
28、 i1 to n dodoaSTRINT( (B( (i),),B( (j)bSTRINT( (B( (j),),B( (i)forfor a 右边的数，因为删除之后高位减小，很容易想.那全局最优解也就是这个了，因为删除 S 个数字就相当于执行了 S 次删除一个数，因为留下的数总是当前最优解.*/procedure GreedyDelet( (N, ,S, ,X) )/N 表示高精度的正整数此整数中没有0，要去掉 S 个整数，X(1:s)表示删除数字的位置 real X ( (1: :s) )char* * ntN /把整数转化为字符串处理 integer s Swhilewhile s 0
29、dodo i = =0 /从串首开始whilewhile i length( (nt) ) andand n in i+ +1 dodo i+;+; repeat delet ( (nt, ,i););/删除串 n 的第 i 个字符 s -;-; X ( (S- -s) )i; ; repeat print ( (X););/输出每次删除的位置 print ( (nt););/输出最后组成的新的整数end GreedyDelet21、对于下列图给出的有向网，写出用 Dijkstra 方法求从顶点 A 到图中其它顶点的最短路径的算法，并写出执行算法过程中顶点的求解次序及从顶点A 到各顶点路径的长
30、度。procedure SHORTEST- -PATHS( (v, ,COST, ,DIST, ,n) ) /G 是一个 n 结点的有向图，它由其成本邻接矩阵 COST(n,n)表示 DIST(j)被置以结点 v 到结点 j 的最短路径长度， 这里 1=j=n;DIST(v)被为 0 boolean S ( (1: :n););real COST( (1: :n, ,1: :n),),DIST( (1: :n) ) integer u , ,v, ,n, ,num, ,i, ,wforfor i1 to n dodo/将集合 S 初始化为空 S ( (i) )0; ; DIST ( (j) )
31、COST( (v, ,j);); repeat S ( (v) )1; ;/将结点 v 计入集合 S DIST ( (v) )0; ;forfor num2 to n- -1 dodo /确定由结点 v 出发的 n-1 条路选取结点 u，它使得在 S( (w)=)=0 的条件下，DIST( (u)=)=min DIST( (w) S ( (u) ) 1; ;/结点计入 Sforfor 所有 S( (w)=)=0 的结点 w dodo DIST( (w) )min( (DIST( (w),),DIST( (u)+)+COST( (u, ,w) repeat repeatend SHORTEST-
32、 -PATHSAA0B48C+D15E28F+G40BCDEFG+012+043+0+33+9+180+1333+020+23+0执行踪迹选取的迭代结点置初值 -1D2E3G45BFSAA,DA,D,EA,D,E,GA,D,E,G,BA00000B484848484848C+61616057SD151515151515E282828282828F+4848484848G403838383838A,D,E,G,B,F022、对于上图给出的有向图，写出最小成本生成树，给出求解算法。B129AE1518D23GLine procedure KRUSKAL( (E, ,COST, ,n, , T, ,
33、 mincost) )/G 有 n 个结点，E 是 G 的边集，COSTu, v是边u, v的成本。T 是最小成本生成树的边集，mincost 是它的成本。/1 real mincost , , COST( (1: : n, , 1: : n) )2 integer PARENT ( (1: :n),), T( (1: :n 1, , 2),), n3以边成本为元素构造一个 min 堆4PARENT15imincost06whilewhile i n 1 and 堆非空 dodoCF207从堆中删去最小成本边( (u, , v) )并重新构造堆8jFIND( (u) )kFIND( (v) )
34、9ifif jk then ii+ +110 T( (i, , 1) )u T( (I, ,2) )v11mincostmincost+ +COST( (u, , v) )12 call UNION( (j, , k) )13 endif14 repeat15ifif in 1 then print( (no spanning tree) ) endif16returnreturn17 end KRUSKAL动态规划动态规划23、求出上图中每对结点间的最短距离的算法，并给出计算结果。line procedure ALL PATHS( (COST, , A, , n) ) integer i ,
35、 , j, , k, , n real COST( (n, , n),), A( (n, , n) )1forfor i1 to n dodo2forfor j1 to n dodo3 A ( (i, ,j) ) COST( (i, ,j) )4 repeat5 repeat6forfor k1 to n dodo7forfor i1 to n dodo8forfor j1 to n dodo9 A( (i, ,j) ) min A( (i, ,j),), A( (i, ,k)+)+A( (k, ,j)10 repeat11 repeat12 repeat13 end ALL PATHSABC
36、DEFGA0B480C571204233929D1555430765272E2873611807090F4825133346020G387866239975024、下列图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A 到达城市 E，怎样走路程最短，最短路程的长度是多少?line procedure FGRAPH ( (E, , k, , n, , P) )/多段图的向前处理算法,输入是按照段的给结点编号的，有 n 个结点的 k 段图。E 是边集，c(i,j)是边(i,j)的成本。P(1:k)是最小成本路径/1 real CO
37、ST ( (n),), integer D( (n- -1),),P( (k),), r, , j, , k, , n2 COST ( (n) )03forforjn- -1 to 1 by - -1 dodo4设 r 是一个这样的结点， E 且使 c( (j, , r)+)+COST( (r) )取最小值。5 COST jc( (j, , r)+)+COST( (r) )6 D ( (j) ) r7 repeat /找一条最小成本路径8 P ( (1) ) 1; ;P( (k) ) n9forfor j2 to k- -1 dodo/找路径上的第 j 个结点10 P ( (j) ) D( (
38、P( (j- -1)11 repeat12 end FGRAPH最短路程:1371011 (13)25、已知序列 a1，a2，an，试设计一算法，从中找出一子序列ai1 ai2 aik使 k 到达最大，并讨论其复杂性。算法一：procedure lis( (A, ,f, ,n) )/A(1:n)为长度为 n 数组序列，f(i)表示 A 中以 A(i)为末元素的最长递增子序列的长度 f( (0) )1; ;/以第 a1 为末元素的最长递增子序列长度为 1；forfor i 2 to n dodo/循环 n-1 次 f( (i) )1; ;/f(i)的最小值为 1；forfor j0 to i d
39、odo/循环 i 次ifif A( (j)f( (i)-)-1 then /选出最大的 f(j) f( (i) )f( (j)+)+1; ;/更新 f(i)的值。endifendif repeat repeatrepeatrepeatreturnreturn f( (n- -1) )end lis这个算法有两层循环，外层循环次数为这个算法有两层循环，外层循环次数为 n-1n-1 次，内层循环次数为次，内层循环次数为 i i 次，算法的时间复杂度次，算法的时间复杂度所以所以 T(n)=O(n2)T(n)=O(n2)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。这个算法的最坏时间复杂度与第一
40、种算法的阶是相同的。算法二：改良后算法procedure lis1( (A, ,B, ,n) )/A(1:n)为长度为 n 数组序列,数组 B 来存储“子序列的”最大递增子序列的最末元素 B 0=-=-10000; ;/把 B0设为最小，假设任何输入都大于-10000； B 1=A 0;/初始时，最大递增子序列长度为 1 的最末元素为 a1int len = = 1; ;/Aen 为当前最大递增子序列长度，初始化为 1；int p, ,r, ,m; ;/p,r,m 分别为二分查找的上界，下界和中点；forfor i = = 1 to n dodo p = =0; ;r= =len; ;whil
41、ewhile p=r dodo/二分查找最末元素小于 ai+1 的长度最大的最大递增子序列； m = = ( (p+ +r)/)/2; ;ifif B m len) ) then len+;+;/更新当前最大递增子序列长度； endif repeatreturnreturn len; ;end lis1算法的循环次数为算法的循环次数为 n n，每次循环二分查找用时，每次循环二分查找用时 lognlogn，所以算法的时间复杂度为，所以算法的时间复杂度为 O(nlogn)O(nlogn)。这。这个算法在第二种算法的基础上得到了较好的改良个算法在第二种算法的基础上得到了较好的改良26、设计一个 On
42、2时间的算法，找出由 n 个数组成的序列的最长的单调递增子序列。上题算法一上题算法一27、旅游预算问题。一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有假设干加油站， 每个加油站收费不一定相同。 旅游预算有如下规则： 假设油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2 元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分1 元=100 分 。编写算法估计实际行驶在某路线所需的最小费用。Procedure LESTCOST( (v, ,vm, ,f, ,n, ,S, ,FP, ,P) )
43、/共 n 个加油站，起点、加油站、和终点，分别编号为 0,1,2.n,n+1，v 为油箱容量，vm 为每升油行驶的公里数，S 为 n 个加油站和起点的距离，FP(1:n)为每个加油站的油价，P(1:n)为每次所停的加油站 integer n , ,P( (1: :n),),N( (1: :n) )float v, ,vm, ,f, ,S( (1: :n),),FP( (1: :n),),LEST( (1: :n) ) integer i , ,j, ,kfloat vf i = =0 vf= =0LESTMAX LEST ( (0) )fwhilewhile i n+ +1 dodo j =
44、=i+ +1whilewhile j n+ +1 and S( (j) ) S( (i)v* *vmthen jj 1 endififif j=i then print( (不可能到达终点) ) returnreturn endififif j= =n then /到达终点continuecontinue endif k = =jwhilewhile j n+ +1 S( (j) ) S( (i)=)=v* *vm/油够到达该站并停车 vf=(=(S( (j) ) S( (i)/)/vm/需要补充的汽油量 cost= =LEST( (i)+)+vf* *FP( (j)+)+2/在 j 站停车的
45、最小血糖ifif cost 0 P ( (j 1)=)=F( (P( (j) j = =P( (j 1) ) enifenif此题的求解与求有向图的最短路径比较相似， 也是选取两点间的直接连线费用和经过某个中间结点进行转折费用中的最小者。 因此， 求总费用的最小值可以分解为求假设干分段的费用最小值，它满足优化原则，所以此题可以采用动态规划的方法进行求解。For interval:=1 to n-1 to do for start:=0 to n-1 do if start+interval=n then Begin Stop:=interval+start; If 从 start 能直接到 s
46、top thenBegin Leststart,stop:=从 start 能直接到 stop 的费用； Nextstopstrat,stop:=stop;End;求出直接从 start 到 stop 的费用一 For next:=start+1 to stop-1 do If 从 start 能直接到 next thenBegin Cost:=从 start 到 next 的费用+从 next 到 stop 的费用； If costE。试用动态规划的最优化原理求出A-E 的最省费用。基本的多段图问题略基本的多段图问题略A-B1(5)-C1(6)-D1(3)-E(5),A-B1(5)-C1(6
47、)-D1(3)-E(5),最短的距离为最短的距离为 191929、已知如下列图，写出用动态规划求最短路径的递推关系式， 并写出求从源点 A0 到终点A3 的最短路径过程。给出求解算法。6A1A2552A0A3344B1B25基本的多段图问题略基本的多段图问题略COST(2,A1)=min(6+COST(3,A2),5+COST(3,B2)=8OCST(2,B1)=min(4+COST(3,A2),5+COST(3,B2)=6COST(1,A0)=min(5+COST(2,A1),3+COST(2,B1)=9最小成本路径为 S=A0,B1,A2,A3搜索与遍历问题搜索与遍历问题30、已知有向图
48、G=，试设计一算法以判断对于任意两点u 和 v，是否存在一条从u到 v 的路径，并分析其复杂度。Line procedure BFS ( (u, ,v) )/宽度优先检索 G，它在结点 u 开始执行。所有已访问结点都标上 VISITED(i)=1。图 G和数组 VISITED 是全程量。VISITED 开始时都已置成 0，如果找到 v 则程序停止/ VISITED ( (u) ) 1; ;tu将 Q 初始化库空/Q 是未检测结点的队列/ Loop For 邻接于 t 的所有结点 wdodoifif w=v/找到 v，说明能从 u 到 v thenreturnreturn true endifi
49、fif VISITED( (w)=)=0 then call ADDQ( (w, , Q) )/w 未检测/ VISITED( (w) ) 1 endif Repeatifif Q为空 thenreturnreturn false endif/不再有还未检测的结点，说明不能从 u 到 v/ Call DELETEQ( (t, , Q) )/从队中取一个未检测的结点/ Repeatend BFS假设假设 G G 由邻接表表示，则由邻接表表示，则 t(n,e)=O(n+e),S(n,e)=O(n)t(n,e)=O(n+e),S(n,e)=O(n) 假设假设 G G 由邻接矩阵表示则由邻接矩阵表示则
50、t(n,e)=O(n2)t(n,e)=O(n2)和和 S(n,e)=O(n)S(n,e)=O(n)31、对于给定的一个二叉树T如下列图a)设计一个算法，统计二叉树中结点总数；b)设计一个算法，求二叉树最大宽度及最大宽度所在深度。设计一个算法，统计二叉树中结点总数；Procedure INORDER( (T) )/T 是一棵二元树。T 的每个结点有三个信息段：LCHILD、DATA、RCHILD，count 用来计算结点数的全程数组/ global integer count0 /count 是全程变量If T0 then call INORDE R( (LCHILD( (T) count+ c
51、all INORDER( (RCHILD( (T) endifend INORDER设计一个算法，求二叉树最大宽度及最大宽度所在深度Procedure LEVEL( (T) )/T 是一棵二元树。T 的每个结点有三个信息段：LCHILD、DATA、RCHILD,w 用来计算/integer width1 /记录最大宽度integer curwidth1; ;/记录当前层宽度integer nextwidth0; ;/记录下层宽度integer hight1; ;/记录最大宽度所在的深度integer curhight1; ;/记录当前深度 ADDQ ( (Q, ,T););whilewhile
52、 Q 非空 dodowhilewhile curwidth! !=0 dodo DELETEQ( (Q, ,T););/出队 curwidth-;-;ifif LCHILD( (T)!)!=0/左孩子入队 then DELETEQ ( (Q, ,LCHILD( (T);); nextwidth+;+; endififif RCHILD( (T)!)!=0 /右孩子入队 then DELETEQ ( (Q, ,RCHILD( (T);); nextwidth+;+; endif repeat curhight +;+;/下一层宽度ifif nextwidth width/如果下层比最宽层宽， 将
53、宽度和深度赋给 width 和 hightthen widthnextwidth; ;hightcurhight endifcurwidthnextwidth; ;/进度下一层nextwidth0; ;end LEVEL32、判近亲问题。给定一个家族族谱，为简化问题起见，假设家族中的夫妻关系只表示男性成员。设用线性表存储家族成员，用成员的父指针指向其生父。编写一个在此种族谱表示方式下的算法，判断给定的二个家族成员是否是五代内的近亲。 提示：家族成员的表示方式应与搜索方式相适应。 Procedure ISNEARRELATION( (PARENT, ,a, ,b, ,n) )/PARENT(i)
54、表示家族成员 i 的生父，a 和 b 是我们要判断是否是近亲的成员/ real PARENT ( (1: :n) ) integer A ( (1: :4),),B( (1: :4););/分别用来存放 a,b 五代以内的近亲 integer a , ,b, ,at, ,bt; ; at a; ; bt b; ;forfor i1 to 4 dodo/分别将 a,b 五代以内的祖先放入一个数组ifif PARENT( (at)0 dodo atPARENT( (at);); A( (i) )at; ; endififif PARENT( (bt)0 dodo btPARENT( (bt) )
55、A( (i) )bt endif repeatforfor i1 to 4 dodo/比较 a，b 是否有相同的祖先forfor ij to 4 dodoifif A( (i) ) =0 or B( (j) ) =m then print(stack overflow)8 Stop9 Endif10 STACK(i) P; PLCHILD(P)11 Repeat12 Loop13 Call VISIT(P) /P 的左子树周游完 / if DATA(p)=name then pa(line,1)name;k2 while top0 and K hightR thenreturnreturn +
56、hightL; ;elseelsereturnreturn +hightR; ; endifend TREEHEIGHT35、编写计算二叉树最大宽度的算法二叉树的最大宽度是指二叉树所有层中结点个数的最大值 。( (见见 3232 题第题第 2 2 问问) )回溯法回溯法36、组合问题求出从自然数1，2，n 中任取 r 个数的所有组合。采用回溯法找问题的解，将找到的组合以从小到大顺序存于a0，a1，ar-1中，组合的元素满足以下性质：1ai+1a，后一个数字比前一个大；2a-i=n-r+1。按回溯法的思想，找解过程可以表达如下：首先放弃组合数个数为 r 的条件，候选组合从只有一个数字 1 开始。
57、因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件1 ，候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a2上的 3 调整为 4，以及以后调整为 5 都满足问题的全部要求，得到解1，2，4 和 1，2，5。由于对5 不能再作调整，就要从 a2回溯到 a1，这时，a1=2，可以调整为 3，并向前试探，得到解 1，3，4。重复上述向前试探和向后回溯，直至要从a0再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下：【程序】# defineMAXN100int aMAXN;vo
58、id comb(int m,int r)int i,j;i=0;a=1;do if (a-i=m-r+1if (i=r-1)for (j=0;j 0 and x( (1)=)=n r+ +1 dodo/将r个数按升序入到数组中的话， 则X(1)不会大于n-r+1X( (k)+)+ifif X( (k)=) 0 dodo X ( (k)+)+whilewhile X( (k)=)=m andand notnot MOVE( (k) ) dodo/此种渡法是否可行 X( (k)+)+ repeatifif X( (k)=)=m then/找到一种摆渡法ifif R( (k)=()=(M, ,M)
59、) thenifif k =h then /当进行的步数大于当前的步数时，则回溯，进行树的截枝 kelseelse k+ X( (k) )0 endif endifelseelse k endif repeat print ( (X, ,L, ,R) )/输出最优即最短步法end Processprocedure MOVE( (k) )/确定第 k 步的渡法,默认是从左岸到右岸的，右岸到左岸只需乘-1/ X(k)值表示第种渡法，为方便起见，可以事先将其存到一个数组中T(1:5,1:2)=1,0),(0,1),1,1,2,0,0,2/ 1 2 3 4 5/教士 1 0 1 2 0/野人 0 1
60、1 0 2/ integer T ( (1: :5, ,1: :2) )1, ,0),(),(0, ,1),),1, ,1,2, ,0,0, ,2 integer a , ,b a T( (X( (k),),1) ) /第 k 步摆渡实际人数 b T( (X( (k),),2) )ifif ISEVEN( (k) ) then /k 是奇数的话，船是左右开,是偶数的话，船右左开 a = =a*(*( 1) ) b = =b*(*( 1) ) endif L ( (k) )( (L( (k 1, ,1) ) a, ,L( (k 1, ,2) ) b) ) /将左右岸的人数调整到摆渡后的人数 R
61、( (k) )( (R( (k 1, ,1)+)+a, ,R( (k 1, ,2)+)+b) )ifif L( (k, ,1)M oror L( (k, ,2) ) oror L( (k, ,1)0 oror L( (k, ,2)0 then /只需考虑左岸人数是否在合理范围内returnreturn( (FLASE) ) endififif L( (k, ,1)0 andand L( (k, ,1)!=)!=L( (k, ,2) ) then /只要有一岸野人人数大于教士人数就不可行,左岸人数只能是(m,0),(0,m),(t,t)三种情况returnreturn( (FLASE) ) en
62、difforfor ik to 0 by1 dodo/查看是否有与以前重复的状态ifif L( (i)=)=L( (k) ) thenreturnreturn( (FALSE) ) endif repeatreturnreturn( (TRUE) )end MOVE38、某乡有 n 个村庄，有一个售货员，他要到各个村庄去售货， 各村庄之间的路程 s 是已知的，且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 1。试设计一个算法，帮他选择一条最短的路。求解思路： 可以用递归和非递归的方法求解。 递归的方法：
63、 用一个过程 road(step， position)来描述走的状况，其中 step 是当前已到村庄数、position 是当前所在的村庄。如果 stepn， 下面只能回起点了， 直接看第 position 个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存)。如果 step 还小于 n，那么将还没有到过的村庄一个一个地试过去， 再调用下一步road(step+1， 新到的村庄号)。procedure ROAD( (step) )/第 step 步所走过的村子，用一个全程数组 X(1:n)来表示第 step 所到的村子，T(1:n)表示是第某个村子是
64、否经过1 表示经过，0 表示未经过，S1:n,1:n)表示两个村子间的距离， 表示 cw 表示当前所经过村子的距离,bestw 表示最短距离 最开始时设为 MAX ， XX(1:n)用来记录最短走法;该算法在主程序中的调用时，cw=0,bestw=MAX,T0,ROAD(1)，此方法假设所有村庄都可达global integer A(1:n),T(1:n),cw,bestwifif step n thencwcw+ +S( (X( (n),),1) )/加上从最后一个村子回来时的距离ifif cw bestw then/是否为最短距离XXX /记录最短走法bestwcw endif eniff
65、orfor j1 to n dodo then /第 step 步能走的村子ifif T( (j)=)=0 then/该村子是否经过过 T( (j) )1 X( (step) )jcwcw+ +S( (X( (step 1),),j) ) /距离加上上个村子到该村的距离 call ROAD( (step+1) ) T( (j) )0 /回溯 X( (step) )0cwcw S( (X( (step 1),),j) ) endif repeatend ROAD39、设某一机器由 n 个部件组成，每一种部件都可以从 m 个不同的供给商处购得。设 wi,j是从供给商 j 处购得的部件 i 的重量，
66、ci,j是相应的价格。试设计一个算法，给出总价格不超过 c 的最小重量机器设计。procedure BKNAPTRACK( (i) )/某一机器由 n 个部件组成， 每一种部件都可以从 m 个不同的供给商处购得， W(i,j)表示从第j 个供给商的部件 i 的重量(1=i=n,1=j n thenifif cp sum then/假设当前选法用价格比最小的更小时sumcp XX= =X /记录最小的厂商选法 endifreturnreturnforfor j= =1 to m dodo/每个厂商的零件都试一次ifif cw+ +W( (i, ,j) n andand count cost th
67、encostcountreturnreturn endifif count 0 dodo X ( (k)=)=X( (k)+)+1whilewhile X( (k) )m andand notnot MOVE( (k) ) dodo X( (k)=)=X( (k)+)+1 repeatifif X( (k) )m thenifif k= =64 then print( (X, ,S) ) returnreturnelseelse k= =k+ +1/此处未判是否越界，即栈溢出。/ X( (k)=)=0 endifelseelse k= =k 1 endif repeatEND 骑士巡游Proc
68、edure MOVE( (k) ) integer t , , Icasecase: :X( (k)=)=1: : S( (k)=()=( S( (k 1, ,1) ) 2, , S( (k 1, ,2)+)+1 ) ): :X( (k)=)=2: : S( (k)=()=( S( (k 1, ,1) ) 1, , S( (k 1, ,2)+)+2 ) ): :X( (k)=)=3: : S( (k)=()=( S( (k 1, ,1)+)+1, , S( (k 1, ,2)+)+2 ) ): :X( (k)=)=4: : S( (k)=()=( S( (k 1, ,1)+)+2, , S(
69、(k 1, ,2)+)+1 ) ): :X( (k)=)=5: : S( (k)=()=( S( (k 1, ,1)+)+2, , S( (k 1, ,2) ) 1 ) ): :X( (k)=)=6: : S( (k)=()=( S( (k 1, ,1)+)+1, , S( (k 1, ,2) ) 2 ) ): :X( (k)=)=7: : S( (k)=()=( S( (k 1, ,1) ) 1, , S( (k 1, ,2) ) 2 ) ): :X( (k)=)=8: : S( (k)=()=( S( (k 1, ,1) ) 2, , S( (k 1, ,2) ) 1 ) ) endcas
70、eifif S( (k, , 1)8 oror S( (k, , 2)8 oror S( (k, , 1)0 oror S( (k, , 2)0 thenreturnreturn( (FALSE) ) endifforfor i= =k1 to0 by1dodoifif S( (i)=)=S( (k) ) thenreturnreturn( (FALSE) ) endif repeatreturnreturn( (TRUE) )END MOVE哈密顿环哈密顿环( (补充补充) )/在使用前首先初始化邻接矩阵 GRAPH(1:n,1:n),然后置 X(2:n)0,X(1)=1,再执行call H
71、AMILTONIAN(2)procedure HAMILTONIAN( (k) )/这是找出力 G 中所有哈密顿环的递归算法。图 G 用它的布尔邻接矩阵 GRAPH(1:n,1:n)表示，每个环都从结点 1 开始/ global integer X ( (1: :n) ) local integer k , ,n loop /生成 X(k)的值 call NEXTVALUE ( (k) )/下一个合法结点分配给 X(k)/ifif X( (k)=)=0 then returnreturn endif/找到下一个点，回溯/ifif k= =n then print( (X, ,1) )/打印一个
72、环/elseelse call HAMILTONIAN( (k+ +1) ) endif repeatend HAMILTONIANprocedure NEXTVALUE( (k) )/X(1),X(2),X(k-1)是一条有 k-1 个不同结点的路径。假设 X(k)=0,则表示再无结点可分配给 X(k)。假设还有 X(1),X(k-1)不同且与 X(k-1)有边相连接的结点，则将其中票数最高的结点置于 X(k)。假设 k=n，则还需要与 X(1)相连接；其中 GRAPH(1:n,1:n)表示两个结点是否相连/ global integer X ( (1: :n),),boolean GRAP
73、H( (1: :n, ,1: :n) ) integer k , ,j loop X ( (k) )( (X( (k)+)+1) )mood( (n+ +1) )/下一个结点ifif X( (k)=)=0/找不到一个合法的边 then returnreturn endififif GRAPH( (X( (k 1),),X( (k) then /X(k-1)和 X(k)是否相连forfor j1 to k 1 dodoifif X( (j)=)=X( (k) ) then/是否有重复的点breakbreak endififif j= =k then/没有重复点 thenifif k n oror ( (k= =n andand GRAPH( (X( (k),),1)/找到一个合法的下一个结点 thenreturnreturn endif endif endif repeatend NEXTVALUE
