作者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