題目要求為：
卡拉茲(Callatz)猜想：
對(duì)任何一個(gè)自然數(shù)n，如果它是偶數(shù)，那么把它砍掉一半；如果它是奇數(shù)，那么把(3n+1)砍掉一半。這樣一直反復(fù)砍下去，最后一定在某一步得到n=1。當(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ò)了，我們稱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ù)字間用空格隔開(kāi)。
輸出格式：每個(gè)測(cè)試用例的輸出占一行，按從大到小的順序輸出關(guān)鍵數(shù)字。數(shù)字間用1個(gè)空格隔開(kāi)，但一行中最后一個(gè)數(shù)字后沒(méi)有空格。
輸入樣例：
6
3 5 6 7 8 11
輸出樣例：
7 6
代碼如下：
<span style="font-size:14px;"> import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; import java.util.Queue; import java.util.Scanner; import java.util.SortedSet; import java.util.TreeSet; public class PAT1005 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int numSize=scanner.nextInt(); ArrayDeque<Integer> newArrayDeque=new ArrayDeque<Integer>(); ArrayDeque<Integer> closeArrayDeque=new ArrayDeque<Integer>(); int i; while (scanner.hasNext()) { //讀取鍵盤(pán)輸入值 for (i = 0; i < numSize; i++) { newArrayDeque.add(scanner.nextInt()); } if (i>=numSize) { break; } } int temp; for (Integer integer : newArrayDeque) { //將非關(guān)鍵數(shù)存入closeArrayDeque中 temp=integer; while (temp!=1) { if (temp%2==0) { temp=temp/2; if (newArrayDeque.contains(temp)) { closeArrayDeque.add(temp); } }else { temp=(temp*3+1)/2; if (newArrayDeque.contains(temp)) { closeArrayDeque.add(temp); } } } } SortedSet<Integer> sortedSet=new TreeSet<Integer>(); //sortedSet用于存放關(guān)鍵數(shù) for (Integer integer : newArrayDeque) { if (!closeArrayDeque.contains(integer)) { sortedSet.add(integer); } } int[] leftInt=new int[sortedSet.size()]; int j=sortedSet.size()-1; for (Integer integer : sortedSet) { leftInt[j]=integer; j--; } for (int j2 = 0; j2 < leftInt.length; j2++) { //按照從大到小的順序輸出關(guān)鍵數(shù) if (j2==leftInt.length-1) { System.out.println(leftInt[j2]); }else { System.out.print(leftInt[j2]+" "); } } } } </span> 以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助。
新聞熱點(diǎn)
疑難解答
圖片精選
