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

作者： 作者的头像   longzh ,  2021-02-02 10:49:30 ,  所有人可见 ,  阅读 414

0


https://pintia.cn/problem-sets/994805260223102976/problems

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 10000
using namespace std;
bool num[3 * MAX + 1];
int main(void) {
    int n, data;
    vector<int> v;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> data;
        v.push_back(data);
        while (data != 1) {
            if (data % 2)
                data = (3 * data + 1) / 2;
            else
                data /= 2;
            num[data] = true;
        }
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    int flag = 0;
    for (int i = 0; i < v.size(); i++)
        if (num[v[i]] == false) {
            if (flag)
                cout << " ";
            cout << v[i];
            flag = 1;
        }
}

3 评论

用户头像
longzh   2021-02-02 16:04         踩      回复

####代码3

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

using namespace std;

const int N  = 100000;

bool  key[N] ;

int main()
{
    int  k ,data ;
    vector <int>  v ;
    cin >> k ;
    while(k)
    {
        cin >> data ; 
        v.push_back(data);
        while(data != 1)
        {
            if( data % 2 == 0 )  //之前写成 data / 2 == 0，导致while死循环，                               
                data /= 2;       //发生段错误
            else 
                data = (data *3 + 1) /2 ;
            key[data] = true ;
        }                                                                                                                                                                                                                       

          k--;
    }
    sort(v.begin( ), v.end() );
    reverse( v.begin() , v.end() );
    int flag = 0 ; 
    for(int i = 0 ; i < v.size() ; i++ )
    {
        if(key[v[i]] == false )
        {
            if(flag ) 
                cout << " ";
            cout << v[i] ;
            flag = 1;
        }
    }

    return 0;
}
用户头像
longzh   2021-02-02 16:03         踩      回复

应该是 data =(data * 3 + 1)/2;

用户头像
longzh   2021-02-02 11:51         踩      回复

###部分正确，未过原因未知

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

using namespace std;
const int  N = 100000;
bool key[N];

int main()
{
    vector <int >  v ;
    int  k , data; 
    cin  >> k ;
    for( int  i = 0 ;i < k ; i++ )
    {
        cin >> data ;
        v.push_back(data );
        while( data != 1 )
        {
            if(data % 2 == 0) 
                data /= 2 ;
            else 
                data =(data * 3 + 1);
            key[data] = true ;    // 不可以是false,否者结果全部输出
                                  // 因为默认初始化false
        }
    }
    sort(v.begin() , v.end());
    reverse(v.begin() , v.end());
    int flag = 0 ;
    for( int i = 0 ; i< v.size() ;i++)
    {
        if(key[v[i]] == false )
        {
            if(flag)
                cout << " ";
            cout << v[i] ;
            flag = 1 ;
        }
    }
    return 0;


}