s算法设计与分析.doc

注意：第一大题第四小题没有答案！一、1分治法构造n位Gray法答：#include #include #include using namespace std;int *Road;void R_Gray( int, int );void Gray( int n, int level ) if( level=0 ) copy( Road, Road+n, ostream_iterator(cout) ),coutendl; return; Roadn-level=0; Gray( n, level-1 ); Roadn-level=1; R_Gray( n, level-1 );void R_Gray( int n, int level ) if( level=0 ) copy( Road, Road+n, ostream_iterator(cout) ),coutn; Road=new intn; Gray( n, n ); delete Road; return 0;2.动态规划法与备忘录各自的特点。答：动态规划法是将待求解的问题分解成若干子问题，先解决子问题，从这些子问题的解得出原问题的解。这些子问题往往不是相互独立的。备忘录方法是动态规划法的变形，用表格保存已经解决的子问题的答案，下次需要解词问题时，只要简单查看该子问题的解答，不必重新计算。不过备忘录的递归方式是自顶向下的，而动态规划法师自底向上的。因此，两种方法控制结构相同，区别在于备忘录放过为解过的子问题建立备忘录以备需时查看，避免了相同子问题的重复求解。3.列举常见的阶为O（n2）和O（nlog2）的排序算法。O（n2）改进为O（nlog2）的根本原因是什么？答：O（n2）：冒泡、插入、选择O（nlog2）：堆、归并、快速当问题规模越大，算法复杂性越低，代表算法效率越高。4.集合S=1、2、6、8，求子集，要求该子集的元素之和d=9，画出子集和问题的解空间树。答：5.比较回溯法与分支界限法在实际应用中的异同答：分支界限法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下两者的求解目标不同，回溯法是找到满足条件的所有解，而分支界限法师找到一个最优解。所以二者对解空间的搜索方式也不相同，回溯法是以深度优先的方法搜索解空间，而分支界限法则是以广度优先货最小耗费优先的方式搜索解空间。二、动态规划方法解决“租用游艇问题”答：该问题实际上是一种特殊的最短路径问题。定义数组a（aij表示从游艇出租站i到游艇出租站j所需的租金），数组a的数据由文件input.txt提供。可根据Dijkstra算法的思想来确定最少租金的最优子结构，定义数组cost（costi存放从游艇出租站1到游艇出租站i所需的最少租金）。对于cost数组，设costj（j1,i-1）存放从游艇出租站1到游艇出租站j的最少租金，则从游艇出租站1到游艇出租站i所需的最少租金costi应是costj+aji（j1,i-1）的最小值。故：costn即为所求的从游艇出租站1到游艇出租站n所需的最少租金。根据上述定义，可通过以下程序实现：/*求解从游艇出租站1到游艇出租站n所需的最少租金问题*/* aij表示从游艇出租站i到游艇出租站j所需的租金/* costi表示从游艇出租站1到游艇出租站i所需的最小租金/* a,cost可最为全局函数，程序载人时已经定义好/*/double mincost(int n)int i,j;cost1=0;cost2=a12;/初始化for(i=3;i=n;i+)costi=a1i;for(j=2;j=i-1;j+)if(costj+ajicosti)costi=costj+aji;return costn;三、字符串由n个小写字母组成（有重复），请输出该串中任意m个字符形成的所有排列（不能重复）答：#include#include#includestatic int v1024;/访问数组 static char t10241024,a1024;static int j=0,count=0;void pailie(char *s,int M,int k) int i; if(j!=M) for(i=0;istrlen(s);i+) if(vi=0) vi=1; aj=si; j+; pailie(s,M,i); else aj=0; for(i=0;icount;i+) if(strcmp(ti,a)=0)i=count+1; if(i=count) strcpy(tcount,a); count+; j-; vk=0;int main() char s1024; int M; printf(请输入字符串：); gets(s); printf(n请输入所取字符个数M：); scanf(%d,&M); for(int i=0;istrlen(s);i+) vi=0; pailie(s,M,0); printf(n得到的排列总数为：%dn,count); printf(n得到的所有排列为：n); for(int i=0;icount;i+) printf(%st,ti); printf(nn); system(pause);四、带限期单机作业排序问题。集合A存储所选择的活动n为作业个数fi为i作业的截止时间si为i作业的起始时间void GreedySelector（int n，Type s,Type f,bool A）A1=true;Int j=1;For(int i=2;i=fj)Ai=ture;j=I; Else Ai=false;五、请使用回溯法或分支界限法解“运动员最佳配对问题” 回溯法：#include stdafx.h#include #include #include #include using namespace std;vector Re; 考试,大提示全局变量,Re用来记录配对情况vectorvector P;vectorvector Q;class Queenfriend int PairUp(int);private:bool Place(int k);void Backtrack(int k);int n;int sum;vector x;public:Queen(int m,int c,int b)x.resize(m+1);Re.resize(m+1);n = c;sum = b;Queen() ;bool Queen:Place(int k)for(int j=1;jn)int temp=0; 第次还原为进行下次的累加for(int i=1;i=n;i+)temp += (Pixi) * (Qxii); 累加，得到一个可行解if(sum=temp) 记录最大可行解sum=temp;copy(x.begin(),x.end(),Re.begin();elsefor(int i=t;i=n;i+)swap(xt,xi);if(Place(t)Backtrack(t+1);swap(xt,xi);int PairUp(int n)Queen X(n,n,0);vector p;for(int i=0;i=n;i+)p.push_back(i);copy(p.begin(),p.end(),X.x.begin();X.Backtrack(1);return X.sum;int _tmain(int argc,_TCHAR* argv)ifstream fin(input.txt);ofstream fout(output.txt);int n,i,j,temp;vector r;vector t;finn;r.push_back(0);P.push_back(r);t.push_back(0);Q.push_back(t);cout从文件input.txt中获得数据.endl;for(i=1;i=n;i+)for(j=1;jtemp;r.push_back(temp);P.push_back(r);for(vector:iterator vr = r.begin()+1;vr != r.end();)vr = r.erase(vr);for(i=1;i=n;i+)for(j=1;jtemp;t.push_back(temp);Q.push_back(t);for(vector:iterato