卡拉茲(Callatz)猜想已經(jīng)在1001中給出了描述熏兄。在這個(gè)題目里秘狞，情況稍微有些復(fù)雜。
當(dāng)我們驗(yàn)證卡拉茲猜想的時(shí)候肯夏，為了避免重復(fù)計(jì)算经宏，可以記錄下遞推過程中遇到的每一個(gè)數(shù)犀暑。例如對(duì) n=3 進(jìn)行驗(yàn)證的時(shí)候，我們需要計(jì)算 3烁兰、5耐亏、8、4沪斟、2广辰、1，則當(dāng)我們對(duì) n=5主之、8择吊、4、2 進(jìn)行驗(yàn)證的時(shí)候槽奕，就可以直接判定卡拉茲猜想的真?zhèn)渭妇Γ恍枰貜?fù)計(jì)算，因?yàn)檫@ 4 個(gè)數(shù)已經(jīng)在驗(yàn)證3的時(shí)候遇到過了粤攒，我們稱 5枉长、8、4琼讽、2 是被 3“覆蓋”的數(shù)必峰。我們稱一個(gè)數(shù)列中的某個(gè)數(shù) n 為“關(guān)鍵數(shù)”，如果 n 不能被數(shù)列中的其他數(shù)字所覆蓋钻蹬。
現(xiàn)在給定一系列待驗(yàn)證的數(shù)字吼蚁，我們只需要驗(yàn)證其中的幾個(gè)關(guān)鍵數(shù)，就可以不必再重復(fù)驗(yàn)證余下的數(shù)字问欠。你的任務(wù)就是找出這些關(guān)鍵數(shù)字肝匆，并按從大到小的順序輸出它們。
輸入格式：
每個(gè)測(cè)試輸入包含 1 個(gè)測(cè)試用例顺献，第 1 行給出一個(gè)正整數(shù) K (<100)旗国，第 2 行給出 K 個(gè)互不相同的待驗(yàn)證的正整數(shù) n (1<n≤100)的值，數(shù)字間用空格隔開注整。
輸出格式：
每個(gè)測(cè)試用例的輸出占一行能曾，按從大到小的順序輸出關(guān)鍵數(shù)字。數(shù)字間用 1 個(gè)空格隔開肿轨，但一行中最后一個(gè)數(shù)字后沒有空格寿冕。
輸入樣例：
6
3 5 6 7 8 11
輸出樣例：
7 6
思路：
將給定數(shù)組中的每一個(gè)數(shù)的計(jì)算數(shù)列記錄下來，然后對(duì)這一系列數(shù)組進(jìn)行消除處理椒袍，即：將每個(gè)數(shù)列的第一個(gè)數(shù)驼唱，在其他數(shù)列中（從第二位開始）查找，如果在其他數(shù)列中找到了驹暑，則證明其他數(shù)列包含這個(gè)數(shù)列玫恳，清空自己的數(shù)組數(shù)列辨赐，循環(huán)執(zhí)行，最后留下的就是互相不包含的數(shù)組京办。
//關(guān)鍵的查找循環(huán)體肖油，其中cal是一個(gè)二維的vecotor，存放每一個(gè)數(shù)的計(jì)算數(shù)列
vector<int>::iterator it;
for (int i = 0; i < K; i++)//對(duì)每一個(gè)數(shù)列與其他數(shù)列比較臂港，如果其第一個(gè)元素存在其他數(shù)列中，清空該數(shù)列视搏，并追加首位為0與次位的0
{
for (int j = 0; j < K; j++)
{
it = find(cal[j].begin() + 1, cal[j].end(), cal[i][0]);//從i+1行的第二個(gè)元素開始找
if (it != cal[j].end())//如果在j中找到审孽，清除自己，并追加0以便之后別的數(shù)組查找
{
cal[i].clear();
cal[i].push_back(0);
cal[i].push_back(0);
break;
}
}
}
查找完后余下一堆[0,0]的數(shù)組以及相互包含的數(shù)組浑娜，取出數(shù)組的首位降序輸出即可
代碼：
//1005 繼續(xù)(3n+1)猜想
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void calculate(vector<int> &a, int n)//計(jì)算數(shù)字n的序列并將其存在vector中
{
while (n != 1)
{
a.push_back(n);
if (n % 2 == 0)n /= 2;
else
{
n = (3 * n + 1) / 2;
}
}
}
int main()
{
int K;//存放K個(gè)整數(shù)
cin >> K;
int *store = new int[K];//存放需要判斷的數(shù)佑力；
for (int i = 0; i < K; i++)
{
cin >> store[i];
}
vector<int> *cal = new vector<int>[K];//計(jì)算每一個(gè)的數(shù)列
for (int i = 0; i < K; i++)
{
calculate(cal[i], store[i]);
}
delete[]store;//釋放store
vector<int>::iterator it;
for (int i = 0; i < K; i++)//對(duì)每一個(gè)數(shù)列與其他數(shù)列比較，如果其第一個(gè)元素存在其他數(shù)列中筋遭，清空該數(shù)列打颤，并追加首位為0
{
for (int j = 0; j < K; j++)
{
it = find(cal[j].begin() + 1, cal[j].end(), cal[i][0]);//從i+1行的第二個(gè)元素開始找
if (it != cal[j].end())//如果在j中找到，清除自己
{
cal[i].clear();
cal[i].push_back(0);
cal[i].push_back(0);
break;
}
}
}
vector<int>result;
for (int i = 0; i < K; i++)
{
if (cal[i][0] != 0)
{
result.push_back(cal[i][0]);
}
}
sort(result.begin(), result.end());//將結(jié)果排序,sort默認(rèn)從小到大
reverse(result.begin(), result.end());//排序結(jié)果反序
cout << *result.begin();
for (it = result.begin()+1; it != result.end(); it++)
{
cout <<' ' << *it ;
}
return 0;
}
