PAT 1005 继续(3n+1)猜想 (水题 难度2) - 详细讲解

我觉得这题可以代表PAT乙级的考核方向, 主要是以题的怪和难理解为主

仔细点, 把数组开大点可以避免段错误

//继续3n+1猜想
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 10000;

int cont[maxn]; //每个数遇到的次数
int solve(int n)
{
    cont[n]++; //次数+1

    if(n == 1)
        return 0;
    else if(n%2 == 0)
        solve(n/2);
    else
        solve((3*n+1)/2);
    return 0;
}
int main()
{
    int K, num[maxn], ans[maxn];
    ms(ans, 0); ms(cont, 0);
    cin >> K;
    for(int i = 1; i <= K; i++){
        cin >> num[i];
        if(cont[num[i]] <= 1) //剪枝
            solve(num[i]);
    }

    int index = 1;
    for(int i = 1; i <= K; i++)
        if(cont[num[i]] == 1)
            ans[index++] = num[i];
    sort(ans+1, ans+index);
    for(int i = index-1; i > 1; i--)
        printf("%d ", ans[i]);
    printf("%d", ans[1]);

    return 0;
}