【实训报告】算法实现题 2-5 半数集（小郭版）

【实验报告】“半数集（小郭版）”是一个关于算法实现的实践项目，主要目的是让学生掌握分治法的基本思想并能应用到实际问题中。在这个实验中，任务是计算给定自然数n的半数集set(n)中的元素个数。半数集是由n开始，按照特定规则不断生成新数的集合，直至无法再添加新数为止。 实验目标： 1. 理解并运用分治策略。 2. 设计并实现针对半数集问题的分治算法。 3. 使用Java等编程语言编写程序，并进行详细注释。 4. 对测试用例进行验证，确保程序正确性。 5. 分析算法的时间复杂性。 实验要求： 1. 清晰阐述算法设计思路。 2. 实现的函数需满足实验需求，编译运行无误。 3. 确保程序运行结果正确，并有相应提示。 实验环境可根据所选编程语言（如Java）来配置，例如，对于Java，可能需要JDK环境和IDE（如Eclipse或IntelliJ IDEA）。 实验内容： 半数集问题描述了一个自然数n的生成过程，遵循三个规则：n本身在集合中，每次在其左侧加一个不超过最近添加数一半的自然数，直至无法添加新数。例如，set(6)={6,16,26,126,36,136}。 编程任务： 输入数据存储在名为input.txt的文本文件中，每行包含一个整数n(0<n<1000)，程序需计算并输出对应半数集中元素的个数。输出同样写入到output.txt文件中。 算法设计： 解决半数集问题可以采用递归方法，即每个n的半数集个数等于从1到n/2的所有子半数集的个数之和，同时要减去那些在十进制表示下，高位数字大于低位数字的子半数集个数。例如，计算12的半数集个数，需要用到1到6的半数集个数。 源代码分析（Java版本）： 提供的代码使用C语言实现，核心算法函数为`f(int n)`，它使用了递归来计算半数集的元素个数。全局数组`inta`用于存储中间结果，避免重复计算。在`main`函数中，读取用户输入的n值，然后调用`f(n)`计算结果并输出。 运行测试： 需要对不同规模的输入数据进行测试，以确保算法在各种情况下的正确性和效率。测试用例应该覆盖各种边界条件，如n=0、n=1以及较大的n值，以验证算法的正确性和性能。 总结： 这个实验有助于加深对分治算法的理解，并锻炼了将理论知识转化为实际编程技能的能力。通过分析和测试，学生可以进一步掌握算法设计和优化，为解决更复杂的计算问题打下基础。