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

计算机算法设计与分析实验报告 专 业： 测试技术10-01 学 号： 54101311 姓 名： XXX指导老师： 宋 胜 利实验一：棋盘覆盖一、实验目的与要求1、理解算法的概念2、实现棋盘化以及棋盘覆盖二、实验题：1、编程任务：设计棋盘覆盖的一个简单算法2、输入数据：输入特殊方格的行号和特殊方格的列号以及棋盘的大小3、结果输出：将计算结果输出显示棋盘三、实验代码：package two;import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.*;import java.util.*; /* * * author 黄建强 */public class FenZi public static void main(String args) new MyChessBoard(); class MyChessBoard extends JFrame implements ActionListener int dimen; /棋盘规模 int x_pos; /特殊点横坐标 int y_pos; /特殊点竖坐标 Container p; public MyChessBoard() super(); x_pos = 0; y_pos = 0; dimen = 0; setTitle(棋盘覆盖); setBackground(Color.YELLOW); setBounds(300,150,510,480); centreOnScreen(); /setResizable(false); p = getContentPane(); JMenuBar jmb = new JMenuBar(); JMenu jm = new JMenu(操作); JMenuItem jitem1 = new JMenuItem(开始); JMenuItem jitem2 = new JMenuItem(退出); jm.add(jitem1); jm.add(jitem2); jmb.add(jm); setJMenuBar(jmb); jitem1.addActionListener(this); jitem2.addActionListener(this); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setVisible(true); public void centreOnScreen() /使窗体显示在屏幕中央 Dimension displaySize = getToolkit().getScreenSize(); Dimension winSize = getSize(); int x = (displaySize.width - winSize.width) / 2; int y = (displaySize.height - winSize.height) / 2; if(x 0) x = 0; if(y 0) y = 0; setLocation(x, y); public void actionPerformed(ActionEvent e) if(e.getActionCommand()=退出) System.exit(0); else if(e.getActionCommand()=开始) /在此输入方阵大小 JOptionPane jop = new JOptionPane(); jop.setVisible(true); do dimen = Integer.parseInt(JOptionPane.showInputDialog(p,输入方阵的行数：,输入棋盘的行数：（提示是2的指数）,JOptionPane.INFORMATION_MESSAGE); if(dimen/2=0) dimen=Integer.parseInt(JOptionPane.showInputDialog(p,请你重新输入:,输入棋盘的行数：（提示是2的指数）,JOptionPane.INFORMATION_MESSAGE); while(dimen/2=0); System.out.println(dimen); x_pos = (int)(dimen*Math.random(); /随机生成特殊点位置 y_pos = (int)(dimen*Math.random(); p.setLayout(new GridLayout(dimen, dimen); System.out.println(x_pos+,+y_pos); ChessBoard cb = new ChessBoard(dimen); cb.coverMethod(0, 0, x_pos, y_pos, dimen); int board = cb.getBoard(); JButton btn; for(int i=0; iboard.length; i+) for(int j=0; jboardi.length; j+) if(boardij = 0) btn = new JButton(); btn.setFont(new Font(, Font.BOLD, 24); btn.setForeground(Color.red); btn.setBackground(new Color(0, 0, 0); else btn = new JButton(); btn.setBackground(new Color(boardij*134)%255, /生成0-255的值，并与boardij建立关系 (boardij*145)%255, (boardij*178)%255); p.add(btn); System.out.println(bbbb); this.setVisible(true); class ChessBoard int board; int tile; ChessBoard(int k) board = new int kk; /k*k的数组，保存最终结果 tile = 0; void coverMethod(int tr,int tc,int dr,int dc,int size) /棋盘覆盖 if(size = 1) return; int t = +tile; int s = size/2; if(drtr+s & dctc+s) coverMethod(tr,tc,dr,dc,s); else boardtr+s-1tc+s-1 = t; coverMethod(tr,tc,tr+s-1,tc+s-1,s); if(dr=tc+s) coverMethod(tr,tc+s,dr,dc,s); else boardtr+s-1tc+s = t; coverMethod(tr,tc+s,tr+s-1,tc+s,s); if(dr=tr+s & dc=tr+s & dc=tc+s) coverMethod(tr+s,tc+s,dr,dc,s); else boardtr+stc+s = t; coverMethod(tr+s,tc+s,tr+s,tc+s,s); public int getBoard() /返回覆盖结果 return board; 四、实验结果输入行数，如：8，然后点击确定：运行如下实验二：矩阵连乘一、 实验目标通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。二、 实验内容1.用动态规划算法解矩阵连乘问题2.算法设计思想动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 本实验的算法思路是： 1、计算最优值算法MatrixChain()：建立两张表（即程序中的*m和*s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2、输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。三、 实验代码#include using namespace std; const int MAX = 100; /p用来记录矩阵的行列，main函数中有说明 /mij用来记录第i个矩阵至第j个矩阵的最优解 /s用来记录从哪里断开的才可得到该最优解 int pMAX+1,mMAXMAX,sMAXMAX; int n;/矩阵个数 int matrixChain() for(int i=0;i=n;i+) mii=0;for(int r=2;r=n;r+)/对角线循环 for(int i=0;i=n-r;i+)/行循环 int j = r+i-1;/列的控制 /找mij的最小值，先初始化一下，令k=i mij=mi+1j+pi+1*pi*pj +1; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi*pk+1*pj+1; if(tempmij) mij=temp; /s用来记录在子序列i-j段中，在k位置处 /断开能得到最优解 sij=k; return m0n-1;/根据s记录的各个子段的最优解，将其输出void traceback(int i,int j) if(i=j) coutAi; return ; if(isij) cout(;traceback(i,sij);if(isij) cout);if(sij+1j) cout(;traceback(sij+1,j);if(sij+1j) cout);void traceback() cout(;traceback(0,n-1); cout); coutendl;int main() cout请输入矩阵的个数：n; cout输入矩阵（形如a*b,中间用空格隔开）:endl; for(int i=0;ipi; /测试数据可以设为六个矩阵分别为 /A130*35,A235*15,A315*5,A45*10,A510*20,A620*25 /则p0-6=30,35,15,5,10,20,25 cout输出结果如下：endl; matrixChain();traceback(0,n-1);/最终解值为m0n-1;coutendl;return 0;四、 实验结果实验三：0-1背包问题一、实验目的与要求1、明确0-1背包问题的概念2、利用动态规划解决0-1背包问题问题二、实验题：0-1背包问题(knapsack problem)， 某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为W，W为一非负数。目标是如何选择装入背包的物品， 使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何？背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分， 而不一定要选择物品的全部。可将这个问题形式描述如下： 约束条件为： 三、实验代码#include #include #include int min(int w,int c) int temp; if (wc) temp=w; else temp=c; return temp; void knapsack(int v,int w,int c,int n,int*m) /求最优值 int jmax=min(wn-1,c); for(int j=0;j=jmax;j+) mnj=0; for(int jj=wn;jj1;i-) /递归部分 jmax=min(wi-1,c); for(int j=0;j=jmax;j+) mij=mi+1j; for(int jj=wi;jj=w1) m1c=max(m1c,m2c-w1+v1); cout最优值：m1cendl; coutendl; cout*endl; int traceback(int *m,int w,int c,int n,int x) /回代，求最优解 cout得到的一组最优解如下:endl; for(int i=1;in;i+) if(mic=mi+1c) xi=0; else xi=1; c-=wi; xn=(mnc)?1:0; for(int y=1;y=n;y+) coutsetw(5)xy; coutendl; return xn; void main() int n,c; int *m; coutnc; int *v=new intn+1; cout请输入价值 (vi):endl; for(int i=1;ivi; int *w=new intn+1; cout请输入重量 (wi):endl; for(int j=1;jwj; int *x=new intn+1; m=new int*n+1; /动态的分配二维数组 for(int p=0;pn+1;p+) mp=new intc+1; knapsack(v,w,c,n,m); traceback(m,w,c,n,x);四、实验结果实验四：八皇后问题一、实验目标：使用深度优先搜索算法以及回溯法的思想进行暴力解题二、实验任务：用8*8的二维数组去模拟皇后所在的棋盘，然后用1标记该位置可以放皇后，用0来标记该位置不可以放皇后。然后每次有一个合理的八皇后方案，就会counter+，记录摆放的方法，并且输出皇后摆放的坐标。三、实验步骤：1.明确实验目标和实验任务2.理解实验所涉及到深度优先搜索的算法以及回溯法的思想3.编写程序实现求解八皇后问题。4.设计实验数据数据并运行程序，记录运行的结果四、实验代码:#includeusing namespace std;struct chessboardint b88; /对棋盘的模拟;struct locationint x,y; /记录皇后放的坐标;chessboard visited9; location loc8;int num;/记录有多少种方法void print()/输出皇后的方法以及种数int i; cout+numends;for(i=0;i=7;i+)coutloci.xendsloci.yends;coutendl;int x1,y1,x2,y2; /用于标记坐标void visit(int x,int y,int step)int i;x1=x;y1=y;x2=x;y2=y;visitedstep=visitedstep-1;/把上一次标记过不能走的坐标传到下一次for(i=0;i8;i+)visitedstep.bxi=0;/与皇后同行的都标为不能放visitedstep.biy=0;/与皇后同列的都标为不能放while(x18 & y18)visitedstep.bx1y1=0;/与皇后对角线的标记为不能放x1+;y1+; while(x2=0)visitedstep.bx2y2=0;/与皇后对角线的标记为不能放x2+;y2-;void dfs(int step)int j;if(step=9)print();elsefor(j=0;j8;j+)if(visitedstep-1.bstep-1j) locstep-1.x=step-1;/放置皇后的位置locstep-1.y=j;visit(step-1,j,step);/进行标记dfs(step+1);/递归进行下一个int main()num=0;/初始化计数变量nummemset(visited,1,sizeof(visited);/初始化visited标记数组dfs(1);/从1开始，1作为步骤参数return 0;五、实验结果实验五：分支限界法求解0-1背包问题一、 实验目的 分支限界法求解0-1背包问题二、 实验内容0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、 实验代码#include #include#define MaxSize 100 /最多结点数typedef struct QNode float weight; float value; intceng; struct QNode *parent; bool leftChild;QNode,*qnode; /存放每个结点typedef struct qnode QMaxSize; int front,rear;SqQueue; /存放结点的队列SqQueue sq;float bestv=0; /最优解int n=0; /实际物品数float wMaxSize; /物品的重量float vMaxSize;/物品的价值int bestxMaxSize; / 存放最优解qnode bestE;void InitQueue(SqQueue &sq ) /队列初始化sq.front=1;sq.rear=1;bool QueueEmpty(SqQueue sq) /队列是否为空if(sq.front=sq.rear)return true;else return false;void EnQueue(SqQueue &sq,qnode b)/入队if(sq.front=(sq.rear+1)%MaxSize)printf(队列已满!);return ;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue &sq)/出队qnode e;if(sq.front=sq.rear)printf(队列已空!);return 0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;return e;void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if (i=n) /可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode); /非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent; b-leftChild=leftchild; EnQueue(sq,b); void maxLoading(float w,float v,int c