计算机算法设计与分析实验报告

计算机算法设计与分析实验报告专业：java技术学号：541213440245姓名：徐亚涛指导老师：谷培培实验一：棋盘覆盖（递归与分治策略）一、实验目的与要求1、明确棋盘覆盖的概念2、明确递归与分治策略的设计思路。3、利用递归与分治策略解决棋盘覆盖问题。二、实验题：

问题描述：递归与分治策略算法，用4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。输入数据由程序运行后的界面中的编辑框中输入游戏规模,特殊方格的位置。将覆盖的结果在窗口中显示出来。三、实验代码packagecn.ChessBoard;importjava.awt.BorderLayout;importjava.awt.Color;importjava.awt.Font;importjava.awt.GridLayout;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.util.Random;importjavax.swing.JButton;importjavax.swing.JFrame;importjavax.swing.JLabel;importjavax.swing.JPanel;importjavax.swing.JTextArea;importjavax.swing.JTextField;publicclassChessBoardsextendsJFrame{ privateinttr,tc,dr,dc,size;//定义各成员变量 inttile=1; floatred,green,blue; JPanelcenterPanel; JPanelsouthPanel; JButton[][]button; JTextFieldTrText,TcText,DrText,DcText,SizeText; JLabelTrLabel,TcLabel,DrLabel,DcLabel,SizeLabel; JButtonOKButton; JButtonCancelButton; JPanelpanel=newJPanel(); publicChessBoards(){ super(); setTitle("棋盘覆盖"); this.setResizable(false); centerPanel=newJPanel(); southPanel=newJPanel(); OKButton=newJButton("确定或开始"); OKButton.addActionListener(newOKButtonAction()); CancelButton=newJButton("取消或清除"); CancelButton.addActionListener(newOKButtonAction()); setBounds(300,-10,900,900);//设置窗口大小与位置 TrText=newJTextField("0",2);//定义各组件 TcText=newJTextField("0",2); DrText=newJTextField("0",2); DcText=newJTextField("0",2); SizeText=newJTextField("4",2); TrLabel=newJLabel("起始方格坐标x:"); TcLabel=newJLabel("起始方格坐标y:"); DrLabel=newJLabel("特殊方格坐标x:"); DcLabel=newJLabel("特殊方格坐标y:"); SizeLabel=newJLabel("棋盘规模size:"); TrText.setEnabled(false); TcText.setEnabled(false); inttR=Integer.parseInt(TrText.getText()); inttC=Integer.parseInt(TcText.getText()); intdR=Integer.parseInt(DrText.getText()); intdC=Integer.parseInt(DcText.getText()); intSize=1; for(inti=0;i<Integer.parseInt(SizeText.getText());i++) Size*=2; tr=tR; tc=tC; dr=dR; dc=dC; size=Size; southPanel.add(CancelButton);//添加各组件到窗体 southPanel.add(TrLabel); southPanel.add(TrText); southPanel.add(TcLabel); southPanel.add(TcText); southPanel.add(DrLabel); southPanel.add(DrText); southPanel.add(DcLabel); southPanel.add(DcText); southPanel.add(SizeLabel); southPanel.add(SizeText); southPanel.add(OKButton); getContentPane().add(southPanel,BorderLayout.NORTH); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } classgridLayout{ publicgridLayout(){ centerPanel.setLayout(newGridLayout(0,size)); button=newJButton[size][size]; for(inti=0;i<size;i++){ for(intj=0;j<size;j++){ button[i][j]=newJButton(); if(i==dr&&j==dc){ button[i][j].setBackground(Color.BLUE); button[i][j].setText("<html><fontsize='2'color='white'>棋盘覆盖<br>DoneByJava!</font></html>"); button[i][j].setEnabled(false); } centerPanel.add(button[i][j]); } } } privatevoidsleep() { for(inti=0;i<100;i++) for(intj=0;j<1000;j++); } publicvoidChessBoard(inttr,inttc,intdr,intdc,intsize){//算法实现 if(size==1)//棋盘方格大小为1,说明递归到最里层 return; intt=tile++;//每次递增1 Randomrd=newRandom(); red=rd.nextFloat(); green=rd.nextFloat(); blue=rd.nextFloat(); Colorcol=newColor(red,green,blue); sleep(); ints=size/2;//棋盘中间的行、列号(相等的) //检查特殊方块是否在左上角子棋盘中 if(dr<tr+s&&dc<tc+s)//在 ChessBoard(tr,tc,dr,dc,s); else//不在，将该子棋盘右下角的方块视为特殊方块 { button[tr+s-1][tc+s-1].setBackground(col); button[tr+s-1][tc+s-1].setEnabled(false); button[tr+s-1][tc+s-1].setText("<html><Fontsize='4',color='white'>"+t+"</Font></html>"); ChessBoard(tr,tc,tr+s-1,tc+s-1,s); sleep(); } //检查特殊方块是否在右上角子棋盘中 if(dr<tr+s&&dc>=tc+s)//在 ChessBoard(tr,tc+s,dr,dc,s); else//不在，将该子棋盘左下角的方块视为特殊方块 { button[tr+s-1][tc+s].setBackground(col); button[tr+s-1][tc+s].setEnabled(false); button[tr+s-1][tc+s].setText("<html><Fontsize='4',color='white'>"+t+"</Font></html>"); ChessBoard(tr,tc+s,tr+s-1,tc+s,s); sleep(); } //检查特殊方块是否在左下角子棋盘中 if(dr>=tr+s&&dc<tc+s)//在 ChessBoard(tr+s,tc,dr,dc,s); else//不在，将该子棋盘右上角的方块视为特殊方块 { button[tr+s][tc+s-1].setBackground(col); button[tr+s][tc+s-1].setEnabled(false); button[tr+s][tc+s-1].setText("<html><Fontsize='4',color='white'>"+t+"</Font></html>"); ChessBoard(tr+s,tc,tr+s,tc+s-1,s); sleep(); } //检查特殊方块是否在右下角子棋盘中 if(dr>=tr+s&&dc>=tc+s)//在 ChessBoard(tr+s,tc+s,dr,dc,s); else//不在，将该子棋盘左上角的方块视为特殊方块 { button[tr+s][tc+s].setBackground(col); button[tr+s][tc+s].setEnabled(false); button[tr+s][tc+s].setText("<html><Fontsize='4',color='white'>"+t+"</Font></html>"); ChessBoard(tr+s,tc+s,tr+s,tc+s,s); sleep(); } } } publicclassOKButtonActionimplementsActionListener{ publicvoidactionPerformed(ActionEvente){ //TODOAuto-generatedmethodstub JButtonwhichButton=(JButton)e.getSource(); StringwhichName=whichButton.getActionCommand(); if(whichName.equals("开始")){ getContentPane().add(centerPanel,BorderLayout.CENTER); inttR=Integer.parseInt(TrText.getText()); inttC=Integer.parseInt(TcText.getText()); intdR=Integer.parseInt(DrText.getText()); intdC=Integer.parseInt(DcText.getText()); intSize=1; for(inti=0;i<Integer.parseInt(SizeText.getText());i++) Size*=2; tr=tR; tc=tC; dr=dR; dc=dC; size=Size; try{ gridLayoutgrid=newgridLayout(); grid.ChessBoard(tr,tc,dr,dc,size); centerPanel.updateUI(); }catch(ExceptionEX){ EX.printStackTrace(); } panel.removeAll(); OKButton.setEnabled(false); } if(whichName.equals("取消或清除")){//当你点下一个提示按钮时的事件响应 JLabellabel=newJLabel(); label.setHorizontalAlignment(JLabel.CENTER); label.setText("<html><Fontsize='+8',color='red'><center><b><br>您取消了操作或是<br><Fontsize='+8',color='blue'><center>您清除了前一个棋盘……"+ "<br><Fontsize='+8',color='green'><center>下面是关于题目的介绍<br><br><br><br><br><br></b></Font></html>");// JLabell=newJLabel("题目要求"); JTextAreaarea=newJTextArea("在一个2kx2k个方格组成的棋盘中，恰有一个方格与其他方格不同，"+ "称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，"+ "且任何2个L型骨牌不得重叠覆盖。",6,50); area.setLineWrap(true); area.setBackground(Color.blue); area.setForeground(Color.white); area.setFont(newFont("宋体",Font.BOLD,14)); area.setEditable(false); panel.add(label,centerPanel); panel.add(area,southPanel); getContentPane().add(panel,BorderLayout.CENTER); panel.updateUI(); tile=1; centerPanel.removeAll(); OKButton.setEnabled(true); } } } publicstaticvoidmain(String[]args){//主函数方法实现 ChessBoardschess=newChessBoards(); chess.setVisible(true); Runtimerun=Runtime.getRuntime(); run.gc();//手动清除数据垃圾 } }

四、实验结果实验二：矩阵连乘问题（动态规划）实验目的与要求1、明确矩阵连乘的概念。2、利用动态规划解决矩阵连乘问题。二、实验题：问题描述：给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。三、实验代码#include<iostream.h>#include<stdlib.h>#include<limits.h>#include<time.h>#defineMAX_VALUE100#defineN201//连乘矩阵的个数(n-1)#definerandom()rand()%MAX_VALUEintc[N][N],s[N][N],p[N];intmatrixchain(intn)//3个for循环实现{for(intk=1;k<=n;k++)c[k][k]=0;for(intd=1;d<n;d++)for(inti=1;i<=n-d;i++){intj=i+d;c[i][j]=INT_MAX;for(intm=i;m<j;m++){intt=c[i][m]+c[m+1][j]+p[i-1]*p[m]*p[j];if(t<c[i][j]){c[i][j]=t;s[i][j]=m;}}}returnc[1][n];}voidPrint(ints[][N],inti,intj){if(i==j)cout<<"A"<<i;else{cout<<"(";Print(s,i,s[i][j]);//左半部子矩阵连乘Print(s,s[i][j]+1,j);//左半部子矩阵连乘cout<<")";}}intlookupchain(inti,intj){if(c[i][j]>0)returnc[i][j];if(i==j)return0;intu=lookupchain(i,i)+lookupchain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}c[i][j]=u;returnu;}voidmain(){srand((int)time(NULL));for(inti=0;i<N;i++)//随机生成数组p[]，各个元素的值的范围：1~MAX_VALUEp[i]=random()+1;clock_tstart,end;doubleelapsed;start=clock();//3重for循环实现cout<<"Count:"<<lookupchain(1,N-1)<<endl;//备忘录方法end=clock();elapsed=((double)(end-start));///CLOCKS_PER_SEC;cout<<"Time:"<<elapsed<<endl;Print(s,1,N-1);//输出矩阵连乘积的计算次序cout<<endl;}

四、实验结果实验三：背包问题（贪心算法）一、实验目的与要求1、掌握背包问题的算法2、初步掌握贪心算法二、实验题：

问题描述：有一个背包容量为Ｃ，输入个物品，每个物品有重量，以及物品放入背包中所得的收益Ｐ。问选择放入的物品，不超过背包的容量，且得到的收益最好。三、实验代码#include<iostream>usingnamespacestd;//物品的信息结构structgoodsinfo{ floatp;//物品效益 floatw;//物品的重量 floatX;//物品该放的数量 intflag;//物品编号};//按物品效益，重量升序排列voidRank(goodsinfogoods[],intn){ intj,i; for(j=2;j<=n;j++){ goods[0]=goods[j]; i=j-1; while(goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; }}//背包信息voidknapsack(goodsinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M; for(i=1;i<n;i++) {if(goods[i].w>cu)break;goods[i].X=1;cu=cu-goods[i].w; }if(i<=n)goods[i].X=cu/goods[i].w;//按物品编号做降序排列for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].flag<goods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}cout<<"最优解为:"<<endl;for(i=1;i<=n;i++){cout<<"第"<<i<<"件物品要放:";cout<<goods[i].X<<endl; } } voidmain(){ cout<<"||---运用贪心算法解背包问题---"<<endl; intj,n; floatM; goodsinfo*goods; while(j) { cout<<"请输入物品的总数量："; cin>>n; goods=newstructgoodsinfo[n+1]; cout<<"请输入背包的最大容量："; cin>>M; cout<<endl; inti; for(i=1;i<=n;i++){ goods[i].flag=i; cout<<"请输入第"<<i<<"件物品的重量："; cin>>goods[i].w; cout<<"请输入第"<<i<<"件物品的效益："; cin>>goods[i].p; goods[i].p=goods[i].p/goods[i].w; cout<<endl;} Rank(goods,n); knapsack(goods,M,n); cout<<"press<1>torunagian"<<endl; cout<<"press<0>toexit"<<endl; cin>>j; } }

四、实验结果实验四：N后问题（回溯法）一、实验目的与要求1、明确回溯算法的设计策略。2、利用回溯法解决N后问题。二、实验题：问题描述：要求在一个n×n格的棋盘上放置n个皇后，使得他们彼此不攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，n后问题等价于要求在一个n×n格的棋盘上放置n个皇后，使得任何2个皇后不能被放在同一行或同一列或同一斜线上。求出问题的所有解。三、实验代码#include<iostream>#include<cstdlib>usingnamespacestd;classQueen{friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);intn,*x;longsum;};boolQueen::Place(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}intnQueen(intn){QueenX;X.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1);delete[]p;cout<<X.sum<<endl;returnX.sum;}intmain(){nQueen(4);nQueen(2);nQueen(3);return0;}

四、实验结果实验五：0-1背包问题（分支限界法）一、实验目的与要求1、掌握0-1背包问题的算法；2、初步掌握分支限界法。二、实验题：

问题描述： 利用分支限界法设计0/1背包问题的算法三、实验代码#include<stdio.h>#include<malloc.h>#defineMaxSize100//最多结点数typedefstructQNode{ floatweight;floatvalue;int ceng; //结点所在树的层数，从1开始structQNode*parent;boolleftChild;}QNode,*qnode;//存放每个结点typedefstruct{ qnodeQ[MaxSize];intfront,rear;}SqQueue;//存放结点的队列SqQueuesq;floatbestv=0;//最优解intn=0;//实际物品数floatw[MaxSize];//物品的重量floatv[MaxSize]; //物品的价值intbestx[MaxSize];//存放最优解qnodebestE;voidInitQueue(SqQueue&sq)//队列初始化{ sq.front=1; sq.rear=1;}boolQueueEmpty(SqQueuesq)//队列是否为空{ if(sq.front==sq.rear) returntrue; else returnfalse;}voidEnQueue(SqQueue&sq,qnodeb)//入队{ if(sq.front==(sq.rear+1)%MaxSize) { printf("队列已满!"); return; } sq.Q[sq.rear]=b; sq.rear=(sq.rear+1)%MaxSize;}qnodeDeQueue(SqQueue&sq)//出队{ qnodee; if(sq.front==sq.rear) { printf("队列已空!"); return0; } e=sq.Q[sq.front]; sq.front=(sq.front+1)%MaxSize; returne;}voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild){ qnodeb; if(i==n)//可行叶子