一个数学函数可以获取特定类型 k 元的叶子数量？

Question

我正在尝试找出一个函数 f(x) 来计算 k 叉树中的叶子数量。例如，假设我们创建了一棵树，从根 4 开始，有 3 个子节点，每个子节点分别为 -1、-2、-3。我们的叶子只能是 0 值，而不是空值。我花了一天的时间试图找出一个函数，但似乎我所做的一切都没有朝着正确的方向发展。

例如：

              4
         /    |     \
        3     2      1
     /  |\   /|     /  
    2   1 0 1 0    0  
   /|  /   /
  1 0 0   0
 /
0

7 片叶子。

任何帮助将非常感激！谢谢！

为了澄清，我需要一个数学方程，如果我递归地遍历树，它可以得出与代码相同的答案。

更多示例： {4,7}{5,13}{6,24}{7,44}{8,81}{9,149}{10,274}{11,504}{12,927}{13,1705}{14,3136}{15, 5768}{16,10609}{17,19513}{18,35890}{19,66012}{20,121415}

 public int numleaves(TreeNode node) {
    if (node == null)
        return 0; 
    else if (node.getLeft() == null && node.getMiddle() == null && node.getRight() == null)
        return 1; 
    else
        return numleaves(node.getLeft()) + numleaves(node.getMiddle()) + numleaves(node.getRight());
}

Answer 1

我无法回答你的问题，但它有一个解决方案。我只能概述孩子数量

等于

的情况。案例

k=3

导致三次多项式具有两个复数解和一个实数解，我这里缺乏以非数值方式导出它们的工具。

但是让我们看一下案例

k=2

。有趣的是，除了边界条件不同之外，这个问题与斐波那契数非常密切相关。

写出递归公式很容易：

a(n) = a(n-1) + a(n-2)

具有边界条件

a(1)=1

和

a(0)=1

。其特征多项式为

x^2 = x + 1

使用解决方案

x1 = 1/2 + sqrt(5)/2

和

x2 = 1/2 - sqrt(5)/2

。这意味着

a(n) = u*x1^n + v*x2^n

对于某些

和

是我们正在寻找的序列的显式公式。代入边界条件我们得到

u = (sqrt(5)+1)/(2*sqrt(5))
v = (sqrt(5)-1)/(2*sqrt(5))

即

a(n) = (sqrt(5)+1)/(2*sqrt(5))*(1/2 + sqrt(5)/2)^n + (sqrt(5)-1)/(2*sqrt(5))*(1/2 - sqrt(5)/2)^n

对于

k=2

。

Answer 2

您的代码似乎正在计算一个 Tribonacci 序列，起始值为

、

和

。这是来自整数序列在线百科全书的序列 A000073，从该序列的第三个条目而不是第一个条目开始。百科全书页面的评论部分给出了一个明确的公式：由于这是一个具有3次特征多项式的线性递推关系，因此根据该多项式的根存在一个封闭形式的解。下面是一段简短的 Python 2 代码，基于给定的公式，可生成前几个值。（请参阅下面的编辑以进行简化。）

from math import sqrt

c = (1 + (19 - 3 * sqrt(33))**(1/3.) + (19 + 3 * sqrt(33))**(1/3.)) / 3.
m = (1 - c) / 2
p = sqrt(((3*c - 5)*(c+1)/4))
j = 1/((c-m)**2 + p**2)
b = (c - m) / (2 * p*((c - m)**2 + p**2))
k = complex(-j / 2, b)
r1 = complex(m, p)

def f(n):
    return int(round(j*c**(n+2) + (2*k*r1**(n+2)).real))

for n in range(0, 21):
    print n, f(n)

输出：

编辑：上面的代码不必要地复杂。通过

round

运算，可以省略

f(n)

中的第二项（随着

的增加，它收敛到零），并且可以简化第一项的公式。这是一些生成相同输出的更简单的代码。

s = (19 + 297**0.5)**(1/3.)
c = (1 + s + 4/s)/3
j = 3 - (2 + 1/c)/c
for n in range(0, 32):
    print n, int(round(c**n / j))

Answer 3

我忍不住，但我在里面看到了二项式树。 http://en.wikipedia.org/wiki/Binomial_heap

我认为好的近似可能是帕斯卡三角形的第 k 行之和，其中 k 代表根节点的编号。

Answer 4

这样是不是更容易理解了：

我们将 tribonacci 序列的起始值设置到一个名为 result 的列表中。然后我们将这些值放入 3 个变量中。我们根据tribonacci公式改变变量内容（新a是a+b+c，新b是旧a，新c是旧b）。然后我们计算出我们想要的任何 tribonacci 数并将每个结果存储到我们的结果列表中。最后，我们读出索引列表。

result=[1,1,2]
a,b,c=result[-1],result[-2],result[-3]
for i in range(40):
    a,b,c=a+b+c,a,b
    result.append(a)
for e,f in enumerate(result):
    print e,f

Answer 5

让 s 表示比例 = .182803532968295464385265406184520048。并设 tribonacci 常数 tc = (1 + (19-3sqrt(33))1⸍3 + (19+3sqrt(33))13)/3 = 1.839286755214161132551852564653... 然后 trib(n) = round(s*tcⁿ) 给出 n 从 0 到 146 的正确整数。

如果您只能将 s 表示为一半的数字，那么它只能表示 n 的大约一半，依此类推。

我非常有兴趣看到 s 的封闭式公式，适用于任意精度计算器中的所有 n。我在上面使用了 Unix 的 bc，并获得了 s 作为 trib(91)/tc^91，其中 91 是 146 除以黄金比例（我不知道为什么，它就是有效！）。

正如其他人用类似语言指出的那样，bc 中的 trib(n) 可以定义为定义 trib(n) {z=0; y=0； x=1;对于 (i=2; i < n; i++) {zz = z; z = y; y = x; x = y+z+zz;}; return x*(n>1)} 如果没有 *(n>1)，trib(0) 将是 1 而不是 0。

我不知道如何计算 bc 中的“round”，我只是目测它。

一个数学函数可以获取特定类型 k 元的叶子数量？

问题描述投票：0回答：5

5个回答

最新问题

一个数学函数可以获取特定类型 k 元的叶子数量？

问题描述 投票：0回答：5

5个回答

最新问题

问题描述投票：0回答：5