作者suhorng ( )
看板b00902HW
標題[討論] 單班 11.1
時間Tue Dec 6 23:26:26 2011
很多人滿分了，可是 Scoreboard 上也有一些 9 分的
今天跟一個同學研究的結論是記憶體動態開會比較理想
也就是說，若直接用陣列把資料個數開好的話，需要把空間開足夠
但是這題的測資很大，而且好像挺接近記憶體限制的邊界，
所以稍微開大一點很容易記憶體超過限制當掉，不容易抓到剛好的邊界
一種方法可以是先掃過一次得到正確的記憶體數量，再動態的開陣列
(動態記憶體或是 int a[n]; 之類的, 雖然後者不太正規, 但都可以通過測試)
我個人寫遞迴, 確實可過(Linux 上遞迴可以超深....), 也挺好寫的
另外要注意一下有可能輸入的本來就是空指標... 什麼也不用印
-
另外HW11還滿少人寫的...不過雖然這章教了二元搜尋樹、鏈結串列、...etc,
但是HW11不一定要把二元搜尋樹建出來XD 雖然我不知道老師出這題是希望看到
怎樣的解法...
輸入給的級別可能是個提示吧，舉例來說
r
____________／
／
s
／ ＼
／ ＼
a d
／ ＼ ＼
b c e
＼
f
則 c、f 的級別分別是 4 和 5 (呃....好像一般比較常叫這個東西'深度'? depth)
此外, s 是從 r 走到 c、以及 r 走到 f 的路中最後一個共通的節點, 級別為 1
可以觀察到 c、f 之間的距離是 c 到 s 的距離 + s 到 f 的距離
而 c 到 s 的距離是 c 的級別減去 s 的級別,
f 到 s 的距離是 f 的級別減去 s 的級別.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.32.126
1F：推 tiefblau:遞迴！ 12/06 23:32
2F：→ suhorng:是唷XD 五行短短的很開心 12/06 23:34
※ 編輯: suhorng 來自: 61.217.32.126 (12/06 23:56)
3F：→ telgniw:九分通常是爆NULL 12/07 08:06
4F：→ telgniw:然後書泓你幹麼講出來這題不用建treeQQ 12/07 08:08
5F：→ suhorng:qq因為輸入實在太奇怪了 一般二元搜尋樹應該會照順序給鍵 12/07 08:54
6F：→ suhorng:值不給深度 但是這題卻是不照順序給鍵值然後給深度 12/07 08:54
7F：推 hasheesh:HW11 judegegirl 網站上看不到題目 QQ 12/07 11:48
8F：推 bemyself:請問有沒有測資沒有深度為1的點? 或是有兩個以上? 12/07 17:07
9F：→ suhorng:不太懂意思, 根節點不就是唯一的深度為 1 的點嗎 ? 12/07 17:40