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

思路

用数组a下标i代表输入的数据，a[i]表示当前状态。
a[i]有三个取值，0、1、2，分别代表未输入该数据，输入过且没有被验证过，被验证过。

代码

#include<iostream>
using namespace std;

int main(){
    int n,i,b,k = 0,a[105] = {0};
    
    cin>>n;

    for(i = 0;i < n; ++ i){
        cin>>b;

        if(a[b] != 2)a[b] = 1;//后输入的数据，可能被前面的数据验证过

        while(b != 1){
            if(b % 2 == 0)b /= 2;
            else b = (3 * b + 1)/2;

            if(b < 101)a[b] = 2;//3n后b值可能大于100，造成数组越界
        }
    }

    for(i = 100;i > 1; -- i){//从大到小输出

        if(a[i] == 1){//等于1代表输入过且没有被其他输入数据验证过
            if(k == 0){
                cout<<i;
                ++ k;
            }else cout<<' '<<i;
        }
    }
    cout<<endl;

    return 0;

}