Java 中的中心正方形数

在本节中，我们将学习什么是中心正方形数，并创建 Java 程序 来检查给定的数字是否为中心正方形数。中心正方形数程序经常在 Java 编码面试和学术中出现。

中心正方形数

中心正方形数是 图形数，它们是递归定义的：

因此，

对于 n = 1

Q(1) = Q(1 - 1) + 4 x (1 - 1) => Q(1) = Q(0) + 4 x 0 = 1 + 0 = 1

对于 n = 2

Q(2) = Q(2 - 1) + 4 x (2 - 1) => Q(2) = Q(1) + 4 x 1 = 1 + 4 = 5

对于 n = 3

Q(3) = Q(3 - 1) + 4 x (3 - 1) => Q(3) = Q(2) + 4 x 2 = 5 + 8 = 13

对于 n = 4

Q(4) = Q(4 - 1) + 4 x (4 - 1) => Q(4) = Q(3) + 4 x 3 = 13 + 12 = 25

对于 n = 5

Q(5) = Q(5 - 1) + 4 x (5 - 1) => Q(5) = Q(4) + 4 x 4 = 25 + 16 = 41

递归方法

在这种方法中，我们将编写一个将调用自身（递归）来计算中心正方形数的方法。用于终止递归的基本情况是 Q(1) = 1。观察下面提到的实现。

文件名： CenteredSquareNumber.java

输出

The first 10 Centered Square Number are: 
1 5 13 25 41 61 85 113 145 181

复杂度分析： 程序的时间复杂度为 O(d)，其中 d 是必须找到的中心正方形数的 d^th 位置。程序不消耗任何额外空间。因此，空间复杂度为 O(1)。

方法：使用迭代

上述程序的空间复杂度可以进一步降低。我们将使用一个数组来存储先前计算的中心正方形的结果。因此，无需一遍又一遍地重新计算先前计算的解决方案。观察下面提到的实现。

文件名： CenteredSquareNumber1.java

输出

The first 10 Centered Square Number are: 
1 5 13 25 41 61 85 113 145 181

复杂度分析： 程序的时间复杂度为 O(1)。程序使用数组来存储结果。因此，程序空间复杂度为 O(n)，其中 n 是必须计算的中心正方形数的总数。

我们仍然可以在空间复杂度方面进行优化。如果我们观察上述递归公式，我们会发现第 n 个中心正方形数仅依赖于第 (n - 1) 个中心正方形数。因此，无需存储所有先前计算的中心正方形数。只需存储最后一个计算的中心正方形数即可完成工作。以下程序显示了相同的内容。

文件名： CenteredSquareNumber2.java

输出

The first 10 Centered Square Number are: 
1 5 13 25 41 61 85 113 145 181

复杂度分析： 程序的时间复杂度为 O(1)。程序不使用数组来存储结果。因此，程序空间复杂度也为 O(1)。

方法：使用数学公式

计算中心正方形数的数学公式是

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

因此，

对于 n = 1

Q(1) = 1² + (1 - 1)² => Q(1) = 1 + 0² = 1 + 0 = 1

对于 n = 2

Q(2) = 2² + (2 - 1)² => Q(2) = 4 + 1² = 4 + 1 = 5

对于 n = 3

Q(3) = 3² + (3 - 1)² => Q(3) = 9 + 2² = 9 + 4 = 13

对于 n = 4

Q(4) = 4² + (4 - 1)² => Q(4) = 16 + 3² = 16 + 9 = 25

对于 n = 5

Q(5) = 5² + (5 - 1)² => Q(5) = 25 + 4² = 25 + 16 = 41

上面提到的数学公式的实现非常直接。

文件名： CenteredSquareNumber3.java

输出

The first 10 Centered Square Number are: 
1 5 13 25 41 61 85 113 145 181

复杂度分析： 该程序的时间复杂度和空间复杂度与前一个程序相同。

检查中心正方形数

到目前为止，我们一直在计算中心正方形数。现在，我们将看看如何验证给定的数字是否为中心正方形数。

方法

该方法是借助三角形数来计算中心正方形数，直到输入数字或大于输入数字（在本例中为 inputNum）。我们可以通过三角形数来做到这一点。观察以下步骤。

步骤 1：首先，我们需要计算三角形数。

步骤 2：然后，将计算出的三角形数乘以 4。

步骤 3：之后，将结果加 1。我们得到的数字是中心正方形数。

步骤 4：如果上一步中找到的计算数字与 inputNum 匹配，则 inputNum 是中心正方形数。否则，计算下一个更大的三角形数并从步骤 2 重复。如果计算出的中心数大于 inputNum，则意味着 inputNum 不是中心正方形数。

注意：三角形数 T(n) = (n x (n + 1)) / 2，其中 n >= 1

文件名： CenteredSquareNumber4.java

输出

4 is not a centered square number.
5 is a centered square number.
8 is not a centered square number.
13 is a centered square number.
15 is not a centered square number.
25 is a centered square number.
40 is not a centered square number.
41 is a centered square number.

复杂度分析：该程序的时间复杂度为 O(N)，其中 N 是必须验证的中心正方形数的值。程序空间复杂度是常数，即 O(1)。