Java 中的十边形数

在本节中，我们将学习十边形数是什么，并创建Java 程序来计算十边形数。十边形数程序经常出现在 Java 编码面试和学术中。

十边形数

十边形数是一个图形数，其递归定义为

因此，

D(1) = D(1 - 1) + 8 * 1 - 7 = D(0) + 8 - 7 = 0 + 8 - 7 = 0 + 1 = 1

D(2) = D(2 - 1) + 8 * 2 - 7 = D(1) + 16 - 7 = 1 + 16 - 7 = 1 + 9 = 10

D(3) = D(3 - 1) + 8 * 3 - 7 = D(2) + 24 - 7 = 10 + 24 - 7 = 10 + 17 = 27

D(4) = D(4 - 1) + 8 * 4 - 7 = D(3) + 32 - 7 = 27 + 32 - 7 = 27 + 25 = 52

D(5) = D(5 - 1) + 8 * 5 - 7 = D(4) + 40 - 7 = 52 + 40 - 7 = 52 + 33 = 85

计算十边形数

计算十边形数有多种方法。在本节中，我们将讨论以下三种方法：

• 使用递归
• 使用动态规划
• 使用数学公式

使用递归

由于我们已经知道了递归公式，因此使用递归很容易计算出十边形数。下面的程序展示了这一点。

文件名： DecagonalNumbers.java

输出

The first 10 Decagonal numbers are: 
1 10 27 52 85 126 175 232 297 370

复杂度分析： 由于计算十边形数的递归从 n 到 0，因此程序的时间复杂度为 O(n)，其中 n 是第 n 个十边形数。由于程序不使用任何额外空间，因此空间复杂度为 O(1)。

上述程序的时间复杂度可以进一步降低，因为我们反复计算相同的子问题。例如，如果我们计算 D(3)，那么递归地，D(3) 会简化为 D(2)，而 D(2) 又会简化为 D(1)。因此，我们看到 D(2) 和 D(1) 被重复计算，这可以避免。以下方法展示了这一点。

使用动态规划

我们可以使用一个辅助数组来存储已计算出的十边形数，并在后续计算中使用它们。观察下面的程序。

文件名： DecagonalNumbers1.java

输出

The first 10 Decagonal numbers are: 
1 10 27 52 85 126 175 232 297 370

复杂度分析： 程序的时间复杂度为 O(1)。由于程序使用了辅助数组，因此空间复杂度为 O(range)，其中 range 是计算十边形数的上限。

如果我们观察递归公式，我们会发现当前的十边形数仅取决于上一个计算出的十边形数，而不取决于之前计算出的所有十边形数。因此，我们可以使用一个变量来存储上一个计算出的十边形数，而不是使用数组。观察下面的程序。

文件名： DecagonalNumbers2.java

输出

The first 10 Decagonal numbers are: 
1 10 27 52 85 126 175 232 297 370

复杂度分析： 程序的时间复杂度为 O(1)。由于程序不使用任何额外空间，因此空间复杂度是常数，即 O(1)。

使用数学公式

计算十边形数的数学公式是：

因此，

D(1) = 1 x ((4 x 1) - 3) = 1 x (4 - 3) = 4 - 3 = 1

D(2) = 2 x ((4 x 2) - 3) = 2 x (8 - 3) = 2 x 5 = 10

D(3) = 3 x ((4 x 3) - 3) = 3 x (12 - 3) = 3 x 9 = 27

D(4) = 4 x ((4 x 4) - 3) = 4 x (16 - 3) = 4 x 13 = 52

D(5) = 5 x ((4 x 5) - 3) = 5 x (20 - 3) = 5 x 17 = 85

实施

观察上面数学公式的实现。

文件名： DecagonalNumbers3.java

输出

The first 10 Decagonal numbers are: 
1 10 27 52 85 126 175 232 297 370

复杂度分析： 程序的时间复杂度为 O(1)。