Java 中的 Iccanobif 数

Iccanobif 数与斐波那契数列相似。与斐波那契数列类似，Iccanobif 数列的当前数字取决于前两个 Iccanobif 数字。然而，主要的区别在于，与斐波那契数列不同的是，必须先反转最后两个数字，然后将它们相加才能得到当前的 Iccanobif 数字。“Iccanobif”这个词是“Fibonacci”这个词的反转。在 Iccanobif 数列中，前两个数字也定义为 0 和 1。

因此，

I(0) = 0; & I(1) = 1; I(2) = I(1) + I(0) = 1 + 0 = 1; I(3) = I(2) + I(1) = 1 + 1 = 2

I(4) = I(3) + I(2) = 2 + 1 = 3; I(5) = I(4) + I(3) = 3 + 2 = 5; I(6) = I(5) + I(4) = 5 + 3 = 8;

I(7) = I(6) + I(5) = 8 + 5 = 13;

到目前为止，Iccanobif 数列与斐波那契数列完全相同。从这一点开始，我们将看到与斐波那契数列不同的数字。

I(8) = rev(I(7)) + I(6) = rev(13) + 8 = 31 + 8 = 39。

I(9) = rev(I(8)) + rev(I(7)) = rev(39) + rev(13) = 93 + 31 = 124

rev() 方法反转数字的各位。我们直到 I(7) 都没有进行数字反转。这是因为直到 I(7)，所有数字都是个位数，反转个位数会得到相同的数字。例如 rev(3) = 3。由于数字反转对直到 I(7) 的数字没有影响，因此这些数字与斐波那契数列相同。

因此，Iccanobif 数列为

0, 1, 1, 2, 3, 5, 8, 13, 39, 124, ...

从 39 开始，Iccanobif 数列与斐波那契数列不同。这就是为什么我们强调数字 39。

让我们看看实现 Iccanobif 数列的不同方法。

递归方法

让我们看看如何使用递归来查找 Iccanobif 数列。

文件名： IccanoBifNumbers.java

输出

The first 10 Iccanobif Numbers are: 
0 1 1 2 3 5 8 13 39 124

时间复杂度：在上面的程序中，每次递归调用都会导致另外两次递归调用。因此，计算每个 Iccanobif 数字的时间复杂度是指数级的，即 (2ⁿ)，其中 n 代表 findIccanobifNum() 方法的参数 num。

上面的程序花费了大量时间来查找 Iccanobif 数列。因此，我们需要进一步优化它以降低时间复杂度。以下方法执行相同的操作。

迭代方法

上面的程序花费了大量时间来查找 Iccanobif 数列。因此，我们需要进一步优化它以降低时间复杂度。

文件名： IccanobifNumbers1.java

输出

The first 10 Iccanobif Numbers are: 
0 1 1 2 3 5 8 13 39 124

复杂度分析：在上面的程序中，我们在 O(n) 时间内计算了 Iccanobif 数列。但是，我们还使用了一个额外的数组来存储结果，这导致空间复杂度为 O(n)，其中 n 是需要计算的 Iccanobif 数的总数。

在空间复杂度方面，我们可以做得更好。仔细观察，我们会发现我们只需要两个变量：一个用于存储倒数第二个 Iccanobif 数字，另一个用于存储最后一个 Iccanobif 数字。因此，我们避免了使用数组。请看下面的程序。

文件名： IccanobifNumbers2.java

输出

The first 10 Iccanobif Numbers are: 
0 1 1 2 3 5 8 13 39 124

复杂度分析：在这里，我们将空间复杂度从 O(n) 降低到 O(1)，时间复杂度仍然相同。

注意：在进行复杂度分析时，我们假设反转数字的位数需要 O(1)，即常数时间。要反转数字的位数，可以使用 StringBuilder 类的 reverse() 方法。但是，在此之前，需要将数字转换为字符串。