計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告_第1頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告_第2頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告_第3頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告_第4頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告_第5頁(yè)
已閱讀5頁(yè)，還剩16頁(yè)未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告專業(yè)：java技術(shù)學(xué)號(hào)：541213440245姓名：徐亞濤指導(dǎo)老師：谷培培實(shí)驗(yàn)一：棋盤覆蓋（遞歸與分治策略）一、實(shí)驗(yàn)?zāi)康呐c要求1、明確棋盤覆蓋的概念2、明確遞歸與分治策略的設(shè)計(jì)思路。3、利用遞歸與分治策略解決棋盤覆蓋問(wèn)題。二、實(shí)驗(yàn)題：

問(wèn)題描述：遞歸與分治策略算法，用4種不同形態(tài)的L型骨牌覆蓋一個(gè)給定的特殊棋盤上除特殊方格以外的所有方格,且任何2個(gè)L型骨牌不得重疊覆蓋。輸入數(shù)據(jù)由程序運(yùn)行后的界面中的編輯框中輸入游戲規(guī)模,特殊方格的位置。將覆蓋的結(jié)果在窗口中顯示出來(lái)。三、實(shí)驗(yàn)代碼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);//設(shè)置窗口大小與位置 TrText=newJTextField("0",2);//定義各組件 TcText=newJTextField("0",2); DrText=newJTextField("0",2); DcText=newJTextField("0",2); SizeText=newJTextField("4",2); TrLabel=newJLabel("起始方格坐標(biāo)x:"); TcLabel=newJLabel("起始方格坐標(biāo)y:"); DrLabel=newJLabel("特殊方格坐標(biāo)x:"); DcLabel=newJLabel("特殊方格坐標(biāo)y:"); SizeLabel=newJLabel("棋盤規(guī)模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){//算法實(shí)現(xiàn) if(size==1)//棋盤方格大小為1,說(shuō)明遞歸到最里層 return; intt=tile++;//每次遞增1 Randomrd=newRandom(); red=rd.nextFloat(); green=rd.nextFloat(); blue=rd.nextFloat(); Colorcol=newColor(red,green,blue); sleep(); ints=size/2;//棋盤中間的行、列號(hào)(相等的) //檢查特殊方塊是否在左上角子棋盤中 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("取消或清除")){//當(dāng)你點(diǎn)下一個(gè)提示按鈕時(shí)的事件響應(yīng) JLabellabel=newJLabel(); label.setHorizontalAlignment(JLabel.CENTER); label.setText("<html><Fontsize='+8',color='red'><center><b><br>您取消了操作或是<br><Fontsize='+8',color='blue'><center>您清除了前一個(gè)棋盤……"+ "<br><Fontsize='+8',color='green'><center>下面是關(guān)于題目的介紹<br><br><br><br><br><br></b></Font></html>");// JLabell=newJLabel("題目要求"); JTextAreaarea=newJTextArea("在一個(gè)2kx2k個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，"+ "稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問(wèn)題中，要用4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，"+ "且任何2個(gè)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){//主函數(shù)方法實(shí)現(xiàn) ChessBoardschess=newChessBoards(); chess.setVisible(true); Runtimerun=Runtime.getRuntime(); run.gc();//手動(dòng)清除數(shù)據(jù)垃圾 } }

四、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)二：矩陣連乘問(wèn)題（動(dòng)態(tài)規(guī)劃）實(shí)驗(yàn)?zāi)康呐c要求1、明確矩陣連乘的概念。2、利用動(dòng)態(tài)規(guī)劃解決矩陣連乘問(wèn)題。二、實(shí)驗(yàn)題：?jiǎn)栴}描述：給定n個(gè)矩陣｛A1,A2,...,An｝，其中Ai與Ai+1是可乘的，i=1，2...，n-1。確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個(gè)數(shù)和每個(gè)矩陣規(guī)模，輸出結(jié)果為計(jì)算矩陣連乘積的計(jì)算次序和最少數(shù)乘次數(shù)。三、實(shí)驗(yàn)代碼#include<iostream.h>#include<stdlib.h>#include<limits.h>#include<time.h>#defineMAX_VALUE100#defineN201//連乘矩陣的個(gè)數(shù)(n-1)#definerandom()rand()%MAX_VALUEintc[N][N],s[N][N],p[N];intmatrixchain(intn)//3個(gè)for循環(huán)實(shí)現(xiàn){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++)//隨機(jī)生成數(shù)組p[]，各個(gè)元素的值的范圍：1~MAX_VALUEp[i]=random()+1;clock_tstart,end;doubleelapsed;start=clock();//3重for循環(huán)實(shí)現(xiàn)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);//輸出矩陣連乘積的計(jì)算次序cout<<endl;}

四、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)三：背包問(wèn)題（貪心算法）一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握背包問(wèn)題的算法2、初步掌握貪心算法二、實(shí)驗(yàn)題：

問(wèn)題描述：有一個(gè)背包容量為Ｃ，輸入個(gè)物品，每個(gè)物品有重量，以及物品放入背包中所得的收益Ｐ。問(wèn)選擇放入的物品，不超過(guò)背包的容量，且得到的收益最好。三、實(shí)驗(yàn)代碼#include<iostream>usingnamespacestd;//物品的信息結(jié)構(gòu)structgoodsinfo{ floatp;//物品效益 floatw;//物品的重量 floatX;//物品該放的數(shù)量 intflag;//物品編號(hào)};//按物品效益，重量升序排列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;//按物品編號(hào)做降序排列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<<"最優(yōu)解為:"<<endl;for(i=1;i<=n;i++){cout<<"第"<<i<<"件物品要放:";cout<<goods[i].X<<endl; } } voidmain(){ cout<<"||---運(yùn)用貪心算法解背包問(wèn)題---"<<endl; intj,n; floatM; goodsinfo*goods; while(j) { cout<<"請(qǐng)輸入物品的總數(shù)量："; cin>>n; goods=newstructgoodsinfo[n+1]; cout<<"請(qǐng)輸入背包的最大容量："; cin>>M; cout<<endl; inti; for(i=1;i<=n;i++){ goods[i].flag=i; cout<<"請(qǐng)輸入第"<<i<<"件物品的重量："; cin>>goods[i].w; cout<<"請(qǐng)輸入第"<<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; } }

四、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)四：N后問(wèn)題（回溯法）一、實(shí)驗(yàn)?zāi)康呐c要求1、明確回溯算法的設(shè)計(jì)策略。2、利用回溯法解決N后問(wèn)題。二、實(shí)驗(yàn)題：?jiǎn)栴}描述：要求在一個(gè)n×n格的棋盤上放置n個(gè)皇后，使得他們彼此不攻擊。按照國(guó)際象棋的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子。因此，n后問(wèn)題等價(jià)于要求在一個(gè)n×n格的棋盤上放置n個(gè)皇后，使得任何2個(gè)皇后不能被放在同一行或同一列或同一斜線上。求出問(wèn)題的所有解。三、實(shí)驗(yàn)代碼#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;}

四、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)五：0-1背包問(wèn)題（分支限界法）一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握0-1背包問(wèn)題的算法；2、初步掌握分支限界法。二、實(shí)驗(yàn)題：

問(wèn)題描述： 利用分支限界法設(shè)計(jì)0/1背包問(wèn)題的算法三、實(shí)驗(yàn)代碼#include<stdio.h>#include<malloc.h>#defineMaxSize100//最多結(jié)點(diǎn)數(shù)typedefstructQNode{ floatweight;floatvalue;int ceng; //結(jié)點(diǎn)所在樹的層數(shù)，從1開始structQNode*parent;boolleftChild;}QNode,*qnode;//存放每個(gè)結(jié)點(diǎn)typedefstruct{ qnodeQ[MaxSize];intfront,rear;}SqQueue;//存放結(jié)點(diǎn)的隊(duì)列SqQueuesq;floatbestv=0;//最優(yōu)解intn=0;//實(shí)際物品數(shù)floatw[MaxSize];//物品的重量floatv[MaxSize]; //物品的價(jià)值intbestx[MaxSize];//存放最優(yōu)解qnodebestE;voidInitQueue(SqQueue&sq)//隊(duì)列初始化{ sq.front=1; sq.rear=1;}boolQueueEmpty(SqQueuesq)//隊(duì)列是否為空{(diào) if(sq.front==sq.rear) returntrue; else returnfalse;}voidEnQueue(SqQueue&sq,qnodeb)//入隊(duì){ if(sq.front==(sq.rear+1)%MaxSize) { printf("隊(duì)列已滿!"); return; } sq.Q[sq.rear]=b; sq.rear=(sq.rear+1)%MaxSize;}qnodeDeQueue(SqQueue&sq)//出隊(duì){ qnodee; if(sq.front==sq.rear) { printf("隊(duì)列已空!"); return0; } e=sq.Q[sq.front]; sq.front=(sq.front+1)%MaxSize; returne;}voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild){ qnodeb; if(i==n)//可行葉子

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論