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