继续(3n+1)猜想

卡拉兹(Callatz)猜想：

对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 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

C++(g++)代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 获取到被覆盖的数
void get_nums(int, vector<int> &);
// 获取每次循环删除后得到的结果数组
void get_result(vector<int>, vector<int> &);

int main() {
    // 用于接收输入的k个待验证数
    vector<int> input_nums;
    // 用于接收输入的k，即k=count
    int count;
    // 用于接收每次输入的数字，以便存入input_nums
    int num;
    // 输入个数count
    cin >> count;
    // 循环输入count个待验证数字
    for(int i = count; i > 0; -- i)
    {
        cin >> num;
        // 将输入的待验证数字存入input_nums
        input_nums.push_back(num);
    }
    // 由于输入的被验证数 >1,所以无需考虑1的情况
    // 定义用于存放结果的数组
    vector<int> result_nums;
    // 初始化，数据和input_nums相同
    result_nums.assign(input_nums.begin(), input_nums.end());
    // 遍历每一个待验证数
    for(auto n : input_nums)
    {
        // 定义用于接收被覆盖数的数组
        vector<int> nums;
        // 获取n对应的被覆盖数
        get_nums(n, nums);
        // 获取删除待验证数中含有被n覆盖的数后的数组
        get_result(nums, result_nums);
    }
    // 对结果数组进行从小到大排序
    sort(result_nums.begin(), result_nums.end());
    // 逆序结果数组，获得从大到小排序的结果数组
    reverse(result_nums.begin(), result_nums.end());
    // 计算结果数组长度
    int len = result_nums.size();
    // 循环遍历结果数组
    for(int i = 0; i < len; ++ i)
    {
        // 如果遍历数为数组第一位，则直接输出
        if(i == 0)
        {
            cout << result_nums[i];
        }
        // 否则，如果被遍历数不是第一位，则前面带一个空格
        else
        {
            cout << " " << result_nums[i];
        }
    }
    return 0;
}

// 获取到被覆盖的数
void get_nums(int num, vector<int> &nums)
{
    // 根据卡拉兹猜想：如果是偶数，则 /2
    if(num % 2 == 0)
    {
        num = num / 2;
    }
    // 如果是奇数，则 (3n+1)/2
    else
    {
        num = (3 * num + 1) / 2;
    }
    // 将得到的数存入nums
    nums.push_back(num);
    // 结束条件：num=1
    if(num == 1)
    {
        return ;
    }
    // 如果num不等于1，则递归调用该函数
    get_nums(num, nums);
}

// 获取每次循环删除后得到的结果数组
void get_result(vector<int> nums, vector<int> &result_nums)
{
    // 遍历被覆盖数数组以删除结果数组中对应的数字
    for(auto e : nums)
    {
        // 获取结果数组长度
        int len = result_nums.size();
        // 如果要删除的数为结果数组最后一个
        if(e == result_nums[len-1])
        {
            // 删除数组中最后一个数字
            result_nums.pop_back();
        }
        // 如果要删除的数字非结果数组最后一个
        else
        {
            // 查找结果数组中对应的值e
            vector<int>::iterator it = find(result_nums.begin(), result_nums.end(), e);
            // 如果查找成功
            if(it != result_nums.end())
            {
                // 删除查找到的数字
                result_nums.erase(it);
            }
            // 否则什么都不做
        }
    }
}