乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT (Basic Level) Practice 1005 继续(3n+1)猜想

问题分析

题目提出一个新概念"关键数", 并给出其定义: 在进行(3n+1)猜想时, 不会出现在其他给定数值的计算过程中的, 就是关键数。
这意味着, 如果我们要计算给定的一组数中, 哪些数是关键数, 则需要对这些数进行(3n+1)猜想的计算,
然后记录计算过程中出现的各个数, 等到完全计算完毕后与给定的数值进行对比, 得到差异即可。

统计出现过的数值

1. 不能记录最初输出的数值本身。由于关键数是说没有出现在其他数的计算过程中, 所以不包括起始数值本身。
2. 鉴于第1点, 所以需要先计算(3n+1)猜想的下一个值, 然后记录该该值。
3. 如果下一个值已经被计算过了, 那么由下一值能够覆盖的数也都应该被计算过了, 这时可以直接break;

完整描述步骤

1. 获取输入: 数值个数, 各个数值
2. 初始化统计器:
   • 该数字已经被计算过的标志位 = {False}
3. 对于每一个数值:
   • 进行(3n+1)猜想, 记录除了数值本身之外出现的数(标志位置为1);
4. 将所有数值逆序排列
5. 依次检查每一个数值:
   • 如果该数值的标记位为False:
     • 输出该数值

伪代码描述

1. get input: number_amount, numbers;
2. init recorder:
   • calculated[10000] = {False}
3. for number in numbers:
   • while number != 1:
     • if number % 2 == 1:
       • number = number * 3 + 1;
     • number = number / 2;
     • calculated[number] = True;
4. sort numbers descendingly
5. for number in sorted(numbers):
   • if calculated[number] == False:
     • print(number)

注意事项

1. 题设给定的正整数的取值范围应该是(1, 10000], 所以calculated的个数应该设置为5001及以上。
   • 不然测试点3和测试点4会段错误

完整提交代码

/*
# 问题分析
题目提出一个新概念"关键数", 并给出其定义: 在进行(3n+1)猜想时, 不会出现在其他给定数值的计算过程中的, 就是关键数。
这意味着, 如果我们要计算给定的一组数中, 哪些数是关键数, 则需要对这些数进行(3n+1)猜想的计算,
然后记录计算过程中出现的各个数, 等到完全计算完毕后与给定的数值进行对比, 得到差异即可。## 统计出现过的数值
1. 不能记录最初输出的数值本身。由于关键数是说没有出现在其他数的计算过程中, 所以不包括起始数值本身。
2. 鉴于第1点, 所以需要先计算(3n+1)猜想的下一个值, 然后记录该该值。
3. 如果下一个值已经被计算过了, 那么由下一值能够覆盖的数也都应该被计算过了, 这时可以直接break;# 完整描述步骤
1. 获取输入: 数值个数, 各个数值
2. 初始化统计器:- 该数字已经被计算过的标志位 = {False}
3. 对于每一个数值:- 进行(3n+1)猜想, 记录除了数值本身之外出现的数(标志位置为1);
4. 将所有数值逆序排列
5. 依次检查每一个数值:- 如果该数值的标记位为False:- 输出该数值# 伪代码描述
1. get input: number_amount, numbers;
2. init recorder:- calculated[10000] = {False}
3. for number in numbers:- while number != 1:- if number % 2 == 1:- number = number * 3 + 1;- number = number / 2;- calculated[number] = True;
4. sort numbers descendingly
5. for number in sorted(numbers):- if calculated[number] == False:- print(number)# 注意事项
1. 题设给定的正整数的取值范围应该是(1, 10000], 所以calculated的个数应该设置为5001及以上。- 不然测试点3和测试点4会段错误
*/# includeint cmp(const void *a, const void *b){return *(int*)b - *(int*)a;
}int main(){int calculated[10000] = {0};int number_amount;scanf("%d", &number_amount);int numbers[number_amount], number;for (int i = 0; i < number_amount; i++){scanf("%d", &number);numbers[i] = number;while (number != 1){if (number % 2 == 1){number = number * 3 + 1;}number = number / 2;if (calculated[number] == 1){break;}calculated[number] = 1;}}int first_element_printed = 0;qsort(numbers, number_amount, sizeof(int), cmp);for (int i = 0; i < number_amount; i++){if (calculated[numbers[i]] == 0){if (first_element_printed){printf(" ");}printf("%d", numbers[i]);first_element_printed = 1;}}return 0;
}