作者flyinsky76 (小雞)
看板Grad-ProbAsk
標題[資結]97中央資結
時間Sat Mar 21 12:18:01 2009
http://140.115.130.224:8080/~arhui/cexamn/exam/MA02_97_04.pdf
想請問大家第7題該如何證明比較好?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.23.202
1F：→ awpadam:用數學歸納法 對內部節點n做歸納證明 03/22 15:56
2F：→ awpadam:當n=k時成立 考慮n=k+1時 然後畫一顆樹 分成左右兩顆子樹 03/22 15:56
3F：→ awpadam:另nL為左子樹的內部節點數 nR為右子樹的內部節點數 03/22 15:57
4F：→ awpadam:IL為左子樹的內部路徑長 IR為右子樹的內部路徑長 03/22 15:58
5F：→ awpadam:EL為左子樹的外部路徑長 ER為右子樹的外部路徑長 03/22 15:58
6F：→ awpadam:可知 EL = IL + 2*nL 且 ER = IR + 2*2nR 03/22 15:59
7F：→ awpadam:且 n = nL + nR + 1 03/22 15:59
8F：→ awpadam:且E = EL + (nL+1) + ER + (nR+1) 03/22 16:00
9F：→ awpadam:且 I = IL + nL + IR + nR 03/22 16:01
10F：→ awpadam:由以上幾式推出 E = I + 2*n 得證 03/22 16:01