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

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.

我有以下接近的解决方案:

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 中减去 2，计算必须减去多少次才能使 n 变为零。但是这些解决方案依赖于具有返回值的方法；这个谜题要求没有返回值。

我还可以看到如何使用一个函数调用 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);
    }
}

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