使用递归的整数除法——以及其他一些有趣的限制

Question

我正在尝试解决 Java 中的一个难题，以启发自己。有人告诉我是设计谜题的人的解决方案，但我自己找不到。

这是谜题：

Implement the following method in Java
/**
 * Divides a natural number by two.
 * 
 * @param n
 *            The number to be divided
 * @updates n
 * @ensures n = floor(n/2)
 */
private static void split(NaturalNumber n) {...}
The NaturalNumber class is simply a class that stores a natural number using a string. ( That is, it can store numbers much larger than Integer.MAX_VALUE. )

The class provides these instance methods and inherited methods, as well as the NaturalNumber.isZero() method, which returns true if the instance's internal string value is "0", false otherwise.

It's worth noting that the NaturalNumber.divideBy10() method essentially pops the rightmost digit off the number, returns it as an int and updates the instance's internal value.

Do not use static properties on the main class to store values. Similarly, do not write static helper methods.

Do not convert n to some other data type and operate on that. Do not use external libraries.

Furthermore, split() must be implemented using recursion.

我制定了以下 near 解决方案：

private static void split(NaturalNumber n) {
  // Initialize local variables.
  String stringBuffer = "";
  int numerator = 0;
  int quotient = 0;
  int remainder = 0;

  int thisDigit = n.divideBy10();

  if (n.isZero()) {
    quotient = thisDigit / 2;
    remainder = thisDigit % 2;
    n.transferFrom(new NaturalNumber2(quotient * 10 + remainder));
  } else {
    split(n);
    numerator = n.divideBy10() * 10 + thisDigit;
    quotient = numerator / 2;
    remainder = numerator % 2;
    if (!n.isZero()) {
      stringBuffer += n.toString();
    }
    stringBuffer += Integer.toString(quotient * 10 + remainder);
    n.transferFrom(new NaturalNumber2(stringBuffer));
  }
}

上面简单的进行了长除法。但是调用堆栈中的最后一帧不必要地将其操作的其余部分附加到解决方案的末尾。

我见过类似问题的解决方案，递归地从 n 中减去二，计算必须减去多少次二才能使 n 变为零。但是这些解决方案依赖于具有 return 值的方法；这个谜题要求没有 return 值。

我还可以看到如何使用对 split() 的一个函数调用和内部循环来解决这个难题。但我被告知解决方案不能依赖循环来对 n.

进行操作

有人知道解决方案吗？

Answer 1

假设n的数字是a...yz。如果 y 是偶数，则 n / 2 的数字是 a...y / 2 和 z / 2 的串联。如果 y 是奇数，令 Y = y - 1。那么n / 2的数字就是a...Y / 2和1z / 2的串接。

我们可以这样实现：

private static void split(NaturalNumber n) {
    int z = n.divideBy10();
    int y = n.divideBy10();

    if (n.isZero()) {
        // Base case.
        int result = (y * 10 + z) / 2;
        n.multiplyBy10(result / 10);
        n.multiplyBy10(result % 10);
    } else if (y % 2 == 0) {
        n.multiplyBy10(y);
        split(n);
        n.multiplyBy10(z / 2);
    } else {
        n.multiplyBy10(y - 1);
        split(n);
        n.multiplyBy10((10 + z) / 2);
    }
}

顺便说一句，这些方法名称很糟糕，让 NaturalNumbers 可变是一个奇怪的设计选择。

使用递归的整数除法——以及其他一些有趣的限制

Integer division using recursion--and a few other interesting limitations

java

recursion

division

in-place

integer-division