算法设计与分析计算题

《算法设计与分析》一、排序和查找是经常遇到的问题。按照要求完成以下各题：(1)对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。解：（1）第一步：15291351832127255第二步：29135183227251515第三步：13532291827251551第四步：13532292725181551(2)请描述递减数组进行二分搜索的基本思想，并给出非递归算法。解：基本思想：首先将待搜索元素v与数组的中间元素2nA进行比较，如果2nvA，则在前半部分元素中搜索v；若2nvA，则搜索成功；否则在后半部分数组中搜索v。非递归算法：输入：递减数组A[left:right]，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：intBinarySearch(intA[],intleft,intright,intv){intmid;while(left=right){mid=int((left+right)/2);if(v==A[mid])returnmid;elseif(vA[mid])right=mid-1;elseleft=mid+1;}return-1;}(3)给出上述算法的递归算法。解：输入：递减数组A[left:right]，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：【3分】intBinarySearch(intA[],intleft,intright,intv){intmid;if(left=right){mid=int((left+right)/2);if(v==A[mid])returnmid;elseif(vA[mid])returnBinarySearch(A,left,mid-1,v);elsereturnBinarySearch(A,mid+1,right,v);}elsereturn-1;}(4)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。解：搜索18：首先与27比较，1827，在后半部分搜索；再次与18比较，搜索到，返回5。搜索31：首先与27比较，3127，在前半部分搜索；再次32比较，3132，在后半部分搜索，与29比较，3129，此时只有一个元素，未找到，返回-1。搜索135：首先与27比较，13527，在前半部分搜索；再次32比较，13532，在前半部分搜索；与135比较，相同，返回0。二、排序和查找是常用的计算机算法。按照要求完成以下各题：（1）对数组A={15，9，115，118，3，90，27，25，5}，使用合并排序方法将其排成递减序。（2）若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z，先与元素[]3nA比较，若[]3nZA，则在前面[]3n个元素中寻找Z；否则与2[]3nA比较，总之使余下的序列为[]3n个元素。给出该方法的伪代码描述。(3)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：118，31，25。解：（1）第一步：15911511839027255第二步：15911811590327255第三步：11811515990272535第四步：11811590272515935第五步：11811590272515953（2）输入：递减数组A[left:right]，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：intBinarySearch(intA[],intleft,intright,intv){intmid;while(left=right){first=left+(right-left+1)/3;second=left+(right-left+1)/3*2;if(v==A[first])returnfirst;elseif(vA[first])right=first-1;elseif(v==A[second])returnsecond;elseif(vA[second]){left=first+1;right=second-1;}elseleft=second+1;}return-1;}（3）搜索118：11827，所以right＝3；118115，所以right＝1；118＝118，找到。搜索31：3127，所以right＝3；3190，所以left=4，结束，未找到。搜索25：92527，所以left=5，right=6；25＝25，找到。三、Dijkstra算法求单源最短路径d[u]:s到u的距离p[u]:记录前一节点信息Init-single-source(G,s)foreachvertexv∈V[G]do{d[v]=∞;p[v]=NIL}d[s]=0Relax(u,v,w)ifd[v]d[u]+w(u,v)then{d[v]=d[u]+w[u,v];p[v]=u}dijkstra(G,w,s)Init-single-source(G,s)S=ΦQ=V[G]whileQΦdou=min(Q)S=S∪{u}foreachvertexv∈adj[u]doRelax(u,v,w)四、对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。ahgfedcb23122423112步骤V1V2E1E21.{a}{b}{}{ab}2.{a,b}{d}{ab}{bd}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}{}结果：从a到h的最短路径为abdfegh，权值为18。五、问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。#includestdio.hvoidmain(){intm,n,i,j,w[50],p[50],pl[50],b[50],s=0,max;printf(输入背包容量m,物品种类n:);scanf(%d%d,&m,&n);for(i=1;i=n;i=i+1){printf(输入物品的重量W和价值P:);scanf(%d%d,&w[i],&p[i]);pl[i]=p[i];s=s+w[i];}if(s=m){printf(wholechoose\n);//return;}for(i=1;i=n;i=i+1){max=1;for(j=2;j=n;j=j+1)if(pl[j]/w[j]pl[max]/w[max])max=j;pl[max]=0;b[i]=max;}for(i=1,s=0;sm&&i=n;i=i+1)s=s+w[b[i]];if(s!=m)w[b[i-1]]=m-w[b[i-1]];for(j=1;j=i-1;j=j+1)printf(chooseweight%d\n,w[b[j]]);六、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。物品ABCDEFG重量35306050401025价值10403050354030解：贪心算法：（1）标准：重量、价值和单位价值。（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。（3）显然使用单位价值作为标准得到的是最优解。回溯法：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：aaabaacQ111x21x31x41x50x60x70xdee40x30x41xe51xf60xg50xh40xi20xj10xa．1501154040305035190.625407(1,1,1,1,,0,0)8b.1501154040305030177.5607(1,1,1,1,0,,0)12c．4040305010170(1,1,1,1,0,0,1)d.1501054040303530167.5603(1,1,1,0,1,,0)4e.1501304040503530175601(1,1,0,1,1,,0)3f.1501304040503510170.71354(1,1,0,1,1,0,)7g.40405030160(1,1,0,1,0,1,0)h.1501404040353010146.85352(1,1,0,0,1,1,)7i.1501254030503530167.5605(1,0,1,1,1,,0)12j.1501454030503530157.5601(0,1,1,1,1,,0)12在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。七、分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间（1）贪心算法O（nlog（n））首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下：voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i=n;i++)x[i]=0;floatc=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)的递归式如下。voidKnapSack(intv[],intw[],intc,intn,intm[][11]){intjMax=min(w[n]-1,c);for(j=0;j=jMax;j++)/*m(n,j)=00=jw[n]*/m[n][j]=0;for(j=w[n];j=c;j++)/*m(n,j)=v[n]j=w[n]*/m[n][j]=v[n];for(i=n-1;i1;i--){intjMax=min(w[i]-1,c);for(j=0;j=jMax;j++)/*m(i,j)=m(i+1,j)0=jw[i]*/m[i][j]=m[i+1][j];for(j=w[i];j=c;j++)/*m(n,j)=v[n]j=w[n]*/m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c]