卡拉茲(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
#include <iostream>
using namespace std;
void bubbleSort(int* c,int n) //大到小排序
{
int temp;
for(int i = 0;i < n;i++)
{
for (int j = 0; j < n; j++)
{
if (c[i] > c[j])
{
temp = c[i];
c[i] = c[j];
c[j] = temp;
}
}
}
}
int main(){
int n;
int count=0;
cin>>n;
int flag[100]={0};
int c[100];
for(int i=0;i<n;i++){ //輸入n個(gè)數(shù)
cin>>c[i];
}
bubbleSort(c,n); //排序
for(int i=0;i<n;i++){
int m;
m=c[i];
while(m!=1){
if(m%2==1){
m=(3*m+1)/2;
}
else{
m=m/2;
}
for(int i=0;i<n;i++){
if(m==c[i]) {
flag[i]=1;
}
}
}
}
for(int i=0;i<n;i++){
if(flag[i]==0) count++;
}
for(int i=0;i<n;i++){
if(!flag[i]) {
if(count-1>0){
// cout<<count<<endl;
cout<<c[i]<<" ";}
else
cout<<c[i];
count--;
}
}
}
讀完 思路:
//存入數(shù)組先按從大到小排序
//創(chuàng)建一個(gè)大小相同的flag數(shù)組 賦初值為0作為標(biāo)記
//每驗(yàn)證一個(gè)數(shù)就與數(shù)組進(jìn)行對(duì)比 存在就另一個(gè)數(shù)組flag=1
//輸出標(biāo)志位為0的數(shù)字
最后一個(gè)數(shù)不輸出空格，因?yàn)椴皇琼樞蜉敵鲋黄茫圆荒苡玫箶?shù)第二個(gè)數(shù)這種判定剖笙，想了好久最后加了一個(gè)flag=0的count 當(dāng)count=0時(shí)便不輸出空格。
