第四讲动态规划精选文档.ppt

《第四讲动态规划精选文档.ppt》由会员分享，可在线阅读，更多相关《第四讲动态规划精选文档.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本讲稿第一页，共五十九页n 主要内容主要内容 动态规划的基本原理动态规划的基本原理动态规划的基本原理动态规划的基本原理动态规划的递推方法动态规划的递推方法动态规划的递推方法动态规划的递推方法 经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例n 重点重点 最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法n 难点难点具体问题的动态规划算法具体问题的动态规划算法具体问题的动态规划算法具体问题的动态规划算法本讲稿第二页，共五十九页一、多段图问题一、多段图问题k

2、 k 段有向图段有向图G=(V,E),|V|=n;V=V1,V2,Vk;uVi,vVi+1,1ik-1,E:c(u,v)求求s到到t的成本最小的路径的成本最小的路径s,v2,v3,v4,t，其中其中,viVi。132546879111012stV1V2V3V4V54.1 基本原理基本原理本讲稿第三页，共五十九页求解方案初探求解方案初探1)1)穷举穷举穷举穷举2)2)多级决策多级决策多级决策多级决策:分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点v2,v3,v4v2,v3,v4132546879111012

3、stV1V2V3V4V5本讲稿第四页，共五十九页二、动态规划二、动态规划任务：任务：决策序列：决策序列：v1,v2,v3,v4,v5；v1=s,v5=t,viVi,i=2,3,4132546879111012stV1V2V3V4V5最优决策序列为路径长度最短的节点序列最优决策序列为路径长度最短的节点序列 s,v2,v3,v4,t确定一个多级决策问题的最优决策序列确定一个多级决策问题的最优决策序列本讲稿第五页，共五十九页状态转移过程状态转移过程状态转移过程状态转移过程状态序列状态序列s0s1sksn状态序列状态序列s0 x1xkxn决策序列决策序列本讲稿第六页，共五十九页最优性原理最优性原理最优

4、性原理最优性原理(最优子结构性质最优子结构性质)2)2)一个一个一个一个 n n 级级级级决策是最优的，则以第决策是最优的，则以第决策是最优的，则以第决策是最优的，则以第 k(kn)k(kn)级决策形成的状态作为级决策形成的状态作为级决策形成的状态作为级决策形成的状态作为初态的任何一个初态的任何一个初态的任何一个初态的任何一个 n-k n-k 级级级级的子决策也必然是最优的。的子决策也必然是最优的。的子决策也必然是最优的。的子决策也必然是最优的。三种表述三种表述1)1)对于一个多级决策问题的对于一个多级决策问题的对于一个多级决策问题的对于一个多级决策问题的最优决策最优决策最优决策最优决策来说，

5、无论过程的初始状态和初始决来说，无论过程的初始状态和初始决来说，无论过程的初始状态和初始决来说，无论过程的初始状态和初始决策是什么策是什么策是什么策是什么,其余的决策相对于初始决策所产生的状态必然构成一个其余的决策相对于初始决策所产生的状态必然构成一个其余的决策相对于初始决策所产生的状态必然构成一个其余的决策相对于初始决策所产生的状态必然构成一个最优决最优决最优决最优决策子序列策子序列策子序列策子序列。3)D(i,j)=D(i,k),D(k+1,j)3)D(i,j)=D(i,k),D(k+1,j)本讲稿第七页，共五十九页例：例：k段图问题的最优性原理说明段图问题的最优性原理说明假设：假设：v1

6、 vq vk是最短路径，是最短路径，那么：那么：v1 vq,vq vk也是最短路径。也是最短路径。本讲稿第八页，共五十九页递推方法递推方法递推方法递推方法1)1)递推的任务递推的任务递推的任务递推的任务3)3)向后递推向后递推向后递推向后递推确定决策向量 X=(x1,x2,xn)各分量的值2)2)向前递推向前递推向前递推向前递推本讲稿第九页，共五十九页4.2 多段图多段图(multistage graph)向前递推向前递推c(i,k)=arg minc+c(i+1,j)1iK-1,1k|Vi|,1j|Vi+1|向后递推向后递推c(i,k)=arg minc(i-1,j)+c2iK,1j|Vi-

7、1|,1k|Vi|kjt Vi Vi+1 vi,k vi+1,jc(i,k)c(i+1,j)c一、递推公式一、递推公式本讲稿第十页，共五十九页二、递推算法二、递推算法节点编号节点编号0 n-1,s.t.,k|kVik|kVi+1dn:各各节节点到点到t最小成本路径上的后向最小成本路径上的后向邻邻接接节节点点Cn:各节点到汇点的最短路径，各节点到汇点的最短路径，向前递推算法向前递推算法cii=n:E,cij0;pk:存存储储s到到t最小成本路径上的最小成本路径上的节节点点编编号号.本讲稿第十一页，共五十九页ForwardShortestPath(float cn,int k,int n)Forw

8、ardShortestPath(float cn,int k,int n)float Cn;int dn,pk;C0:n-2=MAX;Cn-1=0;float Cn;int dn,pk;C0:n-2=MAX;Cn-1=0;for(i=n-2;i=0;i-)for(i=n-2;i=0;i-)for(j=i+1;j=n-1;j+)for(j=i+1;j0)&(cij+Cj0)&(cij+CjCi)Ci=cij+Cj;Ci=cij+Cj;di=j;di=j;for(p0=0,pk-1=n-1,i=1;ik-1;k+)pi=dpi-1;for(p0=0,pk-1=n-1,i=1;ik-1;k+)pi=

9、dpi-1;时间复杂度时间复杂度:O(n2)O(n+e)邻接表邻接表 邻接矩阵邻接矩阵本讲稿第十二页，共五十九页向后递推算法向后递推算法ForwardShortestPath(float cn,int k,int n)ForwardShortestPath(float cn,int k,int n)float Cn;int dn,pk;C0=0;C1:n-1=MAX;float Cn;int dn,pk;C0=0;C1:n-1=MAX;for(i=1;i=n-1;i+)for(i=1;i=0;j-)for(j=i-1;j=0;j-)if(cji0)&(Cj+cji0)&(Cj+cji0;k-)

10、pi=dpi+1;i=k-2;i0;k-)pi=dpi+1;本讲稿第十三页，共五十九页例例4.1 把把 n 个资源分配给个资源分配给 r 个项目的问题个项目的问题,如果把如果把 0jn 个资源分配给个资源分配给项目项目 i,所获得的利润为所获得的利润为 N(i,j),要求使总利润最大化的分配方法。要求使总利润最大化的分配方法。r个资源分配问题的个资源分配问题的r+1段图模型段图模型:n=4n=4n=3n=2n=1n=0n=4n=3n=2n=1n=0n=0N(1,0)N(1,1)N(1,2)N(1,3)N(1,4)N(2,0)N(2,1)N(2,0)N(2,1)N(3,4)N(3,3)N(3,2

11、)N(3,1)N(3,0)本讲稿第十四页，共五十九页4.3 每对节点之间的最短路径长度每对节点之间的最短路径长度 一、问题描述一、问题描述cnn是是G的成本邻接矩阵的成本邻接矩阵求每对节点之间的最短路径长度求每对节点之间的最短路径长度A(i,j).G=(V,E)为为n节点的有向图节点的有向图123462113本讲稿第十五页，共五十九页二、递推公式二、递推公式k:k:编号最大的中间节点编号最大的中间节点编号最大的中间节点编号最大的中间节点Ak(i,j):最短路径长度最短路径长度令：令：递推公式递推公式向后逐级递推：向后逐级递推：A1(i,j),A2(i,j),An-1(i,j),An(i,j)最

12、短路径长度：最短路径长度：A(i,j)=An(i,j)123462113本讲稿第十六页，共五十九页 三、算法实现时需考虑的问题三、算法实现时需考虑的问题 1)1)怎样表示怎样表示怎样表示怎样表示“”“”2)2)怎样判断怎样判断怎样判断怎样判断 i i 到到到到 j j 是否存在最短路径是否存在最短路径是否存在最短路径是否存在最短路径3)3)怎样表示怎样表示怎样表示怎样表示 i i 到到到到 j j 最短路径上的节点序列最短路径上的节点序列最短路径上的节点序列最短路径上的节点序列本讲稿第十七页，共五十九页用动态规划法设计一个算法用动态规划法设计一个算法用动态规划法设计一个算法用动态规划法设计一个

13、算法,对对对对page123page123的图的图的图的图5.12,5.12,编程并上机实现求编程并上机实现求编程并上机实现求编程并上机实现求每对节点间的最短路径长度每对节点间的最短路径长度每对节点间的最短路径长度每对节点间的最短路径长度,输出路径上的节点序列输出路径上的节点序列输出路径上的节点序列输出路径上的节点序列.课外练习：课外练习：本讲稿第十八页，共五十九页4.4 最优二分检索树最优二分检索树(optimal binary search tree)(optimal binary search tree)本讲稿第十九页，共五十九页ifforwhilerepeatloop图(a)iffor

14、repeatloopwhile图(b)一、问题描述一、问题描述成功检索的平均比较次数成功检索的平均比较次数:图图(a)图图(b)12/511/54.4 最优二分检索树最优二分检索树(optimal binary search tree)(optimal binary search tree)本讲稿第二十页，共五十九页已知已知a1,a2,ana1a2anai的检索概率为的检索概率为P(i)假设假设a0=-,an+1=+aiXiai+1Xi的检索概率为的检索概率为Q(i)在整个检索空间在整个检索空间a0 X0 a1 X1 a2 X2,an-1 Xn-1 an Xn an+1本讲稿第二十一页，共五十

15、九页a2a1a5a4a3x0 x1x5x4x2x3检索的预期成本检索的预期成本检索的预期成本检索的预期成本最优二分检索树最优二分检索树使使cost(T)最小的二分检索树最小的二分检索树 本讲稿第二十二页，共五十九页二、递推方法二、递推方法最优二分检索树模型最优二分检索树模型最优二分检索树模型最优二分检索树模型akLR本讲稿第二十三页，共五十九页预期检索成本预期检索成本令：本讲稿第二十四页，共五十九页递推公式递推公式递推公式递推公式c(0,k-1)=cost(TL)c(k,n)=cost(TR)c(0,n)=cost(T)akLR本讲稿第二十五页，共五十九页构造步骤构造步骤1)1)令令令令 j-

16、i=1j-i=1，求，求，求，求c(i,j),W(i,j),r(i,j)c(i,j),W(i,j),r(i,j)r(i,j)：包含：包含Xi,ai+1,Xi+1,aj,Xj等节点的最优二分检索树的根等节点的最优二分检索树的根2)2)令令令令 j-i=2,3,nj-i=2,3,n，递推地求出所有，递推地求出所有，递推地求出所有，递推地求出所有c(i,j),W(i,j),r(i,j)c(i,j),W(i,j),r(i,j)3)3)根据根据根据根据 r(i,j)r(i,j)构造最优二分检索树构造最优二分检索树构造最优二分检索树构造最优二分检索树本讲稿第二十六页，共五十九页三、递推算法三、递推算法已知

17、已知 an:a0a1a2an-1;pn,qn.初始条件为初始条件为 wii=qi;cii=0,rii=0.计算所有的计算所有的 wij,cij,rij.本讲稿第二十七页，共五十九页OptRecursion(float*p,float*q,float cn+1,int rn+1)OptRecursion(float*p,float*q,float cn+1,int rn+1)float wn+1n+1;float wn+1n+1;for(i=0;i=n;i+)wii=qi;cii=0;rii=0;for(i=0;i=n;i+)wii=qi;cii=0;rii=0;for(i=0;i=n-1;i+

18、)for(i=0;i=n-1;i+)wii+1=qi+pi+1+qi+1;cii+1=wii+1;rii+1=i+1;wii+1=qi+pi+1+qi+1;cii+1=wii+1;rii+1=i+1;for(m=2;m=n;m+)for(m=2;m=n;m+)for(i=0;i=n-m;i+)for(i=0;i=n-m;i+)for(j=i+m,wij=qi,k=i+1;k=j;k+)wij+=pk+qk;for(j=i+m,wij=qi,k=i+1;k=j;k+)wij+=pk+qk;k=i+1;cij=cik-1+ckj+wij;rij=k;k=i+1;cij=cik-1+ckj+wij;

19、rij=k;for(k+;k=j;k+)for(k+;k=j;k+)if(t=cik-1+ckj+wij)cij)cij=t;rij=k;if(t=cik-1+ckj+wij)cij)cij=t;rij=k;时间时间复复杂杂度：度：本讲稿第二十八页，共五十九页四、由四、由 r(i,j)构造最优二分检索树构造最优二分检索树struct NODE KEYWORD key;struct NODE*lch,*rch;struct NODE*OptBinTree(i,j)struct NODE*T;if(j-ikey=arij;T-lch=OptBinTree(i,rij-1);T-rch=OptBin

20、Tree(rij,j);return T;本讲稿第二十九页，共五十九页例例 已知 n=4,(a1,a2,a3,a4)=(do,if,read,while),p(1:4)=(3,3,1,1),q(0:4)=(2,3,1,1,1)。w(i,j),c(i,j),r(i,j)的值为：j i01234w c rw c rw c rw c rw c r02 0 08 8 112 19 116 25 216 32 213 0 07 7 29 12 211 19 221 0 03 3 35 8 331 0 03 3 441 0 0r(0,4)=2r(0,1)=1r(2,4)=3r(3,4)=4本讲稿第三十页，

21、共五十九页4.5 0/1背包问题背包问题(0/1 knapsack problem)一、问题描述一、问题描述已知已知 M,n,wi,pi其中，其中，X=x1,x2,xn,xi0,1,pi0,wi0,0in.本讲稿第三十一页，共五十九页二、最优性原理二、最优性原理m(l,j,X)表示表示，xi0,1,pi0,wi0,lij.,s.t.,max0/1背包问题背包问题:最优性原理表述：设最优性原理表述：设 y1,y2,yn是是 m(1,n,M)的最优解，的最优解，那么，那么，y2,y3,yn必定是子问题必定是子问题 m(2,n,M-y1w1)的最优解。的最优解。m(1,n,M).本讲稿第三十二页，共

22、五十九页三、向后递推三、向后递推任务：任务：fi(X)：m(1,i,X)的最优解的最优解X0,f0(X)=-;X0,f0(X)=0.初始条件：初始条件：fi(X)=max fi-1(X),fi-1(X-wi)+pi 递推公式：递推公式：递推公式递推公式本讲稿第三十三页，共五十九页例例 n=3,W=(2,3,4),P=(1,2,5),M=6.f0(X)=-0X0X0f1(X)=-max0,-+1=0max0,0+1=1X00X2X2f2(X)=-max0,-+2=0 max1,-+2=1max1,0+2=2max1,1+2=3X00X22X33X5X5 f3(M)=max3,1+5=6M=6fi

23、(X)=max fi-1(X),fi-1(X-wi)+pi X=(1,0,1)本讲稿第三十四页，共五十九页 1 2 3 4 5 6 7 x12f0(x)=0 1 2 3 4 5 6 7 x12f0(x-w1)+p1 1 2 3 4 5 6 7 x12f1(x)图解说明图解说明图解说明图解说明f0(X)=-0X0X0f1(X)=-max0,-+1=0max0,0+1=1X00X2X2本讲稿第三十五页，共五十九页 1 2 3 4 5 6 7 x12f1(x)1 2 3 4 5 6 7 x12f1(x-w2)+p23 1 2 3 4 5 6 7 x12f2(x)3f1(X)=-max0,-+1=0m

24、ax0,0+1=1X00X2X2f2(X)=-max0,-+2=0 max1,-+2=1max1,0+2=2max1,1+2=3X00X22X33X5X5本讲稿第三十六页，共五十九页 1 2 3 4 5 6 7 x12f2(x)3 1 2 3 4 5 6 7 8 9 x12f2(x-w3)+p3345678f3(x)1 2 3 4 5 6 7 8 9 x12345678f2(X)=-max0,-+2=0 max1,-+2=1max1,0+2=2max1,1+2=3X00X22X33XM 的的(Pj,Wj).本讲稿第四十一页，共五十九页例例 n=3,W=(2,3,4),P=(1,2,5),M=6

25、。本讲稿第四十二页，共五十九页回溯求最优决策序列回溯求最优决策序列回溯求最优决策序列回溯求最优决策序列已知最末序偶已知最末序偶已知最末序偶已知最末序偶 (P(Pl l,W,Wl l)S Sn n,回溯求回溯求回溯求回溯求 x x1 1,x,x2 2,x,xn n 的步的步的步的步骤骤骤骤:n n然后再判断留在然后再判断留在然后再判断留在然后再判断留在 S Sn-1n-1中的中的中的中的 (P(Pl l,W,Wl l)或或或或 (P(Pl l-p-pn n,W,Wl l-w-wn n)是否属于是否属于是否属于是否属于S Sn-2n-2以确以确以确以确定定定定 x xn-1n-1 的的的的值值值值

26、,依此依此依此依此类类类类推推推推,直到推出直到推出直到推出直到推出 x x1 1.n n如果如果如果如果 (P(Pl l,W,Wl l)Sn-1,xn=0;Sn-1,则则(Pl-pn,Wl-wn)Sn-1,xn=1;n n如果如果如果如果 (P(Pl l,W,Wl l)本讲稿第四十三页，共五十九页四、递推算法四、递推算法几个变量几个变量位置位置012345678910Pm00101230125Wm00202350234Si-1l h l h l k,j h l hFn+1F0F1F2F3Fi:Si第一第一对对序偶存序偶存储储位置位置,next:P,W下一个空位下一个空位S Si-1i-1的序

27、偶按的序偶按的序偶按的序偶按(P(Pj j,W,Wj j)的升序顺序产生并存储的升序顺序产生并存储的升序顺序产生并存储的升序顺序产生并存储;S S1 1i i不分配存储不分配存储不分配存储不分配存储,每生成一对序偶即与每生成一对序偶即与每生成一对序偶即与每生成一对序偶即与S Si-1i-1的序偶按支配的序偶按支配的序偶按支配的序偶按支配-清除规则归并到清除规则归并到清除规则归并到清除规则归并到S Si i.本讲稿第四十四页，共五十九页Knapsack01(float*p,float*w,float*P,float*W,int*X)Knapsack01(float*p,float*w,float

28、*P,float*W,int*X)int Fn+1;F0=P0=W0=0;l=h=0;next=h+1;int Fn+1;F0=P0=W0=0;l=h=0;next=h+1;for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)Fi=next;k=j=l;Fi=next;k=j=l;while(k=h)&(Wk+wi-1)=M)while(k=h)&(Wk+wi-1)=M)pp=Pk+pi-1;ww=Wk+wi-1;pp=Pk+pi-1;ww=Wk+wi-1;while(j=h)&(Wjww)Pnext=Pj;Wnext=Wj;next+;j+;while(j=h)&(Wjww)

29、Pnext=Pj;Wnext=Wj;next+;j+;if(j=h)&(Wj=ww)pp=max(pp,Pj);j+;if(jPnext-1)Pnext=pp;Wnext=ww;next+;if(ppPnext-1)Pnext=pp;Wnext=ww;next+;while(j=h)&(Pj=Pnext-1)j+;k+;while(j=h)&(Pj=Pnext-1)j+;k+;while(j=h)Pnext=Pj;Wnext=Wj;next+;j+;while(j0;i-)for(j=Fi-1;Wj+wi-1M;j-);py=Pj+pi-1;wy=Wj+pi-1;if(pxpy)Xi-1=0;

30、else Xi-1=1;px=Pj;wx=Wj;时间复杂度时间复杂度:空间复杂度：空间复杂度：1+2+2n-1=O(2n)P,W数组各需要数组各需要O(2n)的附加存储空间的附加存储空间本讲稿第四十六页，共五十九页4.6 可靠性设计问题可靠性设计问题 一、问题描述一、问题描述该系统的可靠性为该系统的可靠性为:n台设备串联在一起构造一个系统台设备串联在一起构造一个系统:D1r1D2r2Dnrn缺点缺点:即使每一台设备的可靠性很高，系统的可靠性不一定很高即使每一台设备的可靠性很高，系统的可靠性不一定很高 本讲稿第四十七页，共五十九页解决方案解决方案:同类设备并联的多级串联系统同类设备并联的多级串联

31、系统 D11.D1m1r1 D21.D2m2r2 Dn1.Dnmnrn第第i级的可靠性级的可靠性:系统的可靠性为系统的可靠性为系统的可靠性为系统的可靠性为:本讲稿第四十八页，共五十九页设系统的总投资成本设系统的总投资成本设系统的总投资成本设系统的总投资成本C,C,第第第第i i级设备的单价为级设备的单价为级设备的单价为级设备的单价为c ci i,显然显然显然显然,每一级设备至少要每一级设备至少要每一级设备至少要每一级设备至少要配置一台配置一台配置一台配置一台,那么那么那么那么,至多可配置台数为至多可配置台数为至多可配置台数为至多可配置台数为求在总投资成本求在总投资成本求在总投资成本求在总投资成

32、本C C的约束条件下的约束条件下的约束条件下的约束条件下,使系统可靠性最大化的设备配置方案。使系统可靠性最大化的设备配置方案。使系统可靠性最大化的设备配置方案。使系统可靠性最大化的设备配置方案。本讲稿第四十九页，共五十九页用用用用RELI(1,i,X)RELI(1,i,X)表示在容许成本表示在容许成本表示在容许成本表示在容许成本X X约束下对约束下对约束下对约束下对1i1i级设备的可靠性设计问级设备的可靠性设计问级设备的可靠性设计问级设备的可靠性设计问题题题题,即即即即整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用RELI(1,

33、n,C)RELI(1,n,C)表示表示表示表示,最优解是对最优解是对最优解是对最优解是对mm1 1,mm2 2,m,mn n的取值一系列最优决策的结果的取值一系列最优决策的结果的取值一系列最优决策的结果的取值一系列最优决策的结果.本讲稿第五十页，共五十九页二、向后递推公式二、向后递推公式最优解的可靠性为：最优解的可靠性为：初始条件：初始条件：X1;成本邻接矩阵成本邻接矩阵C:E,C(i,j)0;E,C(i,j)=;C(i,i)=0.本讲稿第五十五页，共五十九页递推关系递推关系:（1）一般化一般化:（2 2）初始条件：初始条件：g(i,)=C(i,1),i=2n（3）本讲稿第五十六页，共五十九页

34、g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意1 1个顶点个顶点个顶点个顶点),i=2n;),i=2n;g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意2 2个顶点个顶点个顶点个顶点),i=2n;),i=2n;g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意3 3个顶点个顶点个顶点个顶点),i=2n;),i=2n;g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意n-2n-2个顶点个顶点个顶点个顶点),i=2n;),i=2n;再由再由(1)式可推出式可推出g(1,V-1),即为所求即

35、为所求.本讲稿第五十七页，共五十九页本讲小结本讲小结 1)多级决策与动态规划多级决策与动态规划2)动态规划的解题关键动态规划的解题关键3)动态规划算法举例动态规划算法举例本讲稿第五十八页，共五十九页本讲作业本讲作业 参考实验指导书中的实验四参考实验指导书中的实验四参考实验指导书中的实验四参考实验指导书中的实验四,设计并实现求解多段图问题的动态规划设计并实现求解多段图问题的动态规划设计并实现求解多段图问题的动态规划设计并实现求解多段图问题的动态规划算法算法算法算法 ,并将程序模块存盘备用。并将程序模块存盘备用。并将程序模块存盘备用。并将程序模块存盘备用。参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的A4A4打印稿打印稿打印稿打印稿,由由由由班干部收集后统一提交。班干部收集后统一提交。班干部收集后统一提交。班干部收集后统一提交。本讲稿第五十九页，共五十九页