1. 问题引入当“大”字遇上“最大”的数在算法竞赛和编程面试中我们经常会遇到一类问题给定一组规则要求找出符合规则的最大或最小的数。这类问题往往不是简单的排序或比较而是需要你深入理解规则并设计出高效的构造或搜索策略。2022年蓝桥杯国赛C/C大学B组的第四题“最大的数”就是这样一个典型的、考验选手综合能力的题目。题目本身并不复杂给定一个正整数n你需要使用数字1到9各一次每个数字只能用一次构造一个尽可能大的整数使得这个整数能被n整除。如果没有这样的整数则输出-1。初看之下你可能觉得这像是一个排列组合问题——把1到9的所有排列枚举出来检查是否能被n整除然后取最大值。这确实是一种思路但9! 362880种排列对于每个排列进行大数取模运算在竞赛的时间限制内通常是1秒是可行的。然而题目真正的难点和趣味性在于它引导我们思考两种截然不同的解法路径一种是直观的、基于数组或向量进行深度优先搜索DFS的解法另一种则是巧妙的、基于字符串排序与贪心的解法。前者锻炼了我们对于递归、回溯和剪枝的掌握后者则考验了我们对问题本质的洞察力和数学思维。在本文中我将带你详细拆解这两种解法。我们会从最朴素的暴力DFS开始逐步优化并深入探讨其时间复杂度和可行性。然后我们将跳脱出搜索的框架从一个全新的角度——数论和贪心构造——来审视这个问题你会发现有时候换一个思路问题会变得异常简单和清晰。无论你是正在备赛蓝桥杯的选手还是对算法设计感兴趣的开发者相信这篇详解都能给你带来启发。2. 理解题意与核心约束在动手写代码之前我们必须彻底吃透题目的每一个字。题目要求总结如下数字池只能使用数字1, 2, 3, 4, 5, 6, 7, 8, 9。使用规则每个数字必须且只能使用一次。这意味着我们最终构造的数是一个9位数如果使用全部数字且是1~9的一个排列。目标在所有能用这些数字构成的、能被给定整数n整除的数中找到数值最大的那个。输出如果存在这样的数输出它如果不存在即没有任何一个排列能被n整除则输出-1。这里有几个关键点需要明确“最大”的含义由于数字不重复构造的是一个9位数。要比较两个9位数的大小最直接的方法是先比较位数但这里位数固定然后从最高位开始逐位比较。在编程中如果我们按特定顺序生成排列可以方便地找到最大的。大数问题一个9位数最大是987654321在C的long long通常是-9e18 ~ 9e18范围内可以直接进行取模运算。这简化了问题我们不需要实现高精度取模。除数为nn是输入的正整数。我们需要构造的数num满足num % n 0。最朴素的想法是生成所有1~9的全排列对于每个排列计算其对应的整数值然后检查是否能被n整除并记录最大值。这个算法的时间复杂度是O(9! * 9)大约3.6e6次运算在1秒内是完全可以接受的。这为我们实现DFS解法提供了基础。然而n的范围题目并未明确给出在竞赛中通常会在另一个地方说明。如果n非常大以至于没有任何一个9位数能整除它那么DFS会遍历所有情况后返回-1。如果n很小可能会有很多解我们需要找到最大的。无论哪种情况DFS都是一种可靠的“通用解法”。3. 解法一深度优先搜索DFS与回溯深度优先搜索是解决这类排列问题的经典方法。我们可以把构造数字的过程看作在一棵树上进行探索树的根节点是空数字每一层代表我们选择下一位数字每个节点有若干个分支剩余可用的数字。我们需要遍历所有从根到叶子的路径即所有排列并检查路径对应的数字是否满足条件。3.1 DFS的基本框架与递归函数设计我们设计一个递归函数dfs(current_num, used, depth)。current_num当前已经构造出来的数字整数形式。used一个布尔数组或整数状态位标记数字1~9中哪些已经被使用过了。depth当前已经构造的数字位数即递归深度。递归的流程如下递归终止条件当depth 9时说明我们已经用完了所有数字current_num就是一个完整的候选数。此时检查current_num % n 0如果满足则用其更新全局最大答案ans。递归过程对于当前状态我们遍历所有未使用的数字i从1到9。标记数字i为已使用。计算新的数字new_num current_num * 10 i。这里乘以10相当于在末尾添加一位数字。递归调用dfs(new_num, used, depth 1)。回溯在递归返回后取消数字i的标记以便尝试其他分支。这就是回溯算法的核心尝试一个选择递归探索后续然后撤销选择尝试其他可能性。3.2 关键优化从大到小枚举数字上面的框架能找出所有解但如何保证我们找到的第一个解或最终记录的解是最大的呢这里有一个非常重要的优化技巧在每一层选择数字时从大到小进行枚举即先尝试9再尝试8...最后尝试1。为什么这样做 因为我们要找的是最大的数。对于一个多位数高位数字的大小对数值的影响远大于低位数字。如果我们从最高位开始每次都优先选择当前可用的最大数字那么构造出来的数字在“字典序”上就是最大的。如果这个数字恰好能被n整除那它就是我们想要的最大解。即使它不能被整除由于我们是从大到小枚举所有排列我们找到的第一个可行解也一定是所有可行解中最大的。这个优化不仅帮助我们直接找到最大解还可以用于可行性剪枝。最优性剪枝如果我们已经找到了一个可行解由于我们是从大到小搜索这个解就是最大的理论上可以终止搜索。但在本题中为了验证算法的正确性或者处理“找全部解”的变体我们通常还是会记录最大值而不是直接返回。提前终止一个更激进的优化是当我们已经构造了部分数字current_num并且知道剩下的位数即使全部填上当前可用的最大数字最终形成的数也不可能超过当前记录的最大答案ans时就可以剪枝。但计算这个上界需要一些额外操作对于本题数据规模简单的从大到小枚举已经足够高效。3.3 代码实现与细节处理以下是基于DFS解法的C代码实现包含了详细的注释#include iostream #include vector using namespace std; long long n; // 除数 long long ans -1; // 最终答案初始化为-1 // DFS函数 // current_num: 当前构造的数字 // used: 标记数组used[i]为true表示数字i已被使用 // depth: 当前深度即已使用的数字个数 void dfs(long long current_num, vectorbool used, int depth) { // 终止条件已经使用了9个数字 if (depth 9) { if (current_num % n 0) { // 找到一个可行解更新最大答案 if (current_num ans) { ans current_num; } } return; } // 从大到小枚举当前可用的数字9, 8, ..., 1 // 这样可以保证搜索到的第一个可行解就是字典序最大即数值最大的解 for (int i 9; i 1; --i) { if (!used[i]) { // 如果数字i未被使用 used[i] true; // 选择数字i long long new_num current_num * 10 i; // 构造新数字 dfs(new_num, used, depth 1); // 递归探索下一层 used[i] false; // 回溯撤销选择 } } } int main() { cin n; vectorbool used(10, false); // 下标1~9有效used[0]无用 dfs(0, used, 0); // 从数字0空、深度0开始搜索 cout ans endl; // 输出答案若未找到则ans仍为-1 return 0; }代码细节与注意事项数据类型current_num和ans使用long long以确保能容纳最大的9位数987654321约9.8e8并进行取模运算。状态标记使用vectorbool used(10, false)来标记数字是否使用。索引i对应数字i。used[0]未被使用保持false。递归起点dfs(0, 0, 0)。初始数字为0深度为0。输出搜索结束后如果ans仍为初始值-1则说明没有找到任何解输出-1。3.4 DFS解法的时间复杂度与适用性分析时间复杂度最坏情况下需要遍历所有9! 362880个排列。对于每个排列我们进行常数次操作构造数字、取模、比较。因此总计算量大约在百万级别对于现代计算机在1秒内完成绰绰有余。空间复杂度主要是递归调用栈的深度最大为9以及一个大小为10的used数组可以忽略不计。优点思路直观代码易于理解和实现。它是一种“通用”解法适用于许多类似的排列、组合、选择问题。缺点当数字范围变大时例如使用0~9共10个数字排列数10! 3628800依然可接受但如果数字更多或者约束条件更复杂导致无法有效剪枝DFS可能会超时。实操心得在竞赛中如果对数学构造法没有把握DFS剪枝通常是解决此类小规模排列问题的“保底”策略。实现时务必注意递归函数的参数设计、状态标记与回溯的对称性有标记就必须有撤销以及递归终止条件的正确性。从大到小枚举这个剪枝技巧非常实用能显著提升效率并直接得到最大解。4. 解法二基于数学性质的字符串构造法DFS解法虽然有效但总让人觉得有些“暴力”。我们能否不通过搜索而是直接“构造”出最大的那个数呢答案是肯定的但这需要我们对整除性有更深的理解。让我们重新审视问题我们要用1~9构造一个能被n整除的最大的数。这等价于我们要找到1~9的一个排列使得这个排列对应的数模n为0并且排列的字典序最大。这里有一个关键的观察如果我们把1~9这九个数字直接按照从大到小的顺序排列得到987654321这个数本身不一定能被n整除。但是我们可以通过调整数字的顺序即寻找这个排列的一个“重排”来使其满足整除条件。问题转化为在987654321的所有重排即所有排列中找到一个能被n整除的。既然我们要最大的我们就应该从最大的排列开始尝试依次尝试较小的排列直到找到一个能被整除的。这听起来是不是很像一个“查找”过程我们可以利用C标准库的强大功能来实现。4.1 利用next_permutation进行降序排列遍历C的algorithm头文件中提供了next_permutation和prev_permutation函数它们可以按照字典序生成下一个或上一个排列。我们的策略是首先将数字1~9按从大到小的顺序放入一个数组或字符串中得到初始排列“987654321”。这个排列对应的是理论上最大的数。使用一个循环每次循环中 a. 将当前排列转换成对应的整数。 b. 检查这个整数是否能被n整除。 c. 如果能这就是我们要找的最大解输出并结束。 d. 如果不能就使用prev_permutation函数将排列变为字典序上的“上一个”排列即比当前排列小的下一个最大排列。如果循环遍历了所有排列即prev_permutation返回false表示已经到达第一个排列“123456789”都没有找到解则输出-1。使用prev_permutation是因为我们从最大排列开始需要依次获取更小的排列。4.2 代码实现与转换技巧以下是基于字符串和prev_permutation的解法#include iostream #include algorithm #include string using namespace std; int main() { long long n; cin n; // 初始化为最大排列9, 8, ..., 1 string digits 987654321; bool found false; long long num; // 使用do-while循环先处理初始排列 do { // 将字符串转换为长整型数 // 方法1使用stollC11 // num stoll(digits); // 方法2手动转换更通用 num 0; for (char c : digits) { num num * 10 (c - 0); } // 检查是否能被n整除 if (num % n 0) { found true; break; // 找到第一个即最大的可行解立即退出 } // 获取字典序上的上一个排列即更小的数 } while (prev_permutation(digits.begin(), digits.end())); if (found) { cout num endl; } else { cout -1 endl; } return 0; }代码细节与注意事项字符串操作使用string类型存储数字排列非常方便因为可以直接使用algorithm中的排列函数。prev_permutation的用法该函数会将区间内的元素变换为字典序上的上一个排列。如果变换成功返回true如果当前排列已经是第一个最小排列无法再获取上一个则返回false。这正是我们循环的终止条件。字符串转整数可以使用stoll函数string to long long但需要注意编译器需支持C11。手动转换的循环 (num num * 10 (c - 0)) 是更通用且高效的方法。循环逻辑使用do-while循环是为了确保初始排列“987654321”能被首先检查。如果使用while循环则需要先检查再调用prev_permutation逻辑上稍显别扭。效率这个解法同样需要遍历最多9!个排列时间复杂度与DFS相同。但它代码更简洁完全依赖标准库不易出错。4.3 从“搜索”到“构造”的思维飞跃虽然字符串解法在代码层面看起来和DFS一样是遍历但其背后的思维是不同的。DFS强调的是“探索所有可能性”的过程而字符串解法强调的是“从理论最大值开始逐个尝试更小的候选值”。后者更贴近我们人类的直觉既然我要最大的那我就从最大的开始试。更进一步思考是否存在真正的“构造性”算法即不通过遍历直接通过计算得到答案这取决于除数n的性质。例如如果n是 2 的幂、5 的幂、3 或 9我们可以根据数字和的特性、末位数的特性来快速判断和构造。但对于一个任意的n目前没有通行的、优于遍历的确定性构造算法。因此在通用情况下这种“有序遍历”已经是一种非常优秀的策略。实操心得next_permutation和prev_permutation是处理排列相关问题的利器它们内部实现了高效的算法通常是字典序法代码简洁不易出错。在竞赛中如果问题规模允许如 n ≤ 10应优先考虑使用它们来替代手写DFS除非DFS中有特殊的剪枝优化。将数字处理成字符串再利用这些算法往往能让代码清晰一个数量级。5. 两种解法的对比与选择我们已经详细分析了数组DFS解法和字符串排列解法。现在我们来系统地对比一下它们并讨论在何种情况下应如何选择。5.1 性能与效率对比特性DFS数组回溯解法字符串prev_permutation解法时间复杂度O(9! * 9)O(9! * 9)空间复杂度O(9) (递归栈标记数组)O(9) (字符串)核心操作递归、回溯、手动枚举与剪枝库函数生成排列、字符串转整数代码复杂度中等需要正确实现递归和回溯低主要逻辑由库函数完成可控性高可以方便地加入自定义剪枝逻辑如基于当前结果的部分剪枝低排列生成顺序固定难以插入复杂的剪枝思维模式过程式强调“如何一步步构建出所有解”声明式强调“从解空间的一端开始顺序检查”从表格可以看出两种解法在最坏情况下的时间复杂度是相同的都属于完全遍历。在实际运行中由于prev_permutation是高度优化的库函数而递归调用有一定开销字符串解法在常数时间上可能略有优势但对于9!这个量级差异微乎其微都可以在毫秒级完成。5.2 可扩展性与变体问题如果题目条件发生变化两种解法的适应能力也不同数字可以重复使用DFS解法可以很容易地修改循环条件允许数字重复选择。而prev_permutation是针对不重复元素的排列对于可重复的情况需要先生成所有可能的多重集排列或者使用next_combination之类的思路会更复杂。数字范围变大如0~9两者都能轻松适应只需修改初始集合。DFS需要调整used数组大小和循环范围字符串解法只需修改初始字符串为“9876543210”。需要找出所有解而不仅仅是最大解DFS可以自然地记录所有解。字符串解法需要在循环中收集所有满足条件的排列而不是在找到第一个后就break。加入更强的约束条件剪枝例如在构造过程中如果当前部分数字已经不能被n整除某个中间值那么后续无论怎么添加数字整个数也不可能被整除这只对某些特殊的n成立如n是 2、5、10 的幂等。这种剪枝在DFS中很容易加入在递归函数中检查current_num % n是否满足某种条件而在字符串解法中则难以实现因为它是先生成完整排列再检查。5.3 实战选择建议根据以上分析我们可以给出一些选择建议首选字符串解法当问题规模固定且较小如本题的9个数字且没有特殊剪枝需求时强烈推荐使用字符串prev_permutation的解法。理由如下代码简洁不到20行核心代码逻辑清晰不易出错。不易出错无需手动管理递归和回溯状态避免了深搜中常见的状态恢复错误。调试方便排列顺序明确易于跟踪。符合直觉“从大到小尝试所有排列”的思路非常直接。选择DFS解法在以下情况下DFS是更好的选择需要复杂剪枝题目约束允许在搜索中途就判断某些分支不可能产生解从而提前剪枝大幅减少搜索空间。问题规模稍大但剪枝有效例如数字更多如12个但通过强约束可以剪掉大部分分支。作为学习练习对于初学者亲手实现DFS回溯是理解递归和搜索算法的重要途径。掌握DFS是解决更复杂搜索问题如八皇后、数独、图遍历的基础。避坑指南在竞赛中如果时间紧迫我通常会先写字符串解法因为它又快又稳。只有在字符串解法明显会超时例如数字个数超过10且无其他限制或者题目有明显的可剪枝特征时我才会转向实现DFS。一个常见的错误是在DFS中忘记“回溯”即撤销used[i] true的状态这会导致程序错误地认为某些数字仍被占用从而漏掉大量排列。务必记住递归调用后的状态恢复与递归调用前的状态修改必须对称。6. 从本题延伸的思考与练习“最大的数”这道题虽然描述简单但它串联起了多个重要的编程和算法概念。解决它之后我们可以沿着几个方向进行延伸思考和学习这对于提升算法能力大有裨益。6.1 变体问题如果数字包含0怎么办原题使用的是1~9。如果数字池是0~9呢情况会变得复杂一些因为0不能作为一个多位数的首位。在构造数字时我们需要避免以0开头。对DFS解法的影响在递归的第一层depth 0我们不能选择数字0。在代码中可以在遍历数字的循环里当depth 0且i 0时直接continue。对字符串解法的影响我们不能简单地从“9876543210”开始用prev_permutation因为很多排列会以 ‘0’ 开头对应的是更少位数如8位的数这些数可能比某些9位数小但比另一些9位数大破坏了“从最大排列开始”的假设。一个解决方法是生成所有排列但在转换整数前检查第一个字符是否为 ‘0’如果是则跳过。但这样就不能保证我们检查的顺序是严格从大到小了。更严谨的方法是分别考虑9位数首位非0和8位数等情况但这样会复杂很多。因此对于含0的情况DFS解法在逻辑处理上更清晰、更可控。6.2 性能边界当数字个数增加时本题只有9个数字9! 362880是安全的。如果数字个数增加到12个呢12! 479001600接近5亿在1秒内完成所有排列的检查和转换可能就比较吃力了C大约在2-3秒左右取决于机器和优化。这时纯粹的遍历就可能面临超时风险。我们需要思考如何优化剪枝这是最重要的手段。分析题目是否有其他约束可以在构造过程中提前排除大量无效分支。例如如果n是偶数那么构造的数的末位必须是偶数如果n能被5整除末位必须是0或5。这些规则可以在DFS的每一层进行判断。Meet-in-the-Middle折半搜索对于某些整除性问题我们可以将数字分成两半分别生成所有可能的半部分数字及其模n的余数然后通过组合两半的余数来得到整体余数为0的解。这可以将阶乘级的复杂度降低到大约O((k/2)! * 2)对于k126! 720再平方一下约50万远小于5亿。数论优化利用n的特定性质。例如如果n是3的倍数那么一个数能被3整除的充要条件是它的各位数字之和能被3整除。1~9的总和是45是3的倍数所以任何由1~9组成的排列都能被3整除。如果n3那么答案直接就是987654321。深入挖掘n的质因数分解可能发现更多规律。6.3 与“数字整除”性质相关的其他经典问题理解本题后可以尝试解决一些相关的、更富挑战性的问题巩固知识构造特定倍数给定数字集合构造能被指定数整除的最小数而非最大数。思路类似只需将枚举顺序改为从小到大。包含重复数字的排列如果数字可以重复使用或者给定的数字集合本身就有重复如何高效地生成所有不重复的排列并检查这需要用到“多重集的全排列”生成算法DFS需要记录每个数字的剩余次数而next_permutation对包含重复元素的序列也能正确工作生成不重复的排列。动态规划与状态压缩如果数字集合更大比如15个不同的数字且n不大比如n 1000我们可以用状态压缩DP来解决。定义dp[mask][r]表示使用了mask所代表的数字集合后当前数字模n的余数为r时能构成的最大数或是否存在。这是一种更高级的解法将指数级的排列搜索优化成了O(2^k * n)的DP其中k是数字个数。通过这道“最大的数”我们不仅学会了一种题目的两种解法更重要的是我们看到了如何将一个问题从暴力搜索通过深入分析进行优化并连接到更广阔的算法知识图谱。在编程竞赛和实际开发中这种多角度分析、权衡不同方案的能力往往比记住某个特定算法更为重要。