构造15倍数整数算法：C++实现与详解

本实验报告关注于数字构造问题，具体任务是给定一个只包含数字0-9的字符串，目标是利用其中的字符构建一个能被15整除的最大整数。该问题来源于海南师范大学《算法分析与设计》课程的实验部分，由两位同学合作完成。 实验内容分为三个主要步骤： 1. 数据预处理：首先，学生需要读取输入文件`input.txt`，其中包含一串数字，如02041。接下来，他们要统计每个数字出现的次数，并用变量`len`记录数组的长度。在这个过程中，需要特别注意不能有数字5或0，因为它们会影响整除15的结果，如果存在这些数字，实验会直接判断为"impossible"。 2. 算法设计：核心算法是通过排序和贪心策略实现。首先，将输入的字符串转换为整数数组`a[]`，并用`x`表示每个数字的大小，同时记录每个数字是否可用（`bo`）。接着，对数组进行快速排序，将数字从大到小排列。对于每个元素，计算其对3的余数并记录在`rest`字段中。然后，根据余数规则进行操作：若所有数字之和除以3余1，删除最小的余1数；若余2，删除最小的余2数；如果既无余1也无余2，删除两个最小的余2数。最后，如果数组中有0，保持原样输出；若无0，确保至少有一个5在个位上，输出满足条件的整数。 3. 程序实现：实验者编写了C++程序，使用VC++6.0环境运行。程序定义了一个结构体`a[]`，用于存储字符转换的数字、可用标志以及余数信息。通过循环遍历和排序，最终找到符合条件的最大整数。 通过这个实验，学生们不仅锻炼了解决数字构造问题的能力，还学习了快速排序算法、贪心策略以及如何在实际编程环境中应用算法来解决问题。