从1位数字打印到1000位数字-面试问题

Question

我参加了一次面试，被要求把数字从1打印到1000位数字-

1，2，3，。。. 999999999999999999999999999999999999999999999999........

我无法解决这个问题，但我仍然在寻找最好的方法，因为很明显，在这种情况下，你不能使用整数或浮点数，而且因为这是一个工作面试，我不能使用任何库来处理它。

有人能想出一个好的解决办法吗？最好使用Java/伪码。

Answer 1

使用递归(如果仅用于打印)：

void digits(int count) {
    if (count < 0) throw new IllegalArgumentException("invalid count: " + count);
    digits(count, "");
}

void digits(int count, String text) {
    if (count == 0) {
        System.out.println(text);
    } else {
        for (var i = 0; i < 10; i++) {
            if (i == 0 && text.isEmpty()) {
                digits(count-1, text);
            } else {
                digits(count-1, text+i);
            }
        }
    }
}

Answer 2

我参加了一次面试，我被要求把数字从1打印到1000位数字

我想他们希望你给出的答案是：

“我们需要打印1到10^ 1000 -1之间的数字。去年，全世界售出了价值80e9美元的处理器，即使每1美元卖出一个处理器，每台处理器比最快的处理器快1000倍，而且只有一条指令用来打印每个数字，而所有这些处理器都是在过去1000年里生产出来的，仍然是: 1e1000 /(80e9-1000-8.4e9-1000)> 1e973来打印所有数字。这是10956亿年。”

不管怎么说，如果你想等一下：

BigInteger n = BigInteger.ONE;
BigInteger last = BigInteger.TEN.pow(1000);

while(n.compareTo(last) < 0) {
    System.out.println(n);
    n = n.add(BigInteger.ONE);
}

假设只有System.out.print能够使用(String是一个库，请参阅3)，一种可能的解决方案不需要一次又一次地复制字符串，并且具有预期的输出可以是：

static void printDigits(int n) {
    ds(0, n, new byte[n]);
}

static void ds(int p, int k, byte[] d) {
    if (p < d.length) {                                     // if more digits to print
        for (byte i = 0; i < 10; i++) {                     // from digit 0 to 9
            d[p] = i;                                       //   set at this position
            ds(p + 1, i == 0 ? k : (p < k ? p : k), d);      //   populate next storing first non-zero
        }
    } else {
        if(k < d.length) {                                  // if is not zero
            if(k < d.length - 1 || d[d.length - 1] != 1)    // if is not one
                System.out.print(", ");                     // print separator
            for(int i = k; i < d.length; i++)               // for each digit
                System.out.print((char)('0' + d[i]));       // print
        }
    }
}

然后，对于printDigits(5)，输出是

1, 2, 3, 4, ..., 99999

1

2

3