cy分治解題報告ppt課件(參考版)
2024-12-11 02:42本頁面
【正文】 Answer 。要熟悉用遞歸關(guān)系來表達(dá)問題。做的時候同樣要注意去除重復(fù)計算，這個方法就叫做動態(tài)規(guī)劃。 小結(jié) ? 本題也可以倒著推，從葉子節(jié)點逐步往上窮舉著色方案。 編制測試數(shù)據(jù) ? 用手工可以檢驗的小數(shù)據(jù)，驗證程序的正確性 ? 編寫程序隨機生成大數(shù)據(jù)，檢驗程序的執(zhí)行效率（使用隨機函數(shù)） ? 注意檢驗邊界條件。 return m。 } if (j==0) m++。k2!=k1) { t=maximal(son[i][0],k1)+maximal(son[i][1],k2)。k2++) if (k2!=jamp。k1++) if (k1!=j) for (k2=0。 for (k1=0。 if (max[i][j]!=1) return max[i][j]。 ?n10000 ?本算法在 幾年 之內(nèi)無法得出結(jié)果！ 算法改進(jìn) (1,red) (1,green) (0,blue) (2,blue) (2,green) (2,red) (2,blue) 可以用一個數(shù)組記錄下已經(jīng)搜索過的子問題的答案，避免重復(fù)搜索 記憶化搜索 int maximal(int i,int j) { int k1,k2,t,m。算法效率分析 01( , ) m a x{ ( ( , 0), 1 ) ( ( , 1 ) , 2)} 1m a x{ ( ( , 0), 1 ) ( ( , 1 ) , 2)} 1 11 2 { , , }iF i j F so n i j F so n i j i j gr e e nF so n i j F so n i j i j gr e e nj j j re d gr e e n bl ue????? ? ?? ? ???? ? ? ?? ? ???其 中 、 、 但 互 不 相 同 。 return m。 if (tm) m=t。amp。k23。k13。 m=1。源程序 int maximal(int i,int j) { int k1,k2,t,m。 ? 如何系統(tǒng)的、不遺漏的窮舉所有方案？ ? 嘗試找出問題的遞歸結(jié)構(gòu)： ? 設(shè) f(i,j)表示以編號是 i、顏色是 j的節(jié)點為根節(jié)點的子樹，在滿足約束條件的情況下染色，綠色節(jié)點最多（最少）有多少個。 build()。 build()。 } /*str[pl]==‘2’*/ son[pl][0]=pl+1。 build()。) { son[pl][0]=pl+1。 } if (str[pl]==39。 pl++。) { son[pl][0]=1。 if (pln) { if (str[pl]==39。 ? 如何將輸入串轉(zhuǎn)化為我們定義的數(shù)據(jù)結(jié)構(gòu)？ ? 能否記錄每個節(jié)點的父親？ 建立數(shù)據(jù)結(jié)構(gòu) int pl=0。 S=21202210 數(shù)據(jù)結(jié)構(gòu) ? 二叉樹的表示 ? 給二叉樹上所有節(jié)點標(biāo)號，從 1~N。并且，一個節(jié)點與其子節(jié)點的顏色必須不同，如果該節(jié)點有兩個子節(jié)點，那么這兩個子節(jié)點的顏色也必須不相同。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1