算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告-資料下載頁(yè)
2025-01-18 23:42本頁(yè)面
【正文】 。 } backtract(0)。 //深度優(yōu)先搜索解空間}//=============================搜索解空間====================void backtract(int i){ //到達(dá)葉節(jié)點(diǎn) if(i=n) // i表示深度（層），in搜索到葉子節(jié)點(diǎn) { bestp=cp。 for(int j=0。jn。j++) x[j]=path[j]。 return。 } //搜索子樹(shù) if(cw+w[i]=c) //當(dāng)前物品放入背包不超載 { //進(jìn)入左子樹(shù) cw+=w[i]。 cp+=p[i]。 path[i]=1。 backtract(i+1)。 //繼續(xù)向下深度搜索 cw=w[i]。 cp=p[i]。 } //進(jìn)入右子樹(shù) if(bound(i+1)bestp) //當(dāng)前的節(jié)點(diǎn)不合適時(shí)，跳到下一個(gè)結(jié)點(diǎn) { path[i]=0。 backtract(i+1)。 }}//=========== 限界函數(shù),計(jì)算當(dāng)前價(jià)值與剩余價(jià)值和==============double bound(int i){ double cleft=ccw。 // 剩余容量 double bound=cp。 // 當(dāng)前物品價(jià)值 //以物品單位重量?jī)r(jià)值遞減的順序裝入物品 while(i=namp。amp。w[i]=cleft) // 裝載剩下的物品 { cleft=w[i]。 bound+=p[i]。 i++。 } // w[ i] cleft 跳出循環(huán)，背包裝滿(mǎn),物品部分裝入背包 //裝滿(mǎn)背包 if(i=n) bound+=p[i]*cleft/w[i]。 return bound。 // 當(dāng)前物品價(jià)值與剩余物品價(jià)值之和}//===========================主函數(shù)=============================void main(){ Input()。 knapsack()。 Output()。}棋盤(pán)覆蓋問(wèn)題include include include //聲明變量int title=1。 //L型骨牌號(hào)int board[64][64]。 //二維數(shù)組board[ ][ ]，模擬棋盤(pán)/*tr 棋盤(pán)中左上角方格所在行。tc 棋盤(pán)中左上角方格所在列。dr 殘缺方塊所在行。dl 殘缺方塊所在列。size:棋盤(pán)的行數(shù)或列數(shù)*/void chessBoard(int tr,int tc,int dr,int dc,int size){ int s,t。 if(size==1) return。 //size:棋盤(pán)行數(shù) t=title++。 //L型骨牌號(hào) s=size/2。 // 分割棋盤(pán) // 覆蓋左上角子棋盤(pán) if(drtr+s amp。amp。 dctc+s) //特殊方格在此棋盤(pán)中 chessBoard(tr,tc,dr,dc,s)。 else // 此棋盤(pán)中無(wú)特殊方格 { board[tr+s1][tc+s1]=t。 // 用 t 號(hào)L型骨牌覆蓋右下角 chessBoard(tr,tc,tr+s1,tc+s1,s)。 // 覆蓋其余方格 } // 覆蓋右上角子棋盤(pán) if(drtr+s amp。amp。 dc=tc+s) //特殊方格在此棋盤(pán)中 chessBoard(tr,tc+s,dr,dc,s)。 else // 此棋盤(pán)中無(wú)特殊方格 { board[tr+s1][tc+s]=t。 // 用 t 號(hào)L型骨牌覆蓋左下角 chessBoard(tr,tc+s,tr+s1,tc+s,s)。 // 覆蓋其余方格 } // 覆蓋左下角子棋盤(pán) if(dr=tr+s amp。amp。 dctc+s) //特殊方格在此棋盤(pán)中 chessBoard(tr+s,tc,dr,dc,s)。 else // 此棋盤(pán)中無(wú)特殊方格 { board[tr+s][tc+s1]=t。 //用 t 號(hào)L型骨牌覆蓋右上角 chessBoard(tr+s,tc,tr+s,tc+s1,s)。 //覆蓋其余方格 } //覆蓋右下角子棋盤(pán) if(dr=tr+s amp。amp。 dc=tc+s) //特殊方格在此棋盤(pán)中 chessBoard(tr+s,tc+s,dr,dc,s)。 else // 此棋盤(pán)中無(wú)特殊方格 { board[tr+s][tc+s]=t。 // 用 t 號(hào)L型骨牌覆蓋左上角 chessBoard(tr+s,tc+s,tr+s,tc+s,s)。 //覆蓋其余方格 }}//=============主函數(shù)======================================void main(){ int dr=0,dc=0,s=1,i=0,j=0。 printf(請(qǐng)輸入棋盤(pán)的size(大小必須是2的n次冪):\n)。 scanf(%d,amp。s)。 printf(請(qǐng)輸入特殊方格位置的坐標(biāo)( x,y):\n)。 scanf(%d%d,amp。dr,amp。dc)。 if(drs amp。amp。 dcs) { chessBoard(0,0,dr,dc,s)。 for(i=0。is。i++) { for(j=0。js。j++) { printf(%4d,board[i][j])。 } printf(\n)。 } } else { printf(the wrong specal point!!\n)。 } getch()。 return 。}八、參考文獻(xiàn)[1].王曉東編著. 算法設(shè)計(jì)與分析(第2版).北京:清華大學(xué)出版社,2008年1月第2版[2].肖南峰，任劍洪，——:清華大學(xué)出版社,2012年9月第1版[3].朱振元，++程序設(shè)計(jì)與應(yīng)用開(kāi)發(fā). 北京:清華大學(xué)出版社,2005年2月第1版[4]. 張永，李睿，. 北京: 國(guó)防工業(yè)出版社,2008年8月第1版 27
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1