问题描述：当我们验证卡拉兹猜想的时候，为了避免重复的计算，可以记录下递归过程中的每个数。例如对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 个空格隔开，但一行中最后一个数字后没有空格。
输入样例：
6
3 5 6 7 8 11
输出样例：
7 6
题目的要求：给定一系列待验证的正整数，找出需要验证的正整数称为”关键数“，从大到小的顺序输出。
具体思路：
1.用一个数组存储待验证的正整数，并按照从大到小顺序排序。因为输出格式从大到小嘛。
2.在我们验证卡拉兹猜想的时候，记录下递归过程中的每一个数。如果待验证的数存在于unordered_set容器中就不进行递归。我是将数存进一个unordered_set容器，剔除重复的数。
3.遍历存储了待验证的正整数的数组，将不包含在set容器中的元素存储进vector容器中。这样有利于按照指定的格式输出。
Partially Accepted:
实现：
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
void deal(int i, unordered_set<int>& se)
{
if (i == 1)
{
return;
}
if (i % 2 == 0)
{
i = i / 2;
se.insert(i);
deal(i, se);
}
else
{
i = 3 * i + 1;
se.insert(i);
deal(i, se);
}
}
int main()
{
int number;
cin >> number;
vector<int>vec(number);
for (size_t i = 0 ; i < vec.size() ; i++)
{
cin >> vec[i];
}
sort(vec.begin(),vec.end(),greater<int>());
unordered_set<int>se;
for (size_t i = 0; i < number; i++)
{
if (se.find(vec[i]) == se.end())
{
deal(vec[i], se);
}
}
vector<int>result;
for (int i = 0 ; i < number ; i++)
{
if (se.find(vec[i]) == se.end())
{
result.push_back(vec[i]);
}
}
for (size_t i = 0 ; i < result.size() - 1 ; i++ )
{
cout << result[i] << " ";
}
cout << result[result.size() - 1] << endl;
return 0;
}
为了能够节约点内存，我使用了内部容量按四倍增长的动态数组。并且为了不必要的递归，使用查找算法所以选择内部哈希表支撑的unordered_set容器。但是上诉解答是不够好的，错误的。噩梦。发现自己很依赖标准库。
正确解答之一如下：
代码简洁，清晰。利用两个数组就解决了问题。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
//存储结果（需要验证的正整数）的数组
int a[10001] = { 0 };
//存储一系列待验证的正整数
int b[10001];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> b[i];
a[b[i]] = b[i];
}
for (int i = 0; i < n; i++) {
while (b[i] != 1) {
//b[i]为奇数
if (b[i] % 2)b[i] = (3 * b[i] + 1);
//b[i]为偶数
b[i] /= 2;
//剔除不需要验证的正整数，因为已经计算过了
if (a[b[i]])a[b[i]] = 0;
}
}
//对输出的需要验证的正整数从大到小排序
sort(a, a + 101, greater<int>());
for (int i = 0; i < 101; i++) {
if (a[i]) {
if (i != 0)cout << " ";
cout << a[i];
}
}
}
