Java 中的星形数

2025年03月17日 | 阅读 9 分钟

在本节中，我们将学习 Java 中的星形数。星形数类似于中国跳棋棋盘。星形数是一个六角星。这里，六角星表示一个六角尖的星。请看下图。

在数学上，该数表示为

S_n = 6 x n x (n - 1) + 1，其中 n >= 1

因此，

S₁ = 6 x 1 x (1 - 1) + 1 = 6 x 1 x 0 + 1 = 0 + 1 = 1

S₂ = 6 x 2 x (2 - 1) + 1 = 6 x 2 x 1 + 1 = 12 + 1 = 13

S₃ = 6 x 3 x (3 - 1) + 1 = 6 x 3 x 2 + 1 = 36 + 1 = 37

S₄ = 6 x 4 x (4 - 1) + 1 = 6 x 4 x 3 + 1 = 72 + 1 = 73

S₅ = 6 x 5 x (5 - 1) + 1 = 6 x 5 x 4 + 1 = 120 + 1 = 121

S₆ = 6 x 6 x (6 - 1) + 1 = 6 x 6 x 5 + 1 = 180 + 1 = 181

实施

在 Java 中有三种方法可以编写星形数的代码。一种是使用上面定义的公式，另一种是递归，最后一种是迭代。让我们从基于公式的方法开始。

基于公式的方法

文件名：StarNumbers.java

public class StarNumbers
{

// a method for computing the ith star number
public int findStarNumbers(int i)
{
    // computing star number using the mathematical formula 
    // defined above
    int starNum = 6 * i * ( i - 1) + 1;
    
    return starNum;
}


// main method
public static void main(String argvs[])
{
// total number of star numbers that have to be computed
int num = 10;

// creating an object of the class StarNumbers
StarNumbers obj = new StarNumbers();

System.out.println("The first 10 star numbers are: ");
for(int i = 1; i <= num; i++)
{
// invoking the method findStarNumbers() 
// and storing the result
int ans = obj.findStarNumbers(i);
System.out.print(ans + " ");
}


}
}

输出

The first 10 star numbers are: 
1 13 37 73 121 181 253 337 433 541

时间复杂度：上述程序的时间复杂度为 O(n)，其中 n 是要找到的星形数的总数。

空间复杂度：上述程序没有使用任何额外空间；因此，上述程序的空间复杂度为 O(1)。

递归方法

使用递归也可以计算星形数。但是，在实现递归之前，必须了解计算星形数的递归公式。递归公式定义为

S_n = S_{n - 1} + 12 x (n - 1)，其中 n >= 2 且 S₁ = 1

因此，

S₂ = S_{2 - 1} + 12 x (2 - 1) = S₁ + 12 x 1 = 1 + 12 = 13

S₃ = S_{3 - 1} + 12 x (3 - 1) = S₂ + 12 x 2 = 13 + 24 = 37

S₄ = S_{4 - 1} + 12 x (4 - 1) = S₃ + 12 x 3 = 37 + 36 = 73

S₅ = S_{5 - 1} + 12 x (5 - 1) = S₄ + 12 x 4 = 73 + 48 = 121

S₆ = S_{6 - 1} + 12 x (6 - 1) = S₅ + 12 x 5 = 121 + 60 = 181

请看下面的 Java 代码。

文件名：StarNumbers1.java

public class StarNumbers1
{

// a method for computing the ith star number recursively
public int findStarNumbers(int i)
{
    // handling the base case S1 = 1
    if(i == 1)
    {
        
        return 1;
    }
    
    else
    {
        // recursively finding the ith star number
        return (findStarNumbers(i - 1) + 12 * (i - 1));    
    }
}


// main method
public static void main(String argvs[])
{
// total number of star numbers that have to be computed
int num = 10;

// creating an object of the class StarNumbers1
StarNumbers1 obj = new StarNumbers1();

System.out.println("The first 10 star numbers are: ");
for(int i = 1; i <= num; i++)
{
// invoking the method findStarNumbers() 
// and storing the result
int ans = obj.findStarNumbers(i);
System.out.print(ans + " ");
}
}
}

输出

The first 10 star numbers are: 
1 13 37 73 121 181 253 337 433 541

时间复杂度：为了找到第 n 个星形数，必须递归地从 n 到 1。因此，上述程序的时间复杂度为 O(n²)，其中 n 是要计算的星形数的总数。

空间复杂度：如果我们忽略由于递归引起的隐式内存消耗，则上述程序的空间复杂度为 O(1)。

为了优化上述程序，必须使用记忆化技术。以下程序显示了这一点。

文件名：StarNumbers2.java

public class StarNumbers2
{

// a method for computing the ith star number recursively
public int findStarNumbers(int i, int arr[])
{
    // handling the base case S1 = 1
    if(i == 1)
    {
        
        arr[i] = 1;
        return 1;
    }
    
    // memoization technique is used here
    // For example: for computing the 3rd star number
    // earlier, one has to go recursively from 3 to 1.
    // Therefore, it leads to repetition of computing the 2nd star number
    // In this case, we have already stored the value of 2nd star number
    // in the element arr[2]. All we have to do is to return it
    if(arr[i] != 0)
    {
        return arr[i];
    }
    
    else
    {
        // recursively finding the ith star number
        arr[i] = (findStarNumbers(i - 1, arr) + 12 * (i - 1));  
        return arr[i];
    }
}


// main method
public static void main(String argvs[])
{
// total number of star numbers that have to be computed
int num = 10;

// creating an object of the class StarNumbers2
StarNumbers2 obj = new StarNumbers2();

// for storing the ith star number
int []arr = new int[num];

System.out.println("The first 10 star numbers are: ");
for(int i = 1; i <= num; i++)
{
// invoking the method findStarNumbers() 
// and storing the result
int ans = obj.findStarNumbers(i, arr);
System.out.print(ans + " ");
}


}
}

输出

The first 10 star numbers are: 
1 13 37 73 121 181 253 337 433 541

时间复杂度：由于记忆化技术，上述程序的时间复杂度为 O(n)，其中 n 是要计算的星形数的总数。

空间复杂度：上述程序的空间复杂度为 O(n)，其中 n 是要计算的星形数的总数。

迭代方法

使用循环也可以轻松计算星形数的值。以下程序显示了这一点。

文件名：StarNumbers3.java

public class StarNumbers3
{

// a method for computing the ith star number iteratively
public int findStarNumbers(int i)
{
    // an integer array for storing the star numbers
    int []arr = new int[i + 1];
    
    for(int j = 1; j <= i; j++)
    {
        // handling the base case S1 = 1
        if(j == 1)
        {
            arr[j] = 1;
        }
        
        // else part handles the other cases
        else
        {
            arr[j] = arr[j - 1] + 12 * (j - 1);
        }
    }
    
    return arr[i];
}


// main method
public static void main(String argvs[])
{
// total number of star numbers that have to be computed
int num = 10;

// creating an object of the class StarNumbers3
StarNumbers3 obj = new StarNumbers3();

System.out.println("The first " + num + " star numbers are: ");
for(int i = 1; i <= num; i++)
{
// invoking the method findStarNumbers() 
// and storing the result
int ans = obj.findStarNumbers(i);
System.out.print(ans + " ");
}
}
}

输出

The first 10 star numbers are: 
1 13 37 73 121 181 253 337 433 541

时间复杂度：由于在计算每个星形数时使用了 for 循环，因此上述程序的时间复杂度为 O(n²)，其中 n 是要找到的星形数的总数。

空间复杂度：上述程序的空间复杂度为 O(n)，其中 n 是要计算的星形数的总数。

我们可以优化上述代码以降低时间复杂度。请看以下程序。

文件名：StarNumbers4.java

public class StarNumbers4
{

// main method
public static void main(String argvs[])
{
// total number of star numbers that have to be computed
int num = 10;


// an integer array for storing the star numbers
int []arr = new int[num + 1];


System.out.println("The first " + num + " star numbers are: ");
for(int i = 1; i <= num; i++)
{
// handling the base case S1 = 1
if(i == 1)
{
arr[i] = 1;    
}

// handling the other cases
else
{
arr[i] = arr[i - 1] + 12 * (i - 1);
}
System.out.print(arr[i] + " ");
}


}
}

输出

The first 10 star numbers are: 
1 13 37 73 121 181 253 337 433 541

时间复杂度：由于只有一个循环用于计算星形数；因此，上述程序的时间复杂度为 O(n)，其中 n 是要找到的星形数的总数。

空间复杂度：上述程序的空间复杂度为 O(n)，其中 n 是要计算的星形数的总数。

我们仍然可以做一些优化以减少程序的空间复杂度。如果我们观察递归公式，我们会发现第 n 个星形数依赖于第 (n - 1) 个星形数，而第 (n - 1) 个星形数依赖于第 (n - 2) 个星形数，依此类推。这意味着当前的星形数依赖于前一个星形数。因此，我们不需要数组来存储星形数。我们所要做的就是将前一个星形数存储在一个变量中以计算当前星形数。以下程序显示了这一点。

文件名：StarNumbers5.java

public class StarNumbers5
{

// main method
public static void main(String argvs[])
{
// total number of star numbers that have to be computed
int num = 10;

// for containing the last computed star number
int prv =0;

// for storing the current star number
int curr = 0;

System.out.println("The first " + num + " star numbers are: ");
for(int i = 1; i <= num; i++)
{
// handling the base case S1 = 1
if(i == 1)
{
prv = 1;
curr = 1;
}

// handling the other cases
else
{
// computing the current star number using the previously
// computed star number
curr = prv + 12 * (i - 1);
prv = curr;
}
System.out.print(curr + " ");
}


}
}

输出

The first 10 star numbers are: 
1 13 37 73 121 181 253 337 433 541

时间复杂度：由于只有一个循环用于计算星形数；因此，上述程序的时间复杂度为 O(n)，其中 n 是要找到的星形数的总数。

空间复杂度：由于我们只使用两个变量来计算星形数；因此，上述程序的空间复杂度为 O(1)。

与其他数字的关系

有许多星形数也是三角形数。例如 1、253、49141 等等，都是星形数和三角形数。
有许多星形数也是平方数。例如 1 = 1²、121 = 11²、11881 = 109² 等等，都是星形数和平方数。
星形素数是指既是素数又是星形数的数字。例如：13、37、73 等等，都是星形数和素数。

下一个主题Java 中的 3N+1 问题

← 上一个下一个 →

Java 中的星形数

实施

基于公式的方法

递归方法

迭代方法

与其他数字的关系

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的星形数

实施

基于公式的方法

递归方法

迭代方法

与其他数字的关系

相关帖子

Bus Reservation System Project in Java

Java 中的 DoubleBuffer compact() 方法及示例

Java 和 Core Java 的区别

Java 的 CI/CD 工具

Java Spring Pros & Cons

Java 电费账单程序

CollationElementIterator getOffset() Method in Java with Examples

How to Split a String in Java with Delimiter

Java 中的连续素数和程序

How to Read Character in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器