题目分析

在3n+1的猜想基础上，要求分离出数列中的关键数字。做法就是对于数列中的每一个数字都进行3n+1猜想中的验证，记录过程中间出现的数字。凡是作为中间数出现在验证过程中的数列中的数都是被覆盖的数，予以标记。最后剩下的未被覆盖的就是关键数字，再按照某种算法从大到小输出即可。

算法实现

用两个数组来完成筛选和排序的过程。一个int num[maxn]用于读入数列中的元素，一个bool num_flag[maxn]用于标记每个数字是否被覆盖，初始化全为false表示未覆盖。

对于num数组，遍历之，对其每个元素做3n+1猜想，并将计算过程每个中间数对应的num_flag位标记为true，猜想的计算过程可以递归完成。遍历完后num_flag中被覆盖的数对应位为true，关键数字和非num数组中的数对应的标记位为false。

为实现从大到小排序，用下标i从maxn-1到0进行循环，对每个i检查其是否为num中的数，如果是的话再检查i对应的标记位是否为false，若是则为关键数字。

输出格式要求末尾没有额外空格，因此用一个开关量bool first = true来辨别当前是否为第一个输出的数字，如果是就直接输出并令first = false。对于后续不是第一个输出的数字则先输出空格再输出关键数字。

代码

#include "iostream"
#define maxn 105
using namespace std;

int k = 0, num[maxn];
bool num_flag[maxn];

void set_flag(int num, bool org){
//条件1.判断防止数组越界 条件2.org防止数列中的原有数被标记，保证只标记被覆盖的数
    if(num <= maxn && !org) 
        num_flag[num] = true;
    if(num == 1) return;
    if(num % 2)
        num = (num*3+1) / 2;
    else
        num /= 2;
    set_flag(num, false);
}
// 判断下标是否是数列中的数
bool in_num(int n){
    for(int i=0; i<k; ++i)
        if(num[i] == n)
            return true;
    return false;
}

int main(){
    for(int i=0; i<maxn; ++i)
        num_flag[i] = false;
    cin >> k;
    for(int i=0; i<k; ++i){
        cin >> num[i];
        set_flag(num[i], true);
    }
    bool first = true;
    for(int i=maxn-1; i>=0; --i){
        if(in_num(i))
            if(!num_flag[i])
                if(first){
                    cout << i;
                    first = false;
                }else
                    cout << " " << i;
    }
    return 0;
}

踩坑指南

需要注意，对于num中的数，在第一次传入递归函数时不要对其进行标记，未保持递归函数的可重载性，额外设置一个参数bool org，对于数列中的数首次对其遍历时令org = true，递归调用时令org = false。