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

Question

我接受了面试，被要求打印从 1 到 1000 位的数字 -

1, 2、 3、 . . . ., 99999999999999999999999999999999999999999999999.......

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

有谁能想出好的办法吗？最好在 Java/pseudocode.

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

I had an interview and I've been asked to print numbers from 1 to a 1000 digit number

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

"我们需要打印从 1 到 10^1000-1 的数字。去年，全球售出价值 80e9 美元的处理器 [1]，即使每美元售出一个处理器每个处理器都比其中最快的处理器快一千倍[2]，并且只使用一条指令来打印每个数字，所有这些处理器都是在过去 1000 年内生产的，仍然是：1e1000 / (80e9 - 1000 - 8.4 e9 - 1000) > 1e973 秒打印所有数字。即 10e9560 亿年。"

无论如何，如果你想等一下：

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] https://epsnews.com/2020/09/14/total-microprocessor-sales-to-edge-slightly-higher-in-2020/

[2] https://en.wikipedia.org/wiki/Clock_rate

[3]https://docs.oracle.com/javase/7/docs/api/java/lang/String.html

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

print numbers from 1 to 1000 digit number - interview question

java

data-structures

pseudocode