ACM试题讲解答案详细能运行

根据提供的文件信息，我们可以将这份材料分为五个不同的ACM题目，并对每个题目进行详细解析。 ### 第一题：计算步骤数 #### 题目描述： 对于一个正整数 n (n > 0)，如果 n 是偶数，则将其除以 2；如果 n 是奇数，则将其乘以 3 后加 1。重复此过程直到 n 变为 1，计算总共进行了多少次这样的转换。 **输入格式：** - 一个整数 n。 - n 为 0 时结束输入。 **输出格式：** - 对于每个输入的 n，输出一行表示达到 1 所需的步骤数。 **示例输入：** ``` 3 1 0 ``` **示例输出：** ``` 5 0 ``` #### 解析： 本题采用循环结构，每次判断 n 的奇偶性并执行相应的操作，直至 n 变为 1。同时记录操作次数。 ### 第二题：字符串重排 #### 题目描述： 对于一个由字符 'Z'、'O' 和 'J' 组成的字符串，将其重新排列为多个 "ZOJ" 的形式。如果某个字符的数量不足以组成 "ZOJ"，则按剩余字符数量依次输出这些字符。 **输入格式：** - 一行只包含字符 'Z'、'O' 和 'J' 的字符串。 - 当输入 "E" 时结束。 **输出格式：** - 按题目要求输出重组后的字符串。 **示例输入：** ``` ZZOOOJJJ ZZZZOOOOOJJJ E ``` **示例输出：** ``` ZOJZOJOJ ZOJZOJZOJZOO ``` #### 解析： 首先统计 'Z'、'O'、'J' 的数量，然后按照 "ZOJ" 的顺序输出，直到某一种字符用完为止。之后再依次输出剩余的其他字符。 ### 第三题：寻找未出现的数 #### 题目描述： 给定一系列正整数（不超过 100000），对于每个数 n，计算其按照第一题中的规则转换至 1 的过程中出现的所有数字，并找出其中未出现过的数。 **输入格式：** - 一个正整数 n (n <= 100000)，表示接下来会有 n 个数。 - n 个正整数。 - n 为 0 时结束输入。 **输出格式：** - 对于每个输入的 n 个数，输出一行表示那些在转换过程中没有出现的数。 **示例输入：** ``` 3 384 0 ``` **示例输出：** ``` 3 ``` #### 解析： 使用哈希表记录每个数字是否出现过，在转换过程中更新哈希表。最后遍历输入的数字，输出未出现的数。 ### 第四题：最大值排序 #### 题目描述： 给定一个长度不超过 100000 的数组 w，以及一个正整数 m，求出数组 w 的前 m 个最大值。 **输入格式：** - 一个正整数 n，表示数组 w 的长度。 - n 个整数，构成数组 w。 - 一个正整数 m。 - n 为 0 时结束输入。 **输出格式：** - 输出 m 个整数，即数组 w 的前 m 个最大值。 **示例输入：** ``` 31 25 -1 0 0 ``` **示例输出：** ``` 5 ``` #### 解析： 本题可以使用部分排序的方法解决。先将数组 w 的前 m 个元素排序，然后依次将剩余元素与前 m 个元素的最大值比较并替换，最终得到的 m 个元素即为所求。 ### 第五题：亲属关系查询 #### 题目描述： 定义了一种特殊的亲属关系，包括 parent、child、grandparent 和 great-grandparent。给定一系列关系，求出某个特定关系的数量。 **输入格式：** - 一个正整数 n，表示有 n 行关系数据。 - 每行包含三个字符 a、b、c，表示 a 和 b 之间的关系是 c。 - 一个正整数 m，表示要查询的关系数量。 - m 行，每行包含两个字符 a 和 b，表示要查询 a 和 b 之间的关系。 - n 为 0 时结束输入。 **输出格式：** - 对于每个查询，输出一行表示 a 和 b 之间的关系及数量。 **示例输入：** ``` 32 ABC CDE EFG FA BE 0 0 ``` **示例输出：** ``` great-grandparent 1 ``` #### 解析： 通过结构体定义每个节点的父节点和子节点信息，然后根据查询需求进行递归查找，直到找到相应的亲属关系。