面试题17：打印从1到最大的n位数

从“最大值本身也放不下”开始

先预测：输入n=100时，最大的100位十进制数无法放入32位、64位整数，甚至无法精确放入普通double。如果连循环上界都不能表示，for (i=1; i<=max; ++i)从哪里得到max？

题目要求“打印从1到最大的n位数”。最大值是：10^n - 1。大数问题是用字符串模拟数字的核心考点，n 位十进制数用 n 字符的字符串表示。

例如n=3时打印1到999。这个问题首先是：不能先把10^n-1塞进普通整数再循环。作者用长度固定为n的十进制字符数组保存当前值，每一位永远只在字符'0'..'9'中变化。

表示问题解决后，输出规模仍然巨大。需要打印的非零整数数量是：

所以n=100虽然能用100字节字符数组表示当前值，却要求输出近10^100个数字，物理上不可完成。字符表示避免溢出，不会消除由题目输出本身决定的指数工作量。

方法一：在十进制字符串上模拟加一

作者第一解把字符数组初始化为全0，然后不断执行。每次成功加一后跳过前导零并输出；最高位还产生进位时，说明刚从全9越过n位上限，停止循环。

0098→0099只修改个位；0099→0100让末两位归零并把百位加一。这个过程只依赖字符与，不需要当前整体数值能放入任何整数类型。

下面将输出抽象成回调emit，而不是把全部结果塞进向量。回调可以写控制台、文件、网络流，或在测试中收集小输入。

#include <functional>
#include <string>
#include <string_view>
 
bool incrementDecimal(std::string& digits) {
    int carry = 1;
    for (std::size_t offset = 0;
         offset < digits.size() && carry != 0;
         ++offset) {
        const auto index = digits.size() - 1 - offset;
        const int sum = digits[index] - '0' + carry;
        digits[index] = static_cast<char>('0' + (sum % 10));
        carry = sum / 10;
    }
    return carry == 0;
}
 
std::string_view withoutLeadingZeros(const std::string& digits) {
    const auto first = digits.find_first_not_of('0');
    if (first == std::string::npos) return {};
    return std::string_view(digits).substr(first);
}
 
void printByIncrement(
    int n,
    const std::function<void(std::string_view)>& emit
) {
    if (n <= 0) return;
    std::string digits(static_cast<std::size_t>(n), '0');
    while (incrementDecimal(digits)) {
        emit(withoutLeadingZeros(digits));
    }
}

起始值全0，第一次加一得到00...01并输出1；全9再加一时数组内部回到全0且carry仍为1，函数返回假，外层不输出0。每次加一最坏扫描n位，普通数字通常只改末尾少量位，但整体成本仍被输出规模主导。

方法二：逐位枚举所有十进制组合

作者第二解把长度n的每一位都看成一个0..9选择。递归填到最后一位就输出当前字符数组，去掉左侧，并跳过全0状态。

书中常称其为，但严格说它不是互异元素的排列：每一位可以重复选同一个数字，生成的是n个十进制集合的笛卡尔积。总叶子数10^n，叶子字典序恰好对应00...00到99...99的数值顺序。

void enumerateDigits(
    std::string& digits,
    std::size_t index,
    const std::function<void(std::string_view)>& emit
) {
    if (index == digits.size()) {
        const auto normalized = withoutLeadingZeros(digits);
        if (!normalized.empty()) emit(normalized);
        return;
    }
 
    for (char digit = '0'; digit <= '9'; ++digit) {
        digits[index] = digit;
        enumerateDigits(digits, index + 1, emit);
    }
}
 
void printByEnumeration(
    int n,
    const std::function<void(std::string_view)>& emit
) {
    if (n <= 0) return;
    std::string digits(static_cast<std::size_t>(n), '0');
    enumerateDigits(digits, 0, emit);
}

递归树满足T(n)=10T(n-1)+O(1)：

作者源码对全0数组调用PrintNumber时不打印数字字符，但仍打印一个制表符，因此递归版会多一个空分隔项。现代实现应让格式化函数返回空视图并由调用者明确跳过，使两种方案都恰好输出1到最大值。

输出下界比算法选择更重要

从1到10^n-1的总十进制数字字符数为：

任何真的打印全部结果的算法至少要写出这些字符，所以若把输出 I/O 计入时间，复杂度是Θ(n10^n)，不只是O(10^n)。叶子处每次从头扫描前导零也与这个上界同阶。

两种作者方案的工作内存都只需当前n位字符。增量法额外栈为O(1)；递归法调用栈O(n)。若把全部字符串存入vector，空间会膨胀到输出规模Θ(n10^n)，这不是题目“打印”所需，也会让很小的n就耗尽内存。

流式回调还可以提供取消信号或输出上限。例如 UI 只预览前1000项时，回调返回假让生成器停止；但此时接口语义应改成“枚举前缀”，不能声称完成了原题全部输出。

字符串加一的摊还位操作

单次从...999跨到下一数值会扫描多位，最坏O(n)；但不是每次都传播长进位。个位每次改变，十位每10次改变，百位每100次改变。打印完整范围时，所有加一调用触碰的字符次数形成几何级数：

10^n + 10^(n-1) + ... + 10，

总量仍是O(10^n)。因此不计格式化和 I/O 时，增量核心的摊还每个数只改常数个位；递归枚举同样每条树边写一个字符，全部树边数也是O(10^n)。

真正把总时间提高到Θ(n10^n)的是输出每个数字的有效字符和每次从左扫描前导零。若维护首个非零位置可以减少部分扫描，但当数字从999到1000等长度变化时必须更新，且写出字符的下界仍不可降。

这种区分有助于回答面试追问：算法内部生成并非每项都做n位加法，但“打印”包含 I/O，所以整体不能只按摊还加法声称O(10^n)。复杂度必须说明是否计入输出长度。

两种方案的顺序与不变量

增量法的不变量是：每轮输出前，字符数组表示上次输出值加一，且仍在n位范围内。十进制加一保证严格递增，不会重复或跳过；最高位溢出恰好发生在全9之后，所以范围完整。

递归法的不变量是：进入深度index时，前index位已经固定，后续递归会按字典序枚举其余所有组合一次。十进制等宽字典序与数值序一致；去前导零后，0001..9999对应自然数1到最大值。

两者分别从“相邻数值关系”和“完整数位空间”证明覆盖。用两个结构不同的实现交叉测试，能发现进位漏项、递归边界多项和全零输出问题。

前导零是展示规则，不是数值状态

内部固定宽度让进位与递归简单，因此0007应一直保留为4个字符；只有送给输出端时显示为7。若每次加一后真的删除前导零，缓冲长度会变化，最高位溢出和下标逻辑都变复杂。

withoutLeadingZeros返回指向原字符串的string_view，回调只能在下一次修改digits之前使用它。异步保存时必须复制成std::string；接口文档要说明借用生命周期，避免输出端持有随后被改写的视图。

也可按有效位数1到n分别递归，最高位只枚举1到9，后续位枚举0到9。这样不生成前导零与全零状态，但代码多一层长度循环；输出数量没有变化，渐进下界也不会改善。

按有效位数生成的另一种递归

固定n槽位方案先生成0001再格式化为1。另一种设计按有效长度length=1..n分批：每批最高位只选1到9，其余length-1位选0到9。长度1依次生成1到9，长度2生成10到99，天然没有前导零。

它的优点是叶子可以直接输出整个缓冲，不必每次扫描首个非零；递归深度等于当前有效长度。缺点是外层要重建或调整不同长度缓冲，证明顺序时还要说明“先短后长”与数值升序一致。两种设计生成的合法输出数量完全相同。

固定宽度版本更贴近作者源码，也让增量法与递归法共享withoutLeadingZeros格式化。按长度版本则适合输出层不接受前导零视图的接口。选择应基于代码清晰度和输出协议，而不是声称减少了指数级结果。

若题目扩展为“只打印恰好n位的数”，按长度方案只运行最后一批，范围从10^(n-1)到10^n-1；固定宽度方案则必须过滤前n-1位范围。先确认“最多n位”还是“恰好n位”，否则同一代码会回答不同问题。

BigInt 解决表示，不解决输出规模

支持任意精度整数的语言可以写 BigInt 计数器，从1递增到10^n-1。这在语义上正确，也可能比手写字符串加法更简洁；但面试题通常要求展示大数边界意识和逐位进位，因此作者使用字符数组。

BigInt 也不是常数成本机器整数。位数随n增长，加一与十进制格式化需要处理多字数据，转换成文本仍要写出每一位。库隐藏了表示细节，却没有把10^n个输出变少。

在生产工程中，若平台已有成熟大整数库，应优先复用而不是自行实现完整算术；本题手写的只有“十进制加一”，范围很小且容易验证。不要从这道题推导出自研任意精度乘除法比标准库更可靠。

接口若只需要返回最大值的文本，直接生成n个字符9即可，时间O(n)；但原题要求列出中间每个数。把“求最大值”与“打印整个区间”混为一谈，会得出错误的低复杂度结论。

字符串加法的边界与异常安全

n<=0时作者直接返回，不分配缓冲。将负int先转换为size_t再检查会变成巨大正数并尝试分配，应保持“先验证、后转换”的顺序。

输出回调可能抛异常或报告写入失败。std::string由 RAII 管理，不会泄漏；调用者应决定立即停止、重试还是传播错误。作者使用new[]/delete[]，若打印函数抛异常，手工删除可能被跳过，现代容器更稳健。

极大的n还可能让递归版栈溢出，但在达到很深递归前，完整输出已经不可行。若只做惰性前缀生成且n确实很大，增量法更合适；若要并行划分前缀空间，递归法可按最高若干位分片，但输出合并必须保持全局顺序。

流式输出要处理背压与借用生命周期

控制台或磁盘往往比字符生成慢。同步回调天然形成背压：只有当前写入完成才生成下一项，内存保持有界；异步队列若生产速度更快，必须设置容量并在队列满时等待，否则“流式”仍会积累接近全部结果。

string_view指向正在复用的digits缓冲。同步回调在返回前消费它是安全的；若把视图放入异步队列，下一次加一会改写同一内存，队列中所有项可能最终看到相同或损坏内容。跨越回调生命周期时必须复制成拥有存储的string。

写入错误也应成为生成协议的一部分。回调可返回bool或错误对象：成功继续，取消或磁盘满立即停止。将异常直接吞掉后继续生成只会浪费指数工作，并让调用者误以为输出完整；传播错误时 RAII 字符串会自动释放。

分隔符属于输出层。作者每个数字后打印制表符，并在递归全零状态也打印一个空制表项；更干净的接口只发送规范数字串，由文本输出器决定逗号、换行或制表符，并负责最后一个元素是否带尾分隔符。

并行分片不能破坏全局顺序

递归空间可按前缀分片：一个任务生成首位1的所有后缀，另一个生成首位2的所有后缀。任务内部仍按字典序输出，理论上能并行生成；但原题要求按顺序打印，首位2的结果必须等首位1全部提交后才能写到最终流。

若每个任务先缓存整个分片再按序合并，内存可能再次爆炸；更合理的是为分片设置有界管道，由协调器按前缀顺序消费。由于最终输出设备通常是串行瓶颈，并行生成未必提升吞吐，反而增加同步成本。

增量法不易无重叠分片，但可给每个任务一个十进制起止字符串，实现任意精度区间计数器。区间边界比较和终止也必须使用字符串数值规则，不能转回机器整数。

并行化只改变生成调度，不改变Θ(n10^n)输出下界。实际系统更常做分页、限定范围或写压缩表示；一旦不再列出每个数字，需求已经从原题“打印全部”变成另一种接口。

长输出如何支持恢复与完整性校验

对可实际运行但耗时较长的n，输出端可能中断。增量法可把当前固定宽度字符数组作为检查点，恢复时先校验长度和字符范围，再从该值加一继续；递归法要保存当前各层选择与下一分支下标，状态更复杂。

检查点必须同时记录“当前值是否已经成功提交”。若先写检查点再写输出，崩溃后可能漏一项；先写输出再写检查点，恢复后可能重复一项。需要严格一次语义时，应让输出与检查点在同一事务中提交，或给每项附带可去重序号。

完整性可用预期计数、首尾值和递增关系验证。对n较小可逐项比较两种算法；对流式大结果可维护输出条数和滚动哈希，但哈希相同只能提供高概率证据，不能代替确认写入系统没有截断。

题目中的控制台制表输出没有恢复要求，但把算法改造成文件导出工具时，这些协议问题会比生成下一数字更重要。算法边界与 I/O 交付边界应分层设计。

官方输入与可自动断言的测试

作者依次运行n=1,2,3,0,-1，人工观察两种方法输出。自动测试不应比较整段控制台文本，而应在小输入中让回调收集结果，检查数量、首项、末项、相邻顺序，并比较两种算法完全一致。

#include <cassert>
#include <string>
#include <vector>
 
using Printer = void (*)(
    int,
    const std::function<void(std::string_view)>&
);
 
std::vector<std::string> collect(Printer printer, int n) {
    std::vector<std::string> values;
    printer(n, [&](std::string_view value) {
        values.emplace_back(value);
    });
    return values;
}
 
void testPrintNumbers() {
    for (int n : {1, 2, 3}) {
        const auto byIncrement = collect(printByIncrement, n);
        const auto byEnumeration = collect(printByEnumeration, n);
        assert(byIncrement == byEnumeration);
        assert(byIncrement.size() ==
               static_cast<std::size_t>(
                   n == 1 ? 9 : n == 2 ? 99 : 999));
        assert(byIncrement.front() == "1");
        assert(byIncrement.back() ==
               std::string(static_cast<std::size_t>(n), '9'));
    }
    assert(collect(printByIncrement, 0).empty());
    assert(collect(printByEnumeration, -1).empty());
}

还应单测incrementDecimal的0098→0099→0100和999→溢出，因为端到端输出太长时不易定位进位错误。格式化单测覆盖000、001、010、100，确认全零跳过且内部缓冲不被修改。

本章练习

概念说明

本章核心概念包括：字符串模拟加法，全排列递归。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 打印从1到最大的n位数首先是大数问题，不能先计算10^n-1到普通整数。
2. 字符串模拟加法从个位加一并传播进位，最高位溢出时结束。
3. 全排列递归逐位枚举0到9，生成全部10^n个固定宽组合。
4. 前导零只在输出时跳过，全零状态不应产生数字0或空分隔项。
5. 真实输出数量为10^n-1，总字符量为Θ(n10^n)，算法无法绕过。
6. 两种方案当前缓冲都是O(n)；递归法另有O(n)调用栈。
7. 结果应流式发送给输出端，不能默认缓存全部字符串。
8. 官方n=1,2,3,0,-1可通过回调收集小结果自动断言。

名词解释