PAT乙级1064题解析：数字朋友数算法与实现

1. PAT乙级1064题目解析与实战攻略作为计算机程序设计能力考试PAT乙级的一道经典题目1064题考察的是考生对基础算法和编程思维的掌握程度。这道题在PAT考试中属于中等难度主要测试数组处理、逻辑判断和边界条件处理能力。下面我将从题目分析、解题思路、代码实现到优化技巧全方位拆解这道题目。1.1 题目要求理解题目描述大致如下给定一组正整数要求统计其中朋友数的数量。所谓朋友数是指该数的各位数字之和。例如123的朋友数是1236。最终需要输出所有不同的朋友数并按升序排列。关键点分析输入格式第一行给出正整数N1000随后给出N个不超过10000的正整数处理要求计算每个数的各位数字之和输出要求第一行输出不同朋友数的个数第二行按升序输出这些朋友数空格分隔1.2 核心算法设计解决这个问题需要以下几个步骤数字分解如何将一个整数的各位数字分离出来求和计算对分离出的数字进行求和去重处理确保相同的和只被记录一次排序输出将结果按升序排列对于数字分解常见的有两种方法数学方法通过取模和除法运算逐位提取字符串方法将数字转为字符串后逐个字符处理提示在实际编程竞赛中数学方法通常效率更高但字符串方法更直观易懂。初学者可以先掌握字符串方法熟练后再尝试数学方法。2. 详细实现步骤2.1 输入处理与数据结构选择首先我们需要考虑如何存储和处理输入数据。由于题目要求统计不同的朋友数使用集合(Set)数据结构最为合适因为它自动去重。n int(input()) numbers list(map(int, input().split())) friend_numbers set()这里我们读取整数N读取接下来的N个数字存入列表初始化一个空集合用于存储朋友数2.2 数字求和的实现接下来实现数字求和的函数。以字符串方法为例def get_friend_number(num): return sum(int(digit) for digit in str(num))这个函数将数字转换为字符串然后遍历每个字符即数字的每一位转换为整数后求和。对于数学方法可以这样实现def get_friend_number(num): total 0 while num 0: total num % 10 num num // 10 return total2.3 完整处理流程将上述部分组合起来n int(input()) numbers list(map(int, input().split())) friend_numbers set() for num in numbers: friend_num get_friend_number(num) friend_numbers.add(friend_num) result sorted(friend_numbers) print(len(result)) print( .join(map(str, result)))2.4 边界条件处理在实际编程中有几个边界情况需要考虑输入数字为0的情况虽然题目说正整数但防御性编程很重要大量输入时的性能问题输出格式要求末尾不能有多余空格改进后的代码def get_friend_number(num): if num 0: return 0 total 0 while num 0: total num % 10 num num // 10 return total n int(input()) numbers list(map(int, input().split())) friend_numbers set() for num in numbers: friend_num get_friend_number(num) friend_numbers.add(friend_num) result sorted(friend_numbers) print(len(result)) if result: print( .join(map(str, result)))3. 算法优化与性能分析3.1 时间复杂度分析让我们分析一下这个算法的时间复杂度输入读取O(N)数字求和对于每个数字最多需要处理5位因为数字10000所以是O(5N) O(N)集合插入O(1)平均时间复杂度排序O(M log M)其中M是不同朋友数的数量最坏情况下MN总体时间复杂度为O(N) O(N) O(N log N) O(N log N)对于N1000来说完全足够。3.2 空间复杂度分析空间使用主要来自存储输入数字O(N)存储朋友数最坏O(N)总体空间复杂度为O(N)同样在合理范围内。3.3 进一步优化思路虽然当前解法已经足够但还可以考虑以下优化流式处理不需要存储所有输入数字可以边读边处理位图法因为朋友数最大可能是999936对于9999可以用一个大小为37的数组代替集合并行处理对于大规模数据可以考虑多线程处理优化后的流式处理版本def get_friend_number(num): total 0 while num 0: total num % 10 num num // 10 return total n int(input()) friend_numbers set() for num in map(int, input().split()): friend_numbers.add(get_friend_number(num)) result sorted(friend_numbers) print(len(result)) if result: print( .join(map(str, result)))4. 常见错误与调试技巧4.1 新手常见错误根据多年教学经验学生在解这类题目时常犯以下错误数字分解错误特别是处理0的时候逻辑不完整去重处理遗漏使用列表而不是集合导致重复计算输出格式错误最后一个数字后面多空格或者空集合时输出格式不对边界条件忽略没有考虑输入数字为0的情况4.2 测试用例设计为了全面测试代码建议准备以下测试用例常规测试输入 3 123 456 789 输出 3 6 15 24重复朋友数测试输入 4 111 12 21 1111 输出 2 3 4边界测试输入 1 9999 输出 1 36零测试输入 2 0 10 输出 2 0 14.3 调试技巧打印中间结果在处理每个数字时打印输入数字和计算出的朋友数小规模测试先用少量数据测试确保基本逻辑正确极端值测试测试最大最小值如0、9999等使用断言在关键步骤添加断言检查不变量调试示例def get_friend_number(num): print(fProcessing {num}) # 调试输出 total 0 while num 0: total num % 10 num num // 10 print(fFriend number: {total}) # 调试输出 return total5. 扩展思考与实际应用5.1 题目变种与扩展这道题目可以有多种变种形式例如加权朋友数每位数字乘以不同的权重再求和多步朋友数重复计算朋友数直到得到个位数数字根乘积朋友数计算数字的乘积而非和大数处理处理非常大的数字超过普通整数范围5.2 实际应用场景数字各位之和的计算在实际中有多种应用校验和计算在数据传输中用于错误检测数字根应用在数论和密码学中有一定应用游戏设计某些数字游戏或谜题的基础数学研究研究数字性质的基本操作5.3 进阶学习建议如果想进一步提升这类问题的解决能力建议学习更多关于数字处理的基础算法熟悉Python中集合、字典等数据结构的高级用法练习类似的编程题目如计算数字的二进制表示中1的个数判断一个数是否为回文数计算数字的阶乘和等6. 不同语言实现对比虽然我们主要用Python实现但了解其他语言的实现方式也有助于理解算法本质。6.1 C实现#include iostream #include set #include algorithm #include vector using namespace std; int getFriendNumber(int num) { int sum 0; while (num 0) { sum num % 10; num / 10; } return sum; } int main() { int n; cin n; setint friendNumbers; for (int i 0; i n; i) { int num; cin num; friendNumbers.insert(getFriendNumber(num)); } cout friendNumbers.size() endl; vectorint result(friendNumbers.begin(), friendNumbers.end()); sort(result.begin(), result.end()); for (size_t i 0; i result.size(); i) { if (i ! 0) cout ; cout result[i]; } return 0; }6.2 Java实现import java.util.*; public class Main { public static int getFriendNumber(int num) { int sum 0; while (num 0) { sum num % 10; num / 10; } return sum; } public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); SetInteger friendNumbers new HashSet(); for (int i 0; i n; i) { int num scanner.nextInt(); friendNumbers.add(getFriendNumber(num)); } ListInteger result new ArrayList(friendNumbers); Collections.sort(result); System.out.println(result.size()); for (int i 0; i result.size(); i) { if (i ! 0) System.out.print( ); System.out.print(result.get(i)); } } }6.3 语言特性对比Python代码简洁内置集合和排序功能强大适合快速实现C性能高但需要手动处理更多细节如输出格式Java介于两者之间有丰富的集合类但语法相对冗长在实际编程竞赛中Python因其简洁性常被选为解题语言但在性能敏感场景下C更有优势。7. 编程竞赛技巧总结通过这道题目我们可以总结出一些通用的编程竞赛技巧理解题意优先确保完全理解题目要求和输入输出格式选择合适数据结构根据问题特点选择集合、字典等数据结构边界条件考虑特别注意0、最大值、最小值等边界情况模块化编程将功能分解为独立函数便于测试和调试测试驱动开发先设计测试用例再编写通过测试的代码重要技巧在竞赛中建议先用简单方法实现一个正确解确保拿到基础分然后再考虑优化。不要一开始就追求完美解法而浪费时间。8. 相关题目推荐为了巩固这类数字处理问题的解法推荐练习以下PAT题目PAT乙级1002 - 写出这个数PAT乙级1019 - 数字黑洞PAT乙级1061 - 判断题PAT甲级1048 - Find Coins这些题目都涉及数字处理和逻辑判断是很好的练习材料。每道题目都有其独特之处通过对比练习可以更好地掌握数字处理的技巧。