算法設計與分析課程設計報告-資料下載頁
2025-08-05 11:01本頁面
【正文】 d(tr,tc,dr,dc,s)。 } else { Matrix[tr+s1][tc+s1] = t。 chessBoard(tr,tc,tr+s1,tc+s1,s)。 } //locate the special grid on bottom left corner if (dr tr + s amp。amp。 dc = tc + s ) { chessBoard(tr,tc+s,dr,dc,s)。 } else { Matrix[tr+s1][tc+s] = t。 chessBoard(tr,tc+s,tr+s1,tc+s,s)。 } //locate the special grid on top right corner if (dr = tr + s amp。amp。 dc tc + s) { chessBoard(tr+s,tc,dr,dc,s)。 } else { Matrix[tr+s][tc+s1] = t。 chessBoard(tr+s,tc,tr+s,tc+s1,s)。 } //locate the special grid on top left corner if (dr = tr + s amp。amp。 dc = tc + s) { chessBoard(tr+s,tc+s,dr,dc,s)。 } else { Matrix[tr+s][tc+s] = t。 chessBoard(tr+s,tc+s,tr+s,tc+s,s)。 }}六、測試分析1．普通背包問題（1）輸出結(jié)果（2）復雜度分析時間復雜度為O(nlgn)（3）問題及解決2．0/1背包問題（1）輸出結(jié)果（2）復雜度分析計算上界需要O(n)時間，在最壞的情況下有O(pow(2,n))個右兒子結(jié)點需要計算上界所以01背包問題的回溯算法所需的計算時間為O(*npow(2,n))。（3）問題及解決3．棋盤覆蓋問題（1）輸出結(jié)果（2）復雜度分析設T（n）是算法ChessBoard覆蓋一個2^k *2^k棋盤所需要的時間，則從算法的分治策略可知，T(k)滿足如下遞歸方程： T(k)= k=0k0 解得此遞歸方程可得T(k) = O（4^k）。由于覆蓋一個2^k *2^k棋盤所需的L型骨牌個數(shù)為（4^k — 1）/3,故算法ChessBoard是一個在漸進意義下最優(yōu)的算法（3）問題及解決七、結(jié)論1．普通背包問題普通背包問題采用的是貪心算法。2．0/1背包問題01背包問題采用的是回溯算法3．棋盤覆蓋問題棋盤覆蓋問題采用的是分治算法總結(jié)所解決的問題（采用的什么算法，怎么設計的，還存在哪些問題有待改進等內(nèi)容）。八、參考文獻（6個）參考文獻要注明作者、出版社、出版日期。如[1] [M].北京：科學出版社，2005: 25163.[2] Brian HendersonSellers. A Book of ObjectOriented Knowledge: An Introduction to ObjectOriented Software Engineering[M].PrenticeHall, 1993: 39113
畢業(yè)設計相關(guān)推薦
鄂ICP備17016276號-1