※ 引述《ooww (选ばれし子どもたち)》之铭言： : 题目 : https://reurl.cc/R6MYGg : 若有一棵 k 元树（k_ary tree）其中分支度（degree）为 i 的节点数为 i 个， : i = 1, 2, ..., k， : 请问该 k 元树其叶节点数 L(k)为何？ : 诚心发问此题目 : 完整回答者，愿付300P做为报酬 : (是不是要自己假设树的高度?) 我先给你个例子 你可以很快得到答案 https://imgur.com/WoveMY2 所以公式 : L(K)=1+1*2+2*3 如果i=3 一般形式为 L(K)=1+ sigma_{2 to i} (i-1)*i 证明: 对於树而言 有 节点数-1=边数 边数 对於deg=i 的点 有i+1个边与其相连 (一个在上面) 所以共有 sigma_{1 to i} i(i+1) 个边 (有些重复算等一下讨论) 有一个点是根 所以上式 要-1 对於叶点 有一个边与其相连 所以有 L(K)个点 这样 就确保每个边都计算两次 所以 边数=( (sigma_{1 to i} i(i+1)) -1 + L(K))/2 节点数 这个简单一点 题目已经说了 节点数=L(K) + sigma_{1 to i} i 然後利用 节点数-1=边数 就能解L(K) (当然你要知道sigma的公式) 以上 有钱吗? --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 69.180.5.117 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1619802162.A.78A.html ※ 编辑: RicciCurvatu (69.180.5.117 美国), 05/01/2021 01:14:03