如何在 java 中生成 Hexanacci 数字？

Question

我正在尝试使用 BigInteger 在 java 中生成 hexanacci 系列。

系列：0、1、1、2、4、8、16、32、63、125、248、492、976、1936、3840、7617、15109、29970、59448、117920、233904、 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368 ...

这是我的代码：

import java.math.BigInteger;

/**
 *
 * @author Tushar
 */
public class Hexanacci {

    static int result = 0;

    public static void main(String[] args) {
        int dest = 33;
        System.out.println(calc(BigInteger.valueOf(dest)));
    }

    public static BigInteger calc(BigInteger n) {
        if (n.compareTo(BigInteger.ZERO) == 0) {

            return BigInteger.ONE;

        } else if (n.compareTo(BigInteger.ONE) == 0) {

            return calc(BigInteger.ZERO);

        } else if (n.compareTo(BigInteger.valueOf(2)) == 0) {


            return calc(BigInteger.valueOf(0))
                    .add(calc(BigInteger.valueOf(1)));


        } else if (n.compareTo(BigInteger.valueOf(3)) == 0) {


            return calc(BigInteger.valueOf(0))
                    .add(calc(BigInteger.valueOf(1)))
                    .add(calc(BigInteger.valueOf(2)));


        } else if (n.compareTo(BigInteger.valueOf(4)) == 0) {


            return calc(BigInteger.valueOf(0))
                    .add(calc(BigInteger.valueOf(1)))
                    .add(calc(BigInteger.valueOf(2)))
                    .add(calc(BigInteger.valueOf(3)));


        } else if (n.compareTo(BigInteger.valueOf(5)) == 0) {


            return calc(BigInteger.ZERO)
                    .add(calc(BigInteger.ONE))
                    .add(calc(BigInteger.valueOf(2)))
                    .add(calc(BigInteger.valueOf(3)))
                    .add(calc(BigInteger.valueOf(4)));


        } else {


            return calc(n.subtract(BigInteger.valueOf(1)))
                    .add(calc(n.subtract(BigInteger.valueOf(2))))
                    .add(calc(n.subtract(BigInteger.valueOf(3))))
                    .add(calc(n.subtract(BigInteger.valueOf(4))))
                    .add(calc(n.subtract(BigInteger.valueOf(5))))
                    .add(calc(n.subtract(BigInteger.valueOf(6))));


        }
    }
}

当 dest 较小时，此程序运行没问题。但如果我增加 dest 的价值，它就会被绞死。例如，当 dist 为 33 时，计算结果需要将近 3 分钟：

3414621024
BUILD SUCCESSFUL (total time: 3 minutes 4 seconds)

谁能告诉我这是正确的方法吗？

Answer 1

如评论中所述，memoization 是改进代码和加快操作速度的简单方法。创建一个 Map<BigInteger, BigInteger> 来存储中间结果。像，

static Map<BigInteger, BigInteger> memo = new HashMap<>();
static {
    int[] initial = { 0, 1, 1, 2, 4, 8 };
    for (int i = 0; i < initial.length; i++) {
        memo.put(BigInteger.valueOf(i), BigInteger.valueOf(initial[i]));
    }
}

public static BigInteger calc(BigInteger n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger orig = n, v = BigInteger.ZERO;
    for (int i = 0; i < 6; i++) {
        n = n.subtract(BigInteger.ONE);
        v = v.add(calc(n));
    }
    memo.put(orig, v);
    return v;
}

其中returns第三十三期几乎是瞬间。

Answer 2

I am trying to generate the hexanacci series

要生成直到 count 的序列，您可以只计算 移动和 ，不需要递归。

// Pseudo code:

int count = 80;
mySeries = vector<BigInteger>;

preallocate mySeries to size 'count' (or 'add' items in the loop)
prefill mySeries with 0, 1, 1, 2, 4, 8, 16, 32

for (int i = 8; i < count; i++) {

                  // avoid multiplication by 2, unless BigInteger supports '<< 1'
    mySeries[i] = mySeries[i-1] + mySeries[i-1] - mySeries[i-7];
}

结果应该是即时的。

如何在 java 中生成 Hexanacci 数字？

How to generate Hexanacci numbers in java?

java

performance

biginteger