Java 中的 Jacobsthal 数

2024年9月10日 | 阅读 6 分钟

在本节中，我们将学习如何在 Java 中查找 Jacobsthal 数。数学上，Jacobsthal 数定义为

J_a= (2^a - (-1)^a) / 3，其中 a >= 0

因此，

对于 a = 0，

J₀= (2⁰- (-1)⁰) / 3 = (1 - (1)) / 3 = 0 / 3 = 0

对于 a = 1，

J₁= (2¹- (-1)¹) / 3 = (2 - (-1)) / 3 = 3 / 3 = 1

对于 a = 2，

J₂= (2²- (-1)²) / 3 = (4 - (1)) / 3 = 3 / 3 = 1

对于 a = 3，

J₃= (2³- (-1)³) / 3 = (8 - (-1)) / 3 = 9 / 3 = 3

对于 a = 4，

J₄= (2⁴- (-1)⁴) / 3 = (16 - (1)) / 3 = 15 / 3 = 5

对于 a = 5，

J₄= (2⁵- (-1)⁵) / 3 = (32 - (-1)) / 3 = 33 / 3 = 11

实施

让我们看看如何实现上述数学公式。请看下面的 Java 程序。

文件名： JacobsthalNumberExample1.java

public class JacobsthalNumberExample1
{
// a method that finds the value of b^e
int pow(int b, int e)
{
// anything whose power is 0 is 1
if(e == 0)
{
return 1;
}

// it will store the result
int ans = 1;
while(true)
{

if(e % 2 == 1)
{
e = e - 1;
ans = ans * b;
if(e == 0)
{
return ans;
}
}

b = b * b;
e = e / 2;
}

}
public int findJacobsthal(int a)
{
// finding (2)^a
int x = pow(2, a);

// finding (-1)^a
int y = pow(-1, a);

// finding the jacobsthal number
int no = (x - y) / 3;

return no;
}

// main method
public static void main(String argvs[])
{
// creating an object of the class JacobsthalNumberExample1
JacobsthalNumberExample1 obj = new JacobsthalNumberExample1();

System.out.println("The first 20 Jacobsthal numbers are: ");

for(int i = 0; i < 20; i++)
{
// invoking the method findJacobsthal()
int num = obj.findJacobsthal(i);
    
System.out.print(num + " ");
}
}
}

输出

The first 20 Jacobsthal numbers are: 
0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

使用递归

也可以使用递归来查找 jacbosthal 数。但是，要使用递归查找 jacbsthal 数，我们必须知道它的递归公式。

J₀ = 0 and J₁ = 1

J_a = J_{a - 1} + 2 * J_{a - 2}，对于 a >= 2

因此，

对于 a = 2

J₂= J_{2 - 1}+ 2 * J_{2 - 2}= J₁+ 2 * J₀= 1 + 2 * 0 = 1 + 0 = 1

对于 a = 3，

J₃= J_{3 - 1}+ 2 * J_{3 - 2}= J₂+ 2 * J₁= 1 + 2 * 1 = 1 + 2 = 3

对于 a = 4，

J₄= J_{4 - 1}+ 2 * J_{4 - 2}= J₃+ 2 * J₂= 3 + 2 * 1 = 3 + 2 = 5

对于 a = 5，

J₅= J_{5 - 1}+ 2 * J_{5 - 2}= J₄+ 2 * J₃= 5 + 2 * 3 = 5 + 6 = 11

实施

让我们看看上述递归公式的实现。

文件名： JacobsthalNumberExample2.java

// A Java program that shows how one can use
// recursion with memoization to find the Jacobsthal numbers
public class JacobsthalNumberExample2
{
// a[] is used for the memoization in the recursive calls
// it is done to avoid repeatitive recursive calls 
// For example, J3 = J2 + 2 * J1
// Also, J2 = J1 * 2 * J0
// We see that in J3 and in J2 we have to find the value of J1
// if we will not use array a[], then we have to compute the 
// value of J1 twice (one for J3 and another for J2), which in turn will consume more 
// time.

// initializing the array of size 20 with the value -1
public static int a[] = 
                 { 
                    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
                    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1    
                 };
// method that finds the ith Jacobsthal number
public int findJacobsthal(int i)
{
// if the value of a[i] is not equal to -1, then 
// it means the Jacobsthal number for the ith position
// has already been computed. So, all we have to do 
// is to reuse it
if(a[i] != -1)
{
return a[i];
}
if(i == 0)
{
a[i] = 0;
// handling base case
return 0;
}
else if(i == 1)
{
a[i] = 1;
// handling base case
return 1;
}
// recursively finding the ith jacobsthal number
// Also, storing the value of the jacobsthal number 
// sitting at the ith position. So that it is reused later.
a[i] = findJacobsthal(i - 1) + 2 * findJacobsthal(i - 2);
return a[i];
}
// main method
public static void main(String argvs[])
{
// creating an object of the class JacobsthalNumberExample2
JacobsthalNumberExample2 obj = new JacobsthalNumberExample2();
System.out.println("The first 20 Jacobsthal numbers are: ");
for(int i = 0; i < 20; i++)
{
// invoking the method findJacobsthal()
int num = obj.findJacobsthal(i); 
System.out.print(num + " ");
}
}
}

输出

The first 20 Jacobsthal numbers are: 
0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

迭代实现

除了递归，也可以使用循环来查找 jacbsthal 数。下面的程序对此进行了说明。

实施

让我们以迭代的方式看看上述递归公式的实现。

文件名： JacobsthalNumberExample3.java

public class JacobsthalNumberExample3
{

// main method
public static void main(String argvs[])
{
// creating an object of the class JacobsthalNumberExample3
JacobsthalNumberExample3 obj = new JacobsthalNumberExample3();

// for storing the first 20 Jacobsthal numbers
int a[] = new int[20];

// base cases
a[0] = 0;
a[1] = 1;

// computing the remaining Jacobsthal number
for(int i = 2; i < 20; i++)
{
a[i] = a[i - 1] + 2 * a[i - 2];
}

System.out.println("The first 20 Jacobsthal numbers are: ");

// displaying the jacobsthal numbers
for(int i = 0; i < 20; i++)
{
System.out.print(a[i] + " ");
}
}
}

输出

The first 20 Jacobsthal numbers are: 
0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

上述程序使用一个数组来计算 jacbsthal 数，其大小取决于我们想要查找的 jacbsthal 数的总数。因此，要计算多达 10 个 jacbsthal 数，我们将使用大小为 10 的数组，要计算多达 20 个 jacbsthal 数，我们将使用大小为 20 的数组。如果我们仔细观察，会发现当前的 jacbsthal 数取决于最后两个 jacbsthal 数。在下面的递归公式中，

J_a= J_{a - 1}+ 2 * J_{a - 2}

J_{a - 1}是最后一个 jacbsthal 数，J_{a - 2}是倒数第二个 jacbsthal 数。

因此，我们可以不使用数组，而只使用两个变量来查找 jacbsthal 数。下面的程序说明了这一点。

文件名： JacobsthalNumberExample4.java

public class JacobsthalNumberExample4
{
// main method
public static void main(String argvs[])
{
// creating an object of the class JacobsthalNumberExample4
JacobsthalNumberExample4 obj = new JacobsthalNumberExample4();
// the first two jacobsthal numbers are 0 & 1
int a = 0;
int b = 1;
System.out.println("The first 20 Jacobsthal numbers are: ");
// computing the remaining Jacobsthal number 
//  and along side printing them 
for(int i = 0; i < 20; i++)
{
// base case
if(i == 0)
{
System.out.print(a + " ");
}
else if(i == 1)
{
// base case
System.out.print(b + " ");    
}
else
{
// computing the current jacobsthal number
// using the recurrence formula
int c = b + 2 * a;
System.out.print(c + " ");
// updating the last and the second last 
// Jacobsthal number
a = b;
b = c;
}
}
}
}

输出

The first 20 Jacobsthal numbers are: 
0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

注意：上述方法是查找 Jacobsthal 数的最佳方法，因为程序的空间复杂度为 O(1)，而且与其它方法相比，它耗时最少。

下一主题Java BLOB

Java 中的 Jacobsthal 数

实施

使用递归

实施

迭代实现

实施

注意：上述方法是查找 Jacobsthal 数的最佳方法，因为程序的空间复杂度为 O(1)，而且与其它方法相比，它耗时最少。

联系信息

关注我们

教程

面试题

在线编译器

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 中的 Jacobsthal 数

实施

使用递归

实施

迭代实现

实施

注意：上述方法是查找 Jacobsthal 数的最佳方法，因为程序的空间复杂度为 O(1)，而且与其它方法相比，它耗时最少。

相关帖子

Java List Lambda 排序

Composition in Java

Java 中的普遍肤浅

Java 中的嵌套 ArrayList

Java 中多线程与多进程的区别

Java 程序求最大乘积子数组

Java IdentityHashMap Class

Difference Bitwise AND (&) and Logical AND (&&) in Java

Delegation Event Model in Java

java.io package

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器