2011-01-16

想確認一下作法 跟一些問題


2.想請問第二提 可以寫等價於T(N)=T(N/2)+1 這樣下去解嗎

3.這是出在數學考捲上的問題 不知道可以用MASTER定理直接解嗎? 還是要用數學的解法
題目有說divide and conquer 如果試用數學解法 可以畫樹嗎


5.可以舉個例子 然後寫出尤拉定義,然後找一條路徑給他嗎?

6.關於這提我跟同學討論過後 ,他的樹比我高卻比我 總權重卻較少 ,當10+15=25時 這時要抓一個20跟他作 ,還是另外建一個20跟25 一起作,我用前面後者 因為我想樹會比較矮

8.請問這提答案完整的定義應該怎描述 我只會寫 ab* or ab*ab* 還是寫一個程式碼給他去判斷這個狀態 接收

1 則留言:

線代離散助教(wynne) 提到...

2, 3: 離散考卷上的問題最好都用解遞迴來求出它的closed form, 用master theorem只能求出一個近似值, 會顯得不夠完整; 如果要畫樹出來說明, 只要有確實的計算出樹高, 用圖來輔助說明也很好

5. OK

6. 有時候遇到這種問題時要稍微想一下如果是寫成程式你會怎麼寫, 通常Huffman tree上的演算法我們會用priority queue來做為輔助的資料結構, 而如果把裡面的元素取出來合併之後應該是要再重新放回queue裡面去, 那在執行時就要依照著queue先進先出的順序來走才比較合理

7. 看題意應該是要寫成pseudocode, 如果你fsa畫得出來, 我覺得把fsa改成演算法應該就不會很難了