发布时间 : 星期二 文章算法设计与分析习题 - 图文更新完毕开始阅读4a2af42ba300a6c30c229f7f
for(int i=2; i<=n; i++)//贪心选择从活动j=2?n判是否可加入A { if( 活动i的开始时间，大于 最近活动j的结束时间 ) {将活动i加入活动集合A；
j=i; //活动i作为最近加入活动集合A的最近活动 count++; } else
活动i不加入活动集合A；} return count; }
程序设计语言：
Int greedyselector(int s[ ], int f[ ], boolean a[ ]) { int n=s.length; //n活动的个数
Mergesort (a[ ],f[ ], n ); //按活动结束时间排序，便于贪心选择 a[1]=true; //活动１被选中
int j=1; //j记录最近依次加入活动集合A的活动j int count=1; //count存储相容活动个数
for(int i=2; i<=n; i++) //贪心选择从活动i=2?n判是否可加入A { if( s[ i]>=f[ j] )
{ a[ i]=true; //将活动i加入活动集合A
j=i; //活动i作为最近加入活动集合A的最近活动 count++; }
else a[ i]=false; // s[ i] return count; } 该算法主要包括２部分： ? 按照按活动结束时间对活动排序时间，其时间复杂度为：O(n*logn)； ? 贪心选择时间，其需要经过n-1次的比较（s[ i]>=f[ j]） 时间复杂度为：O(n-1); 故本算法的时间复杂度： O(n*logn＋n-1)； 记为： O(n*logn)。 7、掌握例dijkstra算法的求单源最短路径问题。 算法设计？求解过程？ 答: void dijkstra (int v, float a[][], float dist[]) { //v表示源,a[i][j]表示边i到j的权值 //dist[i]记录源到顶点i的最短路径长度 //prev[i]记录顶点i的前一个点,可以找出最短路径 int n=dist.length; boolean s[ ]; //s[i]标记顶点i是否加入顶点集合s if( v<1 || v>n) return; //源点v不存在 for(int i=1;i<=n;i++) { dist[i]=a[v][i]; //初始化数组dist[i]、s[i] s[i]=false; if(dist[i]=max-value) //源到顶点i没有边 prev[i]=0; else prev[i]=v; } dist[v]=0; s[v]=true; //把源v加入到集合s中 for(int i=1; i for(int j=1;j<=n;j++) //贪心选择，计算V-S中顶点的dist[ ]值，选择最小的那个顶点j if( (!s[j]) &&(dist[j] s[u]=true; //源到顶点u的最短路径已经确定，u加入到s中 for(int j=2;j<=n;j++) //根据u重新计算dist[ ] if( (!s[j]) &&(a[u][j]< max-value) //u到j有边 float newdist=dist[u]+a[u][j]; if(newdist 2 该算法主体有两重循环，故该算法的时间复杂度记为O(n) 8、P126图４－８求最小生成树，写出其prim算法？ 并给出其选边过程? 答： prim算法描述(伪代码) void prim(int n, float c[][])//c[][]存储边权值 { T=空集； //T表示最小生成树的边集合 S={ 1 }; //S表示最小生成树包含的顶点集合 while( S!=V ) {选择边（i，j），i∈S 且j ∈V-S；且权值c[i][j]最小； //贪心选择 T=T∪ {（i，j）}; S=S∪{ j }； } } prim算法描述(程序设计语言) Void prim (int n, float c[][]) {float lowcost[ ]; float closest[ ]; boolean s[ ]; s[1]=true; //初始化，顶点1加入生成树集合s for(int i=2;i<=n;i++) //初始化，计算与顶点1相邻顶点边权值 { lowcost[i]=c[1][i]; colsest[i]=1; s[i]=false; } for(int i=1;i for( int k=2;k<=n; k++) //贪心选择,v-s中找使lowcost[]最小的顶点k if((lowcost[k] s[j]=true; //把找到的顶点j加入到生成树集合s中 for(int k=2;k<=n; k++) //根据刚加入的顶点修改lowcost, closest if((c[j][k] {lowcost[k]=c[j][k]; closest[k]=j;} } } 2 该算法主体有两重循环，故该算法的时间复杂度记为O(n) Prim算法执行过程： 首先，找出V-S中使lowcost值最小的顶点j(距离s最近的顶点j); 然后，根据数组closest选取边(j,closest[j］)； 最后，将j添加到S中，并对closest和lowcost作必要的修改。 选边过程： 9、P126图４－８，利用kruskal算法求最小生成树， 给出其选边过程？ 答：伪代码： void krustral(int n, float c[][])//c[][]存储边权值 { mergesort（float c[][], T[]）; //按边权值排序 T=空集； //T表示最小生成树的边集合 while( |T| //边(i,j)一端i在T1分支,一端j在T２分支 { union(i,j); T=T∪{（i，j)} } else T=T∪{（i，j)}; } } 选边过程： 第５章 回溯算法 1、回溯法基本思想？回溯法解题步骤？ 答：基本思想：在搜索尝试中找问题的解，当不满足条件就”回溯”返回，尝试别的路径。 解题步骤：(1)针对所给问题，定义问题的解空间； (2)并确定易于搜索的解空间结构(排列树，子集树); (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数，剪去无效的枝，避免无效搜索。 2、什么叫子集树？什么叫排列树？ 什么叫满m叉树？ 答：1）子集树 ：当所给问题是在n个元素的集合S中找出S满足某种性质的子集时，其相应的解空间树称作子集树。 2）排列树 ： 当所给问题是在确定的n个元素满足某种性质的排列中搜索问题的解时，相应的解空间树被称作排列树。 3）满m叉树： 当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合。 这类问题的解空间树称为满m叉树。 3、利用回溯法，求解0－1背包问题，要求设计出相应算法？并分析其时间复杂度？ 答：算法描述（递归实现） double knaspack(double p[ ], double w[ ], double c) //c是背包载重 {double cw=0; //当前重量 double cp=0; //当前价值