使用 Java 通过递归来减少 BigIntegers。该方法完全减少数字，然后由于未知原因循环到“向上”的数字-解网

问：

我的任务是编写一个使用递归减少 BigInteger 的方法。如果数字是偶数，则将其分成两半，然后重复该过程，如果数字为奇数，则将其乘以 3，再加 1，然后重复该过程，同时跟踪发生这种情况的次数。

递归一直持续到数字达到 1，然后我返回此过程发生的次数。

我认为我的方法应该可以正常工作。他们没有。他们将 BigInteger 减小到 1，然后它开始向上循环到一个随机数。我不明白为什么。任何帮助将不胜感激。

编辑：我所说的“向上循环”是什么意思：在大 int 减少到 1 后，方法继续“循环”，每次循环时，数字都会增加，计数器也会随着方法循环而减少。该方法中没有任何内容可以解释这一点，所以我不知道它为什么要这样做。这个解释并没有真正帮助，但我把SystemPrintLn放在任何地方，看到它做到了。

public int Problem9(BigInteger value) {
    BigInteger zero = BigInteger.valueOf(0);
    BigInteger one = BigInteger.valueOf(1);
    BigInteger two = BigInteger.valueOf(2);
    BigInteger three = BigInteger.valueOf(3);

    int count = reduceBigInt(value, zero, one, two, three, 1);
    
    return count;
}
public int reduceBigInt(BigInteger num, BigInteger zero,
        BigInteger one, BigInteger two, BigInteger three, int i) {
    
    if (num.equals(one))
        return i;
    else if ((num.remainder(two)) == zero)
        reduceBigInt((num.divide(two)), zero, one, two, three, i++);
    else
        reduceBigInt((num.multiply(three).add(one)), zero, one, two, three, i++);
    return i;
}

Java 递归方法 Collatz

该参数将传递（before increment）的原始值，这意味着每个递归调用都将收到相同的本地值，即 1。当递归调用返回时，下一个语句将执行，当该时间已递增一次时（请记住它是一个局部变量），因此将始终返回 2。i++iireturn iireturn
尽管递归调用返回一个值，但进行递归调用的调用方会忽略此值。
== zero不是比较 BigIntegers 的方法。在这种特殊情况下，您可以改用该方法。testBit
当您开始时等于 1，您的函数永远不会返回 0，但当输入为 1 时，响应应为 0。i
遗憾的是，您必须一遍又一遍地传递、和作为参数，消耗堆栈空间。相反，将它们定义为字段。您甚至可以摆脱所有这些：zeroonetwothree
- 而不是您可以使用 as 只有 1 的位长度为 1。equals(one)bitLength()
- 代替和与进行比较，使用mod(two)zerotestBit(0)
- 代替，使用divide(two)shiftRight(1)
- 而不是，只需将自身加两次，并且要添加一个，我们可以在第一次添加后通过翻转最少的位来做到这一点（这保证为零，因为我们只是将数字加倍）。multiply(three)num
如果您决定使用递归，那么不作为参数传递，而是让每个递归调用都像顶级执行一样执行，而不需要之前已经计算的内容的信息，这样会更优雅。在这种方法中，基本情况应返回 0，调用方应将 1 添加到递归返回的值中。i

这是你如何做到这一点：

    public int Problem9(BigInteger num) {
        return num.bitLength() == 1 ? 0 // Base case
             : 1 + Problem9(
                 num.testBit(0) ? num.add(num).flipBit(0).add(num) // 3x+1
                                : num.shiftRight(1) // x/2
               );
    }

n = 0, x = 123
n = 1, x = 370
n = 2, x = 185
n = 3, x = 556
n = 4, x = 278
n = 5, x = 139
n = 6, x = 418
n = 7, x = 209
n = 8, x = 628
n = 9, x = 314
n = 10, x = 157
n = 11, x = 472
n = 12, x = 236
n = 13, x = 118
n = 14, x = 59
n = 15, x = 178
n = 16, x = 89
n = 17, x = 268
n = 18, x = 134
n = 19, x = 67
n = 20, x = 202
n = 21, x = 101
n = 22, x = 304
n = 23, x = 152
n = 24, x = 76
n = 25, x = 38
n = 26, x = 19
n = 27, x = 58
n = 28, x = 29
n = 29, x = 88
n = 30, x = 44
n = 31, x = 22
n = 32, x = 11
n = 33, x = 34
n = 34, x = 17
n = 35, x = 52
n = 36, x = 26
n = 37, x = 13
n = 38, x = 40
n = 39, x = 20
n = 40, x = 10
n = 41, x = 5
n = 42, x = 16
n = 43, x = 8
n = 44, x = 4
n = 45, x = 2
n = 46, x = 1

上一个：每次访问（或从/复制到）列表中的对象时，如何运行方法？

下一个：尝试交换第一个和最后一个数组元素的值

使用 Java 通过递归来减少 BigIntegers。该方法完全减少数字，然后由于未知原因循环到“向上”的数字

Using Java to reduce BigIntegers using recursion. The method reduces the number completely, then loops to the number 'upwards' for unknown reasons

评论

评论