[資結]97中央資結

看板Grad-ProbAsk作者 (小雞)時間17年前 (2009/03/21 12:18), 編輯推噓0(0推 0噓 10→)
留言10則, 1人參與, 最新討論串1/5 (看更多)
http://140.115.130.224:8080/~arhui/cexamn/exam/MA02_97_04.pdf 想請問大家第7題該如何證明比較好? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.216.23.202
→
03/22 15:56, , 1F
用數學歸納法 對內部節點n做歸納證明
03/22 15:56, 1F
→
03/22 15:56, , 2F
當n=k時成立 考慮n=k+1時 然後畫一顆樹 分成左右兩顆子樹
03/22 15:56, 2F
→
03/22 15:57, , 3F
另nL為左子樹的內部節點數 nR為右子樹的內部節點數
03/22 15:57, 3F
→
03/22 15:58, , 4F
IL為左子樹的內部路徑長 IR為右子樹的內部路徑長
03/22 15:58, 4F
→
03/22 15:58, , 5F
EL為左子樹的外部路徑長 ER為右子樹的外部路徑長
03/22 15:58, 5F
→
03/22 15:59, , 6F
可知 EL = IL + 2*nL 且 ER = IR + 2*2nR
03/22 15:59, 6F
→
03/22 15:59, , 7F
且 n = nL + nR + 1
03/22 15:59, 7F
→
03/22 16:00, , 8F
且E = EL + (nL+1) + ER + (nR+1)
03/22 16:00, 8F
→
03/22 16:01, , 9F
且 I = IL + nL + IR + nR
03/22 16:01, 9F
→
03/22 16:01, , 10F
由以上幾式推出 E = I + 2*n 得證
03/22 16:01, 10F
‣ 更多 flyinsky76 的文章
文章代碼(AID): #19n6fwve (Grad-ProbAsk)
‣ 更多 flyinsky76 的文章
文章代碼(AID): #19n6fwve (Grad-ProbAsk)