算法实验 八皇后问题.docx

姓名：+ 学号：090610213 班级：0904103实验题目： 八皇后问题问题分析：要在8*8的国际象棋棋盘中放8个皇后，是任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。解决问题的关键为怎样取到8个位置，判断他们符合要求。数学模型： 每一行中只能取到一个位置，这样问题的解空间就是8个皇后所在的列的序号。1）通过8重循环从每一行中取得一个位置，检验取到的检验8个位置不在同一列、同一对角线。2）按深度优先的思想，从第一个皇后开始搜索，确定一个位置后，在搜索第二个皇后的位置；每前进一步检查是否满足约束条件，不满足时，用continue语句回溯到上一个皇后，继续尝试下一位置；满足约束条件时，开始搜索下一位置，知道找到问题解。约束条件：不在同一列的表达式 xi!=xj不在同一对角线上的约束条件abs(xi-xj)!=abs(i-j) 算法策略的选择： 蛮力枚举法 枚举回溯法程序流程图：算法的时间复杂度的分析：1）采用8重循环 时间复杂度为8程序实现：1）void CEightqueDlg:OnButton1() /取自不同行的位置count=0;for(que0=0;que08;que0+)for(que1=0;que18;que1+)for(que2=0;que28;que2+)for(que3=0;que38;que3+)for(que4=0;que48;que4+)for(que5=0;que58;que5+)for(que6=0;que68;que6+)for(que7=0;que78;que7+)Judge();CString str;str.Format(%d,count);MessageBox(str);void CEightqueDlg:Judge() for(int t1=0;t18;t1+) /验证是否取自不同的列for(int t2=t1+1;t28;t2+) if(quet1=quet2)return; /存在处于同一列的位置则返bool flag=false; /验证是否在不同的对角线上 for(int j=0;j7;j+) for(int i=1;i8-j;i+) if(quej+i=quei+j|quej-i=quei+j) flag=true; break; if(flag) break; if(!flag) CString a; a=; for(int k=0;kSetWindowText(out); count+; 2）void CEight2Dlg:OnCancel() int a8; int count=0CString aa,bb;aa=bb=;for(a0=0;a08;a0+)for(a1=0;a18;a1+)if(check(a,1)=0) continue;for(a2=0;a28;a2+)if(check(a,2)=0) continue;for(a3=0;a38;a3+)if(check(a,3)=0) continue;for(a4=0;a48;a4+)if(check(a,4)=0) continue;for(a5=0;a58;a5+)if(check(a,5)=0) continue;for(a6=0;a68;a6+)if(check(a,6)=0) continue;for(a7=0;a78;a7+)if(check(a,7)=0) continue；elsefor(int i=0;i8;i+)aa.Format(%d,ai);bb+=aa+ ;m_list.AddString(bb);bb=;count+;aa.Format(%d,count);MessageBox(总共有组合数：+aa);int CEight2Dlg:check(int a, int n) int i; for(i=0;in;i+) if(abs(ai-an)=abs(i-n)|(ai=an) return(0); return(1)； 结果输出：实验题目：动态规划 最大盈利问题分析：5台机器3个工厂，求总利润最大的方案。三个工厂获得的机器数、利润之间都是不独立的，不能用分治和贪婪算法求解，每一种阶段都要在全面考虑各种情况之后，做出必要的决策，因此此题应用动态规划求解。数学模型： 依所考虑的工厂数目划分阶段，公分为三个阶段。线考虑分配给A工厂的机器数与利润之间的关系；第二阶段A，B工厂共同分配的机器数与获得的总利润之间的关系；最后考虑三个工厂共同的情况。q存储每个工厂在获得不同数量的机器是的利润情况，f存储当前考虑的项目数下分配不同机器数时的利润二维数组a存储最大收益的情况下每个工厂分配的机器数。算法策略的选择： 动态规划程序流程图：算法时间复杂度分析：程序实现：void CFactoryDlg:OnCancel() int q6,temp6,gain6;int a36; /记录最大利润时给第i个工厂分配的机器数int m=3; /工厂数 int n=5; /机器数int A36=0,3,7,9,12,13,0,5,10,11,11,11,0,4,6,11,12,12; intf6=0,3,7,9,12,13;for(int i=0;in;i+)a0i=i;for(int k=1;k3;k+)for(int j=0;jn;j+) tempj=fj; qj=Akj; akj=0; for(j=0;j6;j+)for(i=0;itempj)tempj=fj-i+qi; akj=i; for(j=0;j=0;i-)gaini=airest；rest=rest-gaini;CString result,aa; aa.Format(%d,gain0);result+=A厂分配+aa+台;aa.Format(%d,gain1);result+=B厂分配+aa+台;aa.Format(%d,gain2);result+=C厂分配+aa+台;aa.Format(%d,f5);result+=总利润是：+aa;MessageBox(result);结果：总结：实验题目：矩阵连乘问题分析：不同顺序的矩阵相乘运算，虽然运算结果相同，但所作的乘法次数差距很大。找到不同的组合方式下矩阵相乘的最少乘法次数，并用所得到的矩阵相乘的顺序计算矩阵相乘的结果。数学模型：动态规划的阶段是以相乘的矩阵的个数划分的；出事状态为一个矩阵相乘的计算量；第二阶段为两个矩阵相乘.最后一个阶段，是n个矩阵相乘的情况。com记录矩阵相乘的结合方式；m记录乘法次数算法策略的选择： 动态规划流程图：算法的时间复杂度：程序实现：void CMatrixDlg:OnButton1() /寻找乘机数最少的乘法int n,i,j; /n为矩阵的个数CString cou,s1,s2,std;GetPrivateProfileString(count,count,cou.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini);n=atoi(cou); /获取矩阵的个数for(i=0;in;i+)std.Format(%d,i); GetPrivateProfileString(std,size1,s1.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini);ri=atoi(s1);std.Format(%d,-i);GetPrivateProfileString(std,size2,s1.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini);ri+1=atoi(s1);for(i=0;in;i+)for(j=0;jn;j+)comij=0; mij=-1;course(0,n-1);std.Format(%d,m0n-1); m_cishu=std; CString aa,bb;for(i=0;in;i+)for(j=0;j=0) return mij; if(i=j) return 0; if(i=j-1) comii+1=i; mij=ri*ri+1*ri+2; return mij; u=course(i,i)+course(i+1,j)+ri*ri+1*rj+1; comij=i; for(k=i+1;kj;k+) t=course(i,k)+course(k+1,j)+ri*rk+1*rj+1; if(tu) u=t;comij=k; mij=u; return u;void CMatrixDlg:OnButton2() /实现量矩阵相乘CString cou;int c;GetPrivateProfileString(count,count,cou.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini);c=atoi(cou); /获取矩阵的个数int W400,len,m,n,p,k=0;CString str,std,s1,s2,s3,buffer=;for(int i=0;ic;i+)std.Format(%d,i);GetPrivateProfileString(std,size1,s1.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini);GetPrivateProfileString(std,size2,s2.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini);GetPrivateProfileString(std,Mat,str.GetBuffer(MAX_PATH),MAX_PATH,.Matrix.ini); str.ReleaseBuffer();len=str.GetLength();m=atoi(s1);n=atoi(s2);for(int j=0;jlen;j+)if(strj!=,)buffer+=strj;else Wk=atoi(buffer);buffer=;k+;for(int t1=0;t1m;t1+)for(int t2=0;t2n;t2+) Mi.at1t2=Wn*t1+t2;Mi.s1=m;Mi.s2=n;JiSuan(0,c-1);CString result,aa,bb;for(int t1=0;t1M0.s1;t1+)for(int t2=0;t2M0.s2;t2+)bb.Format(%d,M0.at1t2); aa+=bb+ ;m_list.InsertString(t1,aa);aa=;int CMatrixDlg:JiSuan(int a, int b) if(a=b-1) Double(a,b); else if(a=b) else JiSuan(a,comab); JiSuan(comab+1,b); Double(a,comab+1); return 1;void CMatrixDlg:Double(int a, int b) int buf2