算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告-資料下載頁
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）復(fù)雜度分析時(shí)間復(fù)雜度為O(nlgn)（3）問題及解決2．0/1背包問題（1）輸出結(jié)果（2）復(fù)雜度分析計(jì)算上界需要O(n)時(shí)間，在最壞的情況下有O(pow(2,n))個(gè)右兒子結(jié)點(diǎn)需要計(jì)算上界所以01背包問題的回溯算法所需的計(jì)算時(shí)間為O(*npow(2,n))。（3）問題及解決3．棋盤覆蓋問題（1）輸出結(jié)果（2）復(fù)雜度分析設(shè)T（n）是算法ChessBoard覆蓋一個(gè)2^k *2^k棋盤所需要的時(shí)間，則從算法的分治策略可知，T(k)滿足如下遞歸方程： T(k)= k=0k0 解得此遞歸方程可得T(k) = O（4^k）。由于覆蓋一個(gè)2^k *2^k棋盤所需的L型骨牌個(gè)數(shù)為（4^k — 1）/3,故算法ChessBoard是一個(gè)在漸進(jìn)意義下最優(yōu)的算法（3）問題及解決七、結(jié)論1．普通背包問題普通背包問題采用的是貪心算法。2．0/1背包問題01背包問題采用的是回溯算法3．棋盤覆蓋問題棋盤覆蓋問題采用的是分治算法總結(jié)所解決的問題（采用的什么算法，怎么設(shè)計(jì)的，還存在哪些問題有待改進(jìn)等內(nèi)容）。八、參考文獻(xiàn)（6個(gè)）參考文獻(xiàn)要注明作者、出版社、出版日期。如[1] [M].北京：科學(xué)出版社，2005: 25163.[2] Brian HendersonSellers. A Book of ObjectOriented Knowledge: An Introduction to ObjectOriented Software Engineering[M].PrenticeHall, 1993: 39113
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1