1005 继续 (3 n+1) 猜想【PAT (Basic Level) Practice （中文）】

1005 继续 (3 n+1) 猜想【PAT (Basic Level) Practice （中文）】

原题链接：1005 继续(3n+1)猜想 (pintia.cn)

1.前言

• 分数：25

• 难度：⭐️⭐️⭐️⚝⚝

• 知识点：

  • C程序设计/数组/一维数组

• 方法技巧：

  • 散列记录：使用数组的下标表示散列的数字，数组元素的值记录与对应数字相关的量。

• 运行限制

  代码长度限制	16 KB
  时间限制	400 ms
  内存限制	64 MB

2.题目描述

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 $n=3$ 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 $n$=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 $n$ 为“关键数”，如果 $n$ 不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：

每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 $K(<100)$，第 2 行给出 K 个互不相同的待验证的正整数 $n(1<n\le 100)$的值，数字间用空格隔开。

输出格式：

每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。

输入样例：

6
3 5 6 7 8 11
1
2

输出样例：

7 6
1

3.解题思路

3.1题目分析

回到1001题回顾一下卡拉兹(Callatz)猜想。卡拉兹(Callatz)猜想：对任何一个正整数 $n$，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把$(3n+1)$ 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 $n=1$。

这个题目要输出关键数，首先要弄清楚什么是关键数。用数组记录下验证卡拉兹猜想递推过程中遇到的每一个数，这些数中，如果某个数 $n$ 没有被其他数字“覆盖”，那么这个数就是关键数。所谓没有被其他数字覆盖就是在验证其他数字的时候没有遇到的这个数字 $n$。

输入样例中6个数字3 5 6 7 8 11。

• 当 n = 3 时，进行卡拉兹猜想验证：3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1。在验证过程中，数字 10、5、16、8、4、2 为被3覆盖的数字。
• 当 n = 5 时，由于 5 已经在验证 3 的过程中出现过，5为被3覆盖的数字。
• 当 n = 6 时，进行卡拉兹猜想验证：6 -> 3 -> …（重复验证 3 的过程），3位被6覆盖的数字。
• 当 n = 7 时，进行卡拉兹猜想验证：7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> …（重复验证 5 的过程），5为被7覆盖的数字。
• 当 n = 8 时，由于 8 已经在验证 3 的过程中出现过，8为被3覆盖的数字。
• 当 n = 11 时，进行卡拉兹猜想验证：11 -> 34 -> 17 -> …（重复验证 17 的过程），17为被11覆盖的数字。

输入的6个数字只有7 6没有被覆盖，所以输出样例为7 6。

3.2基本思路

遍历输入的数字，没有遇到过的数字初始化为关键数，对该数进行验证卡拉兹猜想的递推，将递推过程遇到的数字标记为非关键数（被 “覆盖”），遍历结束仍被标记为关键数的数字就是关键数。

3.3详解步骤

1. 定义一个数组记录递推过程中遇到的数是否为关键数，数组的下标表示数字，数组的值记录该数是否为关键数。这个数组的大小只能估计一下，$n\le 100$，验证过程中会遇到更大的值。（经过测试 $n$ 的值取300作为数组的大小已满足要求。假如300还不够，就取更大的值。）
2. 输入正整数$K$及个$K$互不相同的待验证的正整数。
3. 循环输入$K$个正整数时：
   • 如果输入的数在之前的计算中没有遇到过，则标记为“关键数”，并对该数进行卡拉兹猜想验证计算。
   • 如果输入的数为之前已经验证过的数，则将该数标记为被 “覆盖”的数并且结束验证。
   • 如果验证过程中遇到之前没有验证过的数，将该数标记为被 “覆盖”的数。
4. 按从大到小的顺序输出关键数。

4.3代码详解

#include 
//取300作为记录递推过程中遇到的数的数组的大小
#define MAXN 300
int main(){
    //定义数组c[MAXN]，n是用来记录读入数的临时变量，max是读入的最大值，输出的时候从最大值开始遍历
	int c[MAXN], n, k, i, max=0, flag;
    //第 1 行给出一个正整数 K (<100)
	scanf("%d", &k);
    //初始化数组
	for (i=0; i<MAXN; i++)
		c[i] = 0;
    //循环读入K个数
	for (i=0; i<k; i++) {
		scanf("%d", &n);
         //更新读入的最大值
		if (n>max) max = n;
		if (!c[n]) {//n值没有计算过
			c[n] = -1;//当前n标记为关键数
             //卡拉兹猜想验证
			while (n!=1) {
				if (n%2)n = (3*n+1)/2;
				else n /= 2;
                 //如果遇到之前已经验证过的数将该数标记为被 “覆盖”的数并且结束验证。
				if (c[n]) {
					c[n] = n;
					break;
				}
                 //如果遇到之前没有验证过的数，将该数标记为被 “覆盖”的数。
				else c[n] = n;
			}
		}
	}
    //用来标记输出的第一个数，因为数字间用 1 个空格隔开，但一行中最后一个数字后没有空格，所以第一个数字要单独输出。
	flag = 1;
    //按从大到小的顺序输出关键数。
	for (i=max; i>0; i--) {
		if (c[i]==-1) {
			if (flag) {
				printf("%d", i);
				flag = 0;
			}
			else printf(" %d", i);
		}
	}
	printf("\n");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48