本文主要是介绍1005继续（3n+1）猜想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
记录自己的做题历程！
https://pintia.cn/problem-sets/994805260223102976/problems/994805320306507776
思想：用容器vector去装给出的几个数据(结构体），结构体中有数组，用来装过程中路过的数，还有一个count用来记是否被覆盖过，被覆盖则加1，每结束一个数，遍历数组的数据，将vector中存在的count加一，此数则是被覆盖的，之后不再关注 ，最后只输出count为0的
#include<iostream>
#include<vector>
using namespace std;
struct num{int value;int *arr=new int[1000];int count;
};
int main(){int n;cin>>n;vector<num> num1;for(int i=0;i<n;i++){num a;cin>>a.value;a.count=0;num1.push_back(a);}for(vector<num>::iterator it=num1.begin();it!=num1.end();it++){if(it->count!=0)continue;int k=0,cou=it->value;while(cou>1){if(cou%2==1){cou=cou*3+1;}else{cou=cou/2;}it->arr[k]=cou;k++;}for(vector<num>::iterator its=num1.begin();its!=num1.end();its++){for(int j=0;j<k;j++){if(its->value==it->arr[j])its->count++;}}}int sum=0;for(vector<num>::iterator it=num1.begin();it!=num1.end();it++){if(it->count==0){if(sum>0)cout<<" "<<endl;cout<<it->value;sum++;}}return 0;
}
这段代码只获得部分正确，所以有地方出了问题。
通过测试数据来看，似乎是因为格式问题 ，以及题目要求未看清，要求从大到小输出
改正方法大概是在输入所有数据后进行一个从大到小排序
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct num{int value;int *arr=new int[1000];int count;
};
bool comp(num a,num b){//sortreturn a.value>b.value;
}
int main(){int n;cin>>n;vector<num> num1;for(int i=0;i<n;i++){num a;cin>>a.value;a.count=0;num1.push_back(a);}sort(num1.begin(),num1.end(),comp);//different from ordinaryfor(vector<num>::iterator it=num1.begin();it!=num1.end();it++){if(it->count!=0)continue;int k=0,cou=it->value;while(cou>1){if(cou%2==1){cou=cou*3+1;}else{cou=cou/2;}it->arr[k]=cou;k++;}for(vector<num>::iterator its=num1.begin();its!=num1.end();its++){for(int j=0;j<k;j++){if(its->value==it->arr[j])its->count++;}}}int sum=0;for(vector<num>::iterator it=num1.begin();it!=num1.end();it++){if(it->count==0){if(sum>0)cout<<" ";cout<<it->value;sum++;}}return 0;
}
此时对了四个，最后一个不对。
我猜想是不是给出的数据只有1个而且是1？发现确实没有考虑当value为1 的问题
于是我改正了一下，将continue的条件加了一个
if(it->count!=0||it->value==1){it->count++;continue;}但是依旧是错的。证明我的思路有个漏洞，但没有找出来
看了一下别人的做法，比我的思路简易
https://github.com/liuchuo/PAT/blob/master/BasicLevel_C++/1005.%20%E7%BB%A7%E7%BB%AD%283n+1%29%E7%8C%9C%E6%83%B3%20%2825%29.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[10000];//直接创建一个足够大的数组，用于记录被覆盖的数，在最后输出时判断一下这些数是否出现过就可以了，省去了我结构体以及vector遍历的麻烦
bool cmp(int a, int b) {return a > b;}
int main() {int k, n, flag = 0;cin >> k;vector<int> v(k);for (int i = 0; i < k; i++) {cin >> n;v[i] = n;while (n != 1) {if (n % 2 != 0) n = 3 * n + 1;//这里可以化简，是我没想到的，但是这里为什么这里没有记录奇数的情况？n = n / 2;if (arr[n] == 1) break;arr[n] = 1;}}sort(v.begin(), v.end(), cmp);for (int i = 0; i < v.size(); i++) {//v.size的运用if (arr[v[i]] == 0) {if (flag == 1) cout << " ";cout << v[i];flag = 1;}}return 0;
}在这里有个疑问，为什么他的没有记录奇数的情况？
等回到学校将回复在评论中或重新发一篇文章。
这篇关于1005继续（3n+1）猜想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
