試題描述
卡拉茲(Callatz)猜想已經(jīng)在1001中給出了描述幼驶。在這個(gè)題目里，情況稍微有些復(fù)雜。
當(dāng)我們驗(yàn)證卡拉茲猜想的時(shí)候饼疙，為了避免重復(fù)計(jì)算，可以記錄下遞推過(guò)程中遇到的每一個(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í)候遇到過(guò)了倍权，我們稱(chēng)5、8捞烟、4薄声、2是被3“覆蓋”的數(shù)。我們稱(chēng)一個(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ù)字間用空格隔開(kāi)爆办。
輸出格式：每個(gè)測(cè)試用例的輸出占一行，按從大到小的順序輸出關(guān)鍵數(shù)字课梳。數(shù)字間用1個(gè)空格隔開(kāi)距辆，但一行中最后一個(gè)數(shù)字后沒(méi)有空格。
輸入樣例：63 5 6 7 8 11
輸出樣例：7 6
試題代碼
package com.hym.PAT_B;
import java.util.*;
/**
* Created by ymhou on 2016/11/2.
* 通過(guò)全部測(cè)試點(diǎn)暮刃，答案正確
*/
public class PAT_B_1005 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int Num[] = new int[n];
for(int i=0; i<n; i++){
Num[i] = scanner.nextInt();
}
Set<Integer> set = new HashSet<Integer>();
int numtemp[] = new int[n];
for(int i=0; i<n; i++){
numtemp[i]=Num[i];
if(set.contains(numtemp[i])){
continue;
}
while(numtemp[i]!=1){
if(numtemp[i]%2==0){
numtemp[i] = numtemp[i]/2;
}else {
numtemp[i] = (3*numtemp[i]+1)/2;
}
if(set.contains(numtemp[i])){
break;
}
set.add(numtemp[i]);
}
}
int outNum[] = new int[n];
int count=0;
for(int i=0;i<n; i++){
if(set.contains(Num[i])){
continue;
}else {
count++;
outNum[i]=Num[i];
}
}
Arrays.sort(outNum);
for(int i=n-1; i>n-count-1; i--){
System.out.print(outNum[i]);
if(i==n-count){
break;
}
System.out.print(" ");
}
}
}
