Java 中的房屋编号

在本节中，我们将学习Java 中的房屋编号。它是一个由边长为 s+1 的立方体组成的数字。在这个立方体上，我们有一个边长为 s 的方锥体数。下图描绘了一个房屋编号。

通常，房屋编号 Hs 在数学上表示为

实现：迭代

让我们看看如何实现上述数学公式。

文件名： HouseNum.java

输出

The first 10 house numbers are: 
1 9 32 78 155 271 434 652 933 1285

时间复杂度： 上面的程序使用循环来查找每个房屋编号的值。因此，该程序的 time complexity 为 O(n²)，其中 n 是需要计算的总房屋编号数。

实现：递归

也可以通过递归来查找房屋编号的值。请看下面的程序。

文件名： HouseNum1.java

输出

The first 10 house numbers are: 
1 9 32 78 155 271 434 652 933 1285

时间复杂度： 上面的程序通过递归查找每个房屋编号的值。因此，该程序的 time complexity 为 O(n²)，其中 n 是需要计算的总房屋编号数。

优化实现

我们用于计算房屋编号值的上述两种方法的迭代或递归是导致时间复杂度增加的主要原因。因此，我们需要找到一种方法来消除迭代或递归。为此，让我们再次观察数学公式。

之所以出现递归或迭代，是因为我们在第二部分进行了求和。如果我们仔细观察，我们会发现第二部分只是前 s 个自然数的平方之和。因此，

让我们实现上述计算数学公式。

文件名： HouseNume2.java

输出

The first 10 house numbers are: 
1 9 32 78 155 271 434 652 933 1285

时间复杂度： 上面的程序没有使用任何递归或迭代来查找每个房屋编号的值。因此，该程序的 time complexity 为 O(n)，其中 n 是需要计算的总房屋编号数。

数学公式仍然有第一部分 ([s + 1]³) 和第二部分 ([s * ( s + 1) * (2 * s + 1)] / 6)。然而，我们可以解方程 A 来组合所有这些部分。

因此，

H_s = (s + 1)³ + ((s * (s + 1) * (2s + 1)) / 6 ............. (方程 A)

H_s = (s + 1)³ + ((s * (s + 1) * (2s + 1)) / 6

H_s = (s + 1) [(s + 1)² + (s * (2s + 1)) / 6]

H_s = (s + 1) [ s² + 2s + 1 + ((s² + s) * (2s + 1)) / 6]

H_s = (s + 1) [s² + 2s + 1 + (2s² + s) / 6]

H_s = (s + 1) [6s² + 12s + 6 + 2s² + s] / 6

H_s = (s + 1) [8s² + 13s + 6] / 6 = (8s³ + 13s² + 6s + 8s² + 13s + 6) / 6

H_s = (8s³ + 21s² + 19s + 6) / 6 ............. (方程 B)

在方程 B 中，所有项都已合并，该方程也可用于查找房屋编号。以下程序说明了这一点。

文件名： HouseNume3.java

输出

The first 10 house numbers are: 
1 9 32 78 155 271 434 652 933 1285

时间复杂度： 该程序的 time complexity 仍然是 O(n)，因为程序没有使用任何递归或迭代来查找每个房屋编号的值。n 是需要计算的总房屋编号数。