算法分析与设计习题集答案

1、算法分析与设计习题集根底篇1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：就是一组有穷的规那么，它规定了解决某一特定类型问题的一系列运算书上定义 特征：输入、输出、有穷性、明确性、有效性区别：算法是完成特定任务的有限指令集。程序是用电脑语言编写的写成特定任务的指令序列。2、算法的时间复杂度指的是什么？如何表示？算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大0符号表述，不包括这个函数的低阶项和首项系数。百度百科3、算法的空间复杂度指的是什么？如何表示？一个程序的空间复杂度是指运行完一个程序所需内存的大小

2、。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储 一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两局部。1固定局部。这局部空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间即代码空间、数据空间常量、简单变量等所占的空间。这局部属于静态空间。2可变空间，这局部空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n )=0(f( n)其中n为问题的规模，S

3、(n)表示空间复杂度。4、什么是最坏时间复杂性？什么是最好时间复杂性？ 答：最坏情况时间复杂性：匚的=唸 二益 Z疑刀=g坍(凡门=T(N. /*)最好情况时间复杂性：I*是DN中使T(N, I*)到达Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率5、什么是递归算法？什么是递归函数？递归算法包括直接递归和间接递归子程序都是通过自己调用自己， 将求解问题转化成性质相同的子问题，最终到达求解的的。 递归算法充分地利用了电脑系统内部机能，自动实现调用过程中对相关且必要的信息的保存与恢复，从而省略了求解过程中的许多细节的描述。【课本】直接递归 子程序在运行完成前调用它们自己。间接递

4、归子程序在运行过程中调用其它子程序，其他子程序反过来调用这个调用子程序。递归函数，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。网上：答：1递归算法：直接或间接地调用自身的算法；2递归函数：用函数自身给出递归定义的函数。6、分治法的设计思想是什么？将整个问题分成假设干个小问题后分而治之给定一个有n个输入的函数，分治策略建议将输入分为k个不同的子集，1<kw n,从而产生k个子问题。当输入规模n取值较大时，可以将这 n个输入分成k 1<kw n个不同子集合的情况下，得 到k个不同的可独立求解的子问题，求出这些子问题的解之后， 再用适当的方法把

5、它们合并成整个问题的解。这就是分治法。如果子问题仍然较大，可以再次使用分治策略。更精确地说，分治策略将输入划分为与原问题同类型的k个子问题。许多时候，k=2。7、动态规划根本步骤是什么？答：1找出最优解的性质，并刻划其结构特征;2递归地定义最优值；3以自底向上的方式计算出最优值 ；(4)根据计算最优值时得到的信息，构造最优解。8、回溯法与分枝限界法之间的相同点是什么？不同之处在哪些方面？ 答：同：他们同是在问题的解空间树上搜索问题解的算法；异：1求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而 分支限界法的求解目标那么是找出满足约束条件的一个解，或是在满足约束条件的解中找出在

6、某种意义下的最优解；2搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法那么以广度优先或以最小消耗优先的方式搜索解空间树。9、分枝限界法的根本思想是什么？答：分支限界法常以广度优先或以最小消耗最大效益优先的方式搜索问题的解空间树。10、限界函数的功能是什么?答：用限界函数剪去得不到最优解的子树11、设某一函数定义如下：p- K-10K>100M (x) - *M CM Cx+1D) x 100编写一个递归函数计算给定x的M x的值。本函数是一个递归函数，其递归出口是：M x= x-10x>100递归体是：M M x+11x < 100实现此题功能的递归函数如下：

7、in tm ( intx ) int y;if ( x>100 )return(x-1O );else y =m(x+11);return (m (y );procedure M(x)if x >100the nreturn(x- 10)elsereturnM ( M( x + 11 )en difend M12、一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值 相同的元素。此题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比拟相邻两个元素，假设值相等，那么删除其中一个，否那么继续向后查找，直到最后一个元素。实现此

8、题功能的函数如下：voiddel ( seqlist*a )in ti=0, j;while ( i<a->le ngth)if ( a->datai!= a->datai+1)i+;elsefor ( j=i; j<a->le ngth; j+)a_>dataj=a_>dataj+1;a->le ngth-;procedure del ( A, LINK , n)A(1: n)是元素按元素值非递减有序排列的顺序表，LINK(1: n)每个数的下一个数所在的下标，等于 0时表示后面再没有数了，初始时为2，3，4n,0global integ

9、er A( 1 ： n), LINK ( 1： n)integer i, j ;i 1;while LINK ( i )> 0 doj LINK ( i )while j <n and A ( i )= A( j ) do/查找是否为相同的数j LINK(j);repeatLINK (i ) -j ; 将i的LINK指向j ,忽略中间相同的数i- j ;repeatend del13、分别写出求二叉树结点总数及叶子总数的算法。计算结点总数int Cou ntNode(Bi nTree *root)int nu m1, nu m2;if(root=Null) return(0);el

10、se if(root->lchild=Null&&rooot->rchild=Null)return(1);elsenu m仁Co un tNode(root->lchild);nu m2=Co un tNode(root->rchild);retur n(nu m1+ nu m2+1);procedure COUNTNODE ( T)/T 是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILDinteger num1, num2 ;if T != 0 thenif LCHILD ( T)= 0 and RCHILD ( T)= 0

11、 then / 既没有左孩子，也没有右孩 子，那么为叶子节点return ( 1);elsenum1=COUNTNODE LCHILD ( T);num2=COUNTNODE RCHILD ( T);return(num1 + num2+1); II将左右子树的结点数加起来，再加本身，相当时树的后序遍历en dfien difreturn ( 0);end COUNTNODE计算叶子总数int Coun tLeafs(B in Tree *root)int nu m1, nu m2;if(root=Null) return(O);else if(root->lchild=Null&

12、;&root->rchild=Null)return(1);elsenu m1=Co un tLeafs(root->lchild);nu m2=Co un tLeafs(root->rchild);retur n(nu m1+ nu m2);procedure COUNTLEAFS ( T)T 是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILDinteger num1, num2 ;if T != 0 thenif LCHILD ( T)= 0 and RCHILD ( T)= 0 then / 既没有左孩子，也没有右孩 子，那么为叶子节点

13、return ( 1);elsenum1=COUNTLEAFS( LCHILD ( T);num2=COUNTLEAFS( RCHILD ( T);return(num1 + num2 ); /将左右子树的结点数加起来，再加本身，相当时树的后序遍历en dfien difreturn ( 0); /T 为空时，没有结点end COUNTLEAFS分治术14、有金币15枚，其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假的金币找出来，试设计一种算法方案，使在最坏情况下用天平的次数最少。procedure SELECKP ( p, q)A 是一个全程数组，分别表示n个硬币的重量，在此题中

14、表示15个硬币；p和q表示假币所在的一组硬币的起始和终止编号；最后返回硬币的编号；在主程序中调用SELECKP(1,15)if p=qthe nreturn (p);en dif;global ingeger A( p: q);integer a, b, c, d, m;ap; /第一组数的起始编号dq; /第二组硬币的终止编号n0; /最多余的一个硬币所在的编号if ( ISODD (q- p+1) /如果该组硬币数量为d奇数the n mq; /最后一个数不作比拟dd- 1 ;edifc ( a + d + 1)/ 2; /第二组硬币的起始编号编号bb- 1 ; /第一组硬币的终止编号/将

15、该组硬币分为平均分为两组，然后用天平比拟两组重量，将轻的一组递归调用本方法If WEIGHT( a, b)< WEIGHT( c, d)thenreturn( SELECKP( a, b);else if WEIGHT(a, b)> WEIGHT(c, d)thenreturn( SELECKP( c, d);else if m!= 0/假设两组硬币重量相等，那么剩下一个为假币return ( m);else /如果两组硬币重量相等，且没有不比拟的硬币，即本次检查的硬币总数为偶数，表示没有硬币print("没有假币“)；return (0);en difend SELEC

16、KP15、利用分治策略，在 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; 对于k<m<=n,有 A(m)>=t.A(n+1)=+ g/integer n, k, m, r, j ;n 1r n1 ; A( n +1) + gloop/每当进入这一循环时，1<=m<=r<=n+1j r将剩下的元素的最大下标加1后置给j/ca

17、ll PARTITIONcase(m, j ) /返回j ,它使得A(j)，它使得A(j)是第j小的值:k=j : return/找到该元素该元素为A(j):kvj : r j /j是新的上界,k在m与j之间:else : nj + 1/j+1是新的下界，k在j+1 与m之间endcaserepeatend SELECTprocedure PARTITION( m, p)integer m, p, i ; global A ( m p- 1);vA m); i m; A(m) 是划分元素 / looploop i i +1 un til A(i )> =v repeat/i由左向右移lo

18、op p p - 1un til A(p)< =v repeat/p由左向右移if i <p- 1then call A(i)?A(p) /A(i)和 A(p)换位else exiten difrepeatA ( 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个队所比赛的对手，假设轮空那么为0glob

19、el integer A( 1: n, 1 : n)if n =1 the nA (1, 1)= 1;return ;en difif ISODD (n) then /当队数为奇数时，增加一个虚拟队员TOURNAMENT (n + 1);return ;en difTOURNAMENT (n/ 2); /是偶数时，递归调用，返回时合并call MAKECOPY ( n); /主要是将左上角的递归计算岀的小块中的所有数字按照其相 对位置抄写到右下角，将左上角小块中的所有数字加n/2后按照其相对位置抄写到左下角，将左下角小块中的所有数字按照相对位置抄到右上角。end COUNTLEAFS17、序列

20、503 , 87, 512, 61, 908, 170, 897, 275, 652, 462，写一个自底向上的 归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。void Merge(ElemType *r , ElemType *rf , int u , int v , int t)for(i=u , j=v , k=u ； i<v&&j<=t ； k+) if(ri.key<rj.key) rfk=ri ； i+ ； else rfk=rj ； j+ ； if(i<v) rfk t=ri v-1;if(j<=t) rfk t=r

21、j t;void MergeSort(S_TBL *p , ElemType *rf) /*对*p表归并排序，*rf为与*p表等长的辅助数组*/ElemType *q1 , *q2 ;q1=rf ; q2=p->elem;for(len=1 ; len<p->length ; len=2*len)/* 从 q2 归并到 q1*/ for(i=1 ; i+2*len-1<=p->length ; i=i+2*len)Merge(q2 ,q1, i, i+len,i+2*len-1) ;/* 对等长的两个子表合并 */if(i+le n-1<p->le n

22、gth)Merge(q2 ,q1, i, i+len,p->length) ;/* 对不等长的两个子表合并*/else if(i<=p->le ngth)while(i<=p->le ngth)/*假设还剩下一个子表，那么直接传入*/q1i=q2i;q1<->q2 ;/*交换，以保证下一趟归并时，仍从 q2归并到q1*/if(q1!=p->elem)/*假设最终结果不在*p表中，那么传入之*/for(i=1 ; i<=p->length ; i+)p->elemi=q1i;high- low+1 >0个待分类的元素/Pro

23、cedure MERGESORT ( low , high )/A(low : high)是一个全程数组，它含有Integer low, high ;If low< high the ncall MERGESORT(low,mid )call MERGESORT(mid+1 , highcal MERGE(low,mid ,high )Endifmid int ( low +high )/ 2)/求这个集合的分割点/将一个子集合分类)/将另一个子集合分类/归并两个已分类的子集合/ en dMERGESORTProcedure MERGEA(low: high)中的已分类的子集合。中/(l

24、ow , mid , high )是一个全程数组，它含有两个放在Alow : mid和A mid+1 : high/使用一个辅助数组In teger h,B(low : high)/,j , k , low , midhigh/low < mid<highGlobal A:high ); local B(low;/A中第一队列的队头 /第三队列，即B的队头(low : high )mid + 1 ; /A中第二队列的队头< high (whileifthe nh< mid and jA(h) <A(j )B(i )A( h);do/hT+1当两个集合都没有取尽时

25、elseB (i )目标是将这两个已分类的集合归并成一个集合，并存放到A(low : high)en difi i+1repeatif h >mid then/处理剩余的元素/forkj to high do /第二队列未处理完(i ) A( k); i i + 1repeatElsefork h to mid(i ) Tk);do/第一队列未处理完i i + 1repeat en difdo /将已归并的集合复制到A/for k low to highA ( k) B( k) repeat en dMERGE归并过程黄色底纹的是每次归并的数123456789100503|8751261

26、9081708972756524621875035126190817089727565246228750351261908170897275652462387503512619081708972756524624618750351290817089727565246256187503512908170897| 27565246266187503512908170275897652462761875035129081702758974626528618750351290817027546265289796187170275462503512652897908贪心法1个磁道。这18、设有n个文件f

27、l, f2,，fn要求存放在一个磁盘上，每个文件占磁盘上nn个文件的检索概率分别是pi, P2,，pn,且 pi =1。磁头从当前磁道移到被检索信i 1息磁道所需的时间可用这两个磁道之间的径向距离来度量。如果文件fi存放在第i道上，K i w n那么检索这n个文件的期望时间是pipjd(i, j)。其中d(i , j)是第i道与第j1 i j n道之间的径向距离。磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间到达最小。试设计一个解此问题的算法，并分析算法的正确性与计算复 杂性。磁盘文件最优存储问题具有贪心选择性质：先将n个文件从大到小按概率进行排序。假设排序后有p1

28、>=p2>=>=pn。贪心选择性质表示每次所选择参加的对象文件，都能得到当前的最优值，即使得期望检索时间到达最小。在磁盘最优存储问题中，要想使期望检索时间到达最小。那么就要使两个概率较大者的径向距离越小越好。因此第一次从 p1>=p2>=>=pn 中选取P1所对应的文件f1置于中心磁道上。随后从剩余概率队列中选取概率最大和次最大者所对应的文件放 在靠着f1的左磁道，和f1的右磁道。这将得到初始的最优值。同样地，继续选择剩余概率队 列中概率最大和次最大者所对应的文件分别置于靠着刚刚所得最优位置的左磁道和右磁道上，将得到新的最优值。所以磁盘最优存储问题具有贪心选

29、择性质。最优子结构性质：按照这 n个文件的排序概率(p1>=p2>=>=pn)假设排序后的理想最优序列为：fn-1 丨，f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,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)f

30、4,f2,f1,f3,f5,f(i)f(n -2),fn。该序列是原序列对调f(i) 与f(j)的位置所得。该序列所得到的期望检索时间小于上面的贪心策略时间。经验证发现，该序列所获得的期望检索时间>原所获得的期望检索时间。与最优值相矛盾。故贪心解为最优解。*/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

31、n/ 2;/取中间位置，除法为向下取整/X ( k) A( 1);/中间位置放概率最大的文件/for i 2 to n by +2 doX ( k+i / 2) A( i );repeatfor i 3 to n by +2 doX ( 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

32、;string B( 1: n), sfor i 1 to n - 1 dofor i 1 to n doa STRINT( B( i ), B(j );b STRINT(B(j), B( i );for a <b thencall INTERCHANGE( B( i ), B( j );/将字符串拼接再转化为字符串en difrepeatrepeatfor i 1 to n do /将B按顺序拼接起来主为最大的整数ss + B( i )end SORTTN20、键盘输入一个高精度的正整数N此整数中没有 0',去掉其中任意 S个数字后剩下的数字按原左右次序将组成一个新的正整数。编

33、程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小输出应包括所去掉的数字的位置和组成的新的正整数，N不超过240位。/*最优解是删除岀现的第一个左边>右边的数，因为删除之后高位减小，很容易想那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解.*/procedure GreedyDelet( N, S, X)N表示高精度的正整数此整数中没有0'，要去掉S个整数，X(1:s)表示删除数字的位置real X ( 1: s)char * nt N; /把整数转化为字符串处理in teger s S;while s >0 doi

34、 =0;/从串首开始while i <length ( nt ) and n i < n i +1 doi+；repeatdelet( nt , i ); Illi 删除串n的第i个字符s-；X( S-s) i ;repeatprint(X); II输岀每次删除的位置print( nt ); II输岀最后组成的新的整数end GreedyDelet21、对于以下图给出的有向网，写出用 Dijkstra方法求从顶点 A到图中其它顶点的最短路 径的算法，并写出执行算法过程中顶点的求解次序及从顶点A到各顶点路径的长度。procedure SHORTEST - PATHS( v, COST

35、, DIST , n) G 是一个 n 结点的有向图，它由其成本邻接矩阵COST(n,n) 表示DIST(j) 被置以结点v到结点j的最短路径长度，这里1<=j<=n;DIST(v)被为 0boolean S( 1 ： n); real COST( 1: n,1: n), DIST ( 1 : n)integer u, v, n, num, i , wfor i 1 to n do II将集合S初始化为空S ( i ) 7DIST (j ) COST( v, j );repeatS ( v) 1 ; II将结点v计入集合SDIST ( v) 0;for num 2 to n - 1

36、 do /确定由结点 v岀发的n-1 条路选取结点u，它使得在 S( w)= 0的条件下，DIST ( u)= min DIST ( w)S (u) 1 ; II结点计入Sfor 所有S( w)= 0的结点 w doDIST( w) min ( DIST ( w), DIST ( u)+ COST( u , w)repeatrepeatend SHORTEST - PATHSABCDEFGA048+ x1528+ x40B+x012+ x+x+ x+ xC+x+ x043+x13+ xD+x+ x+ x0183323二+x+ x33+ x0+ x+ xF+x+ x9+ x+x0+ xG+x+

37、x+ x+ x+x200执行踪迹迭代选取的 结点SSABCDEFG置初值-A048+x1528+ x401DA,D048+x152848382EA,D,E04861152848383GA,D,E,G04861152848384BA,D,E,G,B04860152848385FA,D,E,G,B,F048571528483822、对于上图给出的有向图，写出最小本钱生成树，给出求解算法。Line procedure KRUSKAL( E, COST, n, T , min cost)G有n个结点，E是G的边集，COST u, v丨是边u, v丨的本钱。T是最小本钱生成树 的边集，min cost是

38、它的本钱。/1 real min cost, COST ( 1: n ,1: n )2 integer PARENT( 1 ： n), T ( 1 : n- 1 , 2), n3 以边本钱为元素构造一个min -堆4 PARENT - 15 i min cost T6 while i <n - 1 and 堆非空 do7 从堆中删去最小本钱边(u, v )并重新构造堆8 j FIND(u); k FIND(v)9 if j 工 k then i i +110 T( i ,1) u; T ( I , 2) v11 min cost min cost +COST( u, v )12 call

39、 UNION(j , k )13 en dif14 repeat15 if i 工 n-1 then print ( ' no spanning tree ') endif16 return17 end KRUSKAL动态规划23、求出上图中每对结点间的最短距离的算法，并给出计算结果。lineprocedure ALL-PATHS( COST,A , n )in teger i,j , k , n ; real COST( n, n ), A ( n, n )1for i 1 to ndo2for j 1to ndo3A (i ,j )COSTi ,j)4repeat5repe

40、at6for k 1 to ndo7for i 1to ndo8forj 1 to ndo9A(i , j ) min A( i , j),A (i , k)+ A( k, j )10 repeat11 repeat12 repeat13 end ALL - PATHSABCDEFGA0485715284838Boo01255732578CooOO043611366Doooo420183323Eoooo337604699Foooo95270075Goooo29729020024、以下图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道 路，连线上的数值代表道路的长度。现在，想

41、从城市A到达城市E,怎样走路程最短,最短路程的长度是多少 ？line procedure FGRAPH( E, k , n , P )/多段图的向前处理算法，输入是按照段的给结点编号的，有n个结点的k段图。E是边集,c(i,j)是边(i,j)的本钱。P(1:k)是最小本钱路径/1real COST( n), integer D(n-1), P(k),r , j , k , n2COST (n) 03forj n- 1 to 1 by - 1do4设r是一个这样的结点，<j , r > E 且使c( j , r )+ COST( r)取最小值5COSTjc(j , r )+ COST

42、( r)6D (j ) r7 repeat /找一条最小本钱路径8 P (1) T; P( k) n9 forj 2 to k -1 do/找路径上的第 j个结点10 P(j ) DP(j - 1)11 repeat12 end FGRAPH最短路程:1 3 7 10 11 (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; /以第

43、a1为末元素的最长递增子序列长度为1 ;for i 2 to n do/ 循环 n-1 次f(i ) 1; /f(i) 的最小值为1 ;for j 0 to i do / 循环 i 次if A (j )< A( i ) a nd f(j )> f ( i )- 1 then / 选岀最大的 f(j)f( i ) f(j )+1;/ 更新 f(i)的值。en difrepeat repeatreturnf ( n - 1)end lis这个算法有两层循环，外层循环次数为n-1次，内层循环次数为i次，算法的时间复杂度所以T(n)=0(n2)。这个算法的最坏时间复杂度与第一种算法的阶是相

44、同的。算法二：改进后算法procedure lisl(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分别为二分查找的上界，下界和中点；for i = 1 to n dop =0; r =len ;while p <= r do/二分查找最末元素小于ai+1 的长度最大的最大递增子序

45、列；m= ( p+r)/ 2;if B m< A i the n p= m +1 ;else r = m - 1;en difrepeatB p = A i ; /将长度为p的最大递增子序列的当前最末元素置为ai+1;if ( p>len )then len+; /更新当前最大递增子序列长度；en difrepeatreturn len ;end lis1算法的循环次数为n ,每次循环二分查找用时logn ，所以算法的时间复杂度为0(nlogn)。这个算法在第二种算法的根底上得到了较好的改进26、 设计一个0n2时间的算法，找出由 n个数组成的序列的最长的单调递增子序列。上题算法一

46、27、旅游预算问题。一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有假设干加油站，每个加油站收费不一定相同。 旅游预算有如下规那么： 假设油箱的油过半, 不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加 油时，司机要花费 2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出 时在起点加满油箱；计算精确到分1元=100分。编写算法估计实际行驶在某路线所需的最小费用。Procedure LESTCOST ( v, vm, f , n, S, FP, P)/共n个加油站，起点、加油站、和终点，分别编号为0,1,2n,n+1, v为油箱容量,vm为每升油

47、行驶的公里数，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 , k;float vf ;i =0; vf =0;LEST MAXLEST ( 0) fwhile i <n + 1 doj =i +1while j <n + 1 and S (j )- S( i )< 1/ 2* v* vm do/ 剩余油量还剩一大半时j j- 1rep

48、eatif S (j )- S(i )> v* vmthen j j - 1;en difif j <= i then print("不可能到达终点 )returnendifif j =n then /到达终点con ti nue;en difk =j ;while j <n + 1 S (j )- S( i )<= v* vm/油够到达该站并停车vf=( S( j )- S( i )/ vm/需要补充的汽油量cost=LEST(i )+ vf *FP(j )+ 2/在j站停车的最小血糖if cost < LEST (j ) the nLEST(j )=

49、 costN(j )= ien difj =j +1repeati =k;repeat从k到n到到t，使LEST (t )最小P ( n)= n;p (n -1)=jwhile j >0P(j -1)= F(P(j );j=P(j - 1);enifenif此题的求解与求有向图的最短路径比拟相似，也是选取两点间的直接连线费用和经过某个中间结点进行转折费用中的最小者。因此，求总费用的最小值可以分解为求假设干分段的费用最小值，它满足优化原那么，所以此题可以采用动态规划的方法进行求解。For in terval:=1 to n-1 to dofor start:=0 to n-1 doif s

50、tart+i nterval<=n the nBeginStop:=i nterval+start;If从start能直接到stop thenBeginLeststart,stop:=从 start 能直接到 stop 的费用；Nextstopstrat,stop:=stop;End;求出直接从start到stop的费用一 For n ext:=start+1 to stop-1 doIf从start能直接到 next thenBeginCost:=从start到next的费用+从next到stop的费用；If cost<leststart,stop the nBeg inLest

51、start,stop:=cost;Nextstopstart,stop:=next;En d;End;中间经过next是否能减少费用End;动态规划的求解过程然后，从各油站中找到能直接到终点，而且从起点到该站的lest值最小的油站stop。那么该旅程的最小费用为该lest值加上在起点的费用。 然后利用下面的迭代式就可以求出，中途所停的油站：start:=0; start:=nextstopstart,stop;直至U start=stopA->E。试用动28、以下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由 态规划的最优化原理求出A->E的最省费用。20ft根本的多段图问题略A->B1(5)->C1(6)->D1(3)->E(5),最短的距离为 1929、如以下图，写出用动态规划求最短路径的递推关系式，并写出求从源点 A0到终点A3的最短路径过程。给出求解算法。6根本的多段图问题略COST(2,A1)=mi n(6+COST(3,A2),5+COST(3,B2)=8OCST(2,B1)=mi n( 4+COST(3,