Keshawn_lu's Blog

PAT 1005.继续(3n+1)猜想

字数统计: 703阅读时长: 2 min
2021/02/03 Share

题目简介:

卡拉兹(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≤100)的值,数字间用空格隔开。

输出格式:

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

输入样例:

1
2
6
3 5 6 7 8 11

输出样例:

1
7 6

思路:

定义一个哈希表,若输入的数字在之前的计算中未被覆盖,则初始化为2,否则直接忽略,继续输入下一个数字。

对于之前未被覆盖的数字,按照猜想的方法,进行逐步计算,并将过程中出现的数字对应的哈希表置为1(即该数字被覆盖)。

最后将未被覆盖的数字排序后输出(即哈希表中的值为2)。

代码如下:

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
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main()
{

int K;
cin >> K;

unordered_map<int, int> map;

for (int i = 0; i < K; i++) {

int num;
cin >> num;

if (map[num] == 1) //已被覆盖,不做考虑
continue;
else
map[num] = 2; //初始化

while (num != 1) {

if (num % 2 == 0)
num = num / 2;
else
num = (3 * num + 1) / 2;

if (map[num] == 1) //之前已经被覆盖过了
break;
else
map[num] = 1; //迭代后的数字被覆盖
}
}

vector<int> res;

for (auto item : map) {

if (item.second == 2)
res.push_back(item.first);
}

sort(res.begin(), res.end());

for (int i = res.size() - 1; i > 0; i--) {

cout << res[i] << " ";
}

cout << res[0];
}
CATALOG
  1. 1. 题目简介:
    1. 1.1. 输入格式:
    2. 1.2. 输出格式:
    3. 1.3. 输入样例:
    4. 1.4. 输出样例:
  2. 2. 思路:
  3. 3. 代码如下: