程序设计方法学实验

程序设计方法学实验

动态规划解0-1背包：　　#include　　using namespace std;　　//显然定义为全局变量不好　　const int item=3;//物品数量　　const int max_wgt=10;//背包最蚂凳大容量　　int c[item+1][max_wgt+1];//从1…i…item物品中,背包剩余空间为0<=j<=max_wgt的最大价值　　int w[item+1]={0,3,4,5};//物品质量　　int vl[item+1]={0,4,5,6}; //物品价值　　int knapbag()　　{　　for (int i=0;i<=item;i++)//初始化　　{　　for (int j=0;j<=max_wgt;j++)　　{　　c[i][j]=0;　　}　　}　　//c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)}　　for (int i=1;i<=item;i++)　　{　　for (int j=1;j<=max_wgt;j++)　　{　　if (w[i]<=j)　　{　　if (vl[i]+c[i-1][j-w[i]]>c[i-1][j])　　{　　c[i][j]=vl[i]+c[i-1][j-w[i]];//选择第i物品　　}　　else　　c[i][j]=c[i-1][j];//不选择第i个物品　　}　　else　　c[i][j]=c[i-1][j];//剩余容量不够　　}//endfor　　}//endfor　　return c[item][max_wgt];//返回最大值　　}　　int main()　　{　　cout<0;i--)　　闷虚旅{　　if (c[i][temp_wei]==c[i-1][temp_wei])//最后一个肯定是最大价值的　　{　　x[i]=0;　　}　　else　　{　　x[i]=1;　　temp_wei-=w[i];　　}　　}　　for (int i=0;i<=item;i++)　　{　　if (x[i])　　{　　std::cout<　　using namespace std;　　void LCS_Length(char *x,char *y,int **b,int m,int n)　　{　　//c[i][j]表示x[i-1],y[j-1]之前公共子序列的长度,i表示x数组前进，j表示y数组前进　　//不用c[i][j]表示x[i],y[j]之前公共子序列的长度是因为需要使用c[0][0]来表示没有公共子序列，　　//即c[0][0]恒等于0，因此c数组最大下标为c[m+1][n+1]　　int **c;　　c=new int*[m+1];　　for( int i=0;i=c[i][j-1])　　{　　c[i][j]=c[i-1][j];//当前最长公共子序列可以不需要x[i-1]　　b[i][j]=-1;　　}　　//和上面分析类似　　else　　{　　c[i][j]=c[i][j-1];//当前最长公共子序列可以不需要y[j-1]　　b[i][j]=1;　　}　　}　　}　　for(int i=0;i=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。　　3.A*算法的步骤　　A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。　　A*算法的步骤如下：　　1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。　　2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。　　3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。　　4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。　　5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。　　4.八数码问题的A*算法的估价函数　　估价函数中，主要是计算h，对于不同的问题，h有不同的含义。那么在八数码问题中，h的含意是各什么？八数码问题的一个状态实际上是数字0~8的一个排列，用一个数组p[9]来存储它，数组中每个元素的下标，就是该数在排列中的位置。例如，在一个状态中，p[3]=7，则数字7的位置是3。如果目标状态数字3的位置是8，那么数字7对目标状态的偏移距离就是3，因为它要移动3步才可以回到目标状态的位置。　　八数码问题中，每个数字可以有9个不同的位置，因此，在任意状态中的每个数字和目标状态中同一数字的相对距离就有9*9种，可以先将这些相对距离算出来，用一个矩阵存储，这样只要知道两个状态中同一个数字的位置，就可查出它们的相对距离，也就是该数字的偏移距离：　　0 1 2 3 4 5 6 7 8　　0 0 1 2 1 2 3 2 3 4　　1 1 0 1 2 1 2 3 2 3　　2 2 1 0 3 2 1 4 3 2　　3 1 2 3 0 1 2 1 2 3　　4 2 1 2 1 0 1 2 1 2　　5 3 2 1 2 1 0 3 2 1　　6 2 3 4 1 2 3 0 1 2　　7 3 2 3 2 1 2 1 0 1　　8 4 3 2 3 2 1 2 1 0　　例如在一个状态中，数字8的位置是3，在另一状态中位置是7，那么从矩阵的3行7列可找到2，它就是8在两个状态中的偏移距离。　　估价函数中的h就是全体数字偏移距离之和。　　显然，要计算两个不同状态中同一数字的偏移距离，需要知道该数字在每个状态中的位置，这就要对数组p[9]进行扫描。由于状态发生变化，个数字的位置也要变化，所以每次计算h都沿线扫描数组，以确定每个数字在数组中的位置。为了简化计算，这里用一个数组存储状态中各个数字的位置，并让它在状态改变时随着变化，这样就不必在每次计算h时，再去扫描状态数组。　　例如，某个状态中，数字5的位置是8，如果用数组r[9]存储位置，那么就有r[5]=8。　　现在用数组r[9]存储当前状态的数字位置，而用s[9]存储目标状态的数字位置，那么当前状态数字i对目标状态的偏移距离就是矩阵中r[i]行s[i]列对应的值。　　5.A*算法的类结构　　A*算法的类声明如下：　　class TAstar:public TEight　　{　　public:　　TAstar(){} //构造函数　　TAstar(char *fname); //带参数构造函数　　virtual void Search(); //A*搜索法　　private:　　int f,g,h; //估价函数　　int r[Num]; //存储状态中各个数字位置的辅助数组　　static int s[Num]; //存储目标状态中各个数字位置的辅助数组　　static int e[]； //存储各个数字相对距离的辅助数组　　void Printl(TList L); //成员函数，输出搜索路径　　int Expend(int i); //成员函数，A*算法的状态扩展函数　　int Calcuf(); //成员函数，计算估价函数　　void Sort(TList& L,int k); //成员函数，将新扩展结点按f从小到大　　//顺序插入待扩展结点队列　　int Repeat(TList &L); //成员函数，检查结点是否重复　　};　　int TAstar::s[Num],TAstar::e[Num*Num];　　TAstar::TAstar(char *fname):TEight(fname)　　{　　for(int i=0;i>e[i];　　fin.close();　　f=g=h=0; //估价函数初始值　　}　　void TAstar::Printl(TList L)　　{　　TAstar T=*this;　　if(T.last==-1)　　return;　　else　　{　　T=L.GetData(T.last);　　T.Printl(L);　　T.Printf();　　}　　}　　int TAstar::Expend(int i)　　{　　if(Extend(i)) //结点可扩展　　{　　int temp=r[p[r[0]]]; //改变状态后数字位置变化，存储改变后的位置　　r[p[r[0]]]=r[0];　　r[0]=temp;　　return 1;　　}　　return 0;　　}　　int TAstar::Calcuf()　　{　　h=0;　　for(int i=0;i& L,int k)　　{　　int n=L.Getlen();　　for(int i=k+1;if<=T.f)　　break;　　}　　L.Insert(*this,i);　　}　　int TAstar::Repeat(TList &L)　　{　　int n=L.Getlen();　　for(int i=0;i L; //建立队列　　L.Append(T); //初始结点入队　　int head=0,tail=0; //队列头和尾指针　　while(head<=tail) //队列不空则循环　　{　　for(int i=0;i<4;i++) //空格可能移动方向　　{　　T=L.GetData(head); //去队列头结点　　if(T.h==0) //是目标结点　　{　　T.Printl(L);//输出搜索路径　　T.Print(); //输出目标状态　　return; //结束　　}　　if(T.Expend(i)) //若结点可扩展　　{　　int k=T.Repeat(L); //返回与已扩展结点重复的序号 if(kT.g) //比较两结点g值　　L.SetData(T,k); //保留g值小的　　continue;　　}　　T.Sort(L,head) ; //新结点插入可扩展结点队列 tail++; //队列尾指针后移　　}　　}　　head++; //一个结点不能再扩展，队列头指针指向下一结点　　}　　}　　n皇后问题　　#include 　　#include 　　void Queue(int n)　　{　　for (i=1; i<=n; i++) //初始化　　x[i]=0;　　k=1;　　while (k>=1)　　{　　x[k]=x[k]+1; //在下一列放置第k个皇后　　while (x[k]<=n && !Place(k))　　x[k]=x[k]+1; //搜索下一列　　if (x[k]<=n && k= =n) { //得到一个解，输出　　for (i=1; i<=n; i++)　　cout<