Java 中的 Hogben 数

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

Hogben 数字

Hogben 数是递归定义的数字，如下所示：

H(n) = H(n - 1) + 2 * (n - 1)，其中 n >= 1 且 H(0) = 1。

因此，

H(1) = H(1 - 1) + 2 * (1 - 1) = H(0) + 2 * 0 = 1 + 0 = 1

H(2) = H(2 - 1) + 2 * (2 - 1) = H(1) + 2 * 1 = 1 + 2 = 3

H(3) = H(3 - 1) + 2 * (3 - 1) = H(2) + 2 * 2 = 3 + 4 = 7

H(4) = H(4 - 1) + 2 * (4 - 1) = H(3) + 2 * 3 = 7 + 6 = 13

H(5) = H(5 - 1) + 2 * (5 - 1) = H(4) + 2 * 4 = 13 + 8 = 21

让我们看看计算 Hogben 数的不同方法。

方法：递归

让我们看看用于计算前 10 个 Hogben 数的递归方法。

文件名： HogbenNum.java

输出

The first 10 Hogben numbers are:
1 3 7 13 21 31 43 57 73 91

复杂度分析：程序的时间复杂度为 O(n)，其中 n 是第 n 个数字。程序空间复杂度为常数，即 O(1)。

方法：迭代

让我们看看用于计算前 10 个 Hogben 数的迭代方法。

文件名： HogbenNum1.java

输出

The first 10 Hogben numbers are:
1 3 7 13 21 31 43 57 73 91

复杂度分析：程序的时间复杂度为 O(1)。程序空间复杂度为常数，即 O(n)，其中 n 是要计算的 Hogben 数的总数。

当前的 Hogben 数仅取决于最后一个计算出的 Hogben 数的值。因此，我们可以使用一个变量来计算 Hogben 数，而不是使用数组。请看下面的程序。

文件名： HogbenNum2.java

输出

The first 10 Hogben numbers are:
1 3 7 13 21 31 43 57 73 91

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

方法：使用数学公式

计算 Hogben 数的数学公式是：

H(n) = n² - n + 1，其中 n >= 1

因此，

H(1) = 1² - 1 + 1 = 1 - 1 + 1 = 1

H(2) = 2² - 2 + 1 = 4 - 2 + 1 = 3

H(3) = 3² - 3 + 1 = 9 - 3 + 1 = 7

H(4) = 4²- 4 + 1 = 16 - 4 + 1 = 13

H(5) = 5² - 5 + 1 = 25 - 5 + 1 = 21

实施

下面的程序使用了上述数学公式。

文件名： HogbenNum3.java

输出

The first 10 Hogben numbers are:
1 3 7 13 21 31 43 57 73 91

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