The question requirements are:
Callatz conjecture:
For any natural number n, if it is an even number, cut it off in half; if it is an odd number, cut (3n+1) in half. If you keep cutting this repeatedly, you will definitely get n=1 at a certain step. When we verify the Karaz conjecture, in order to avoid repeated calculations, we can record every number encountered during the recursion process. For example, when verifying n=3, we need to calculate 3, 5, 8, 4, 2, and 1. When we verify n=5, 8, 4, and 2, we can directly determine the authenticity of the Karaz conjecture without repeated calculations, because these 4 numbers have been encountered when verifying 3, and we say 5, 8, 4, and 2 are numbers "covered" by 3. We call a certain number n in a sequence a "key number" if n cannot be overwritten by other numbers in the sequence.
Now given a series of numbers to be verified, we only need to verify a few key numbers, so we don’t have to repeatedly verify the remaining numbers. Your task is to find out these key numbers and output them in order from large to small.
Input format: Each test input contains 1 test case. Line 1 gives a positive integer K (<100), line 2 gives K values of K different positive integer n (1<n<=100) to be verified, separated by spaces.
Output format: The output of each test case takes up one row, and key numbers are output in order from large to small. The numbers are separated by 1 space, but there are no spaces after the last number in a line.
Enter a sample:
6
3 5 6 7 8 11
Output sample:
7 6
The code is as follows:
<span style="font-size:14px;"> import java.util.ArrayDequ; import java.util.ArrayList; import java.util.Dequ; 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()) { //Read the keyboard input value for (i = 0; i < numSize; i++) { newArrayDequ.add(scanner.nextInt()); } if (i>=numSize) { break; } } int temp; for (Integer integer : newArrayDequ) { //Save non-critical numbers into closeArrayDequate temp=integer; while (temp!=1) { if (temp%2==0) { temp=temp/2; if (newArrayDequ.contains(temp))) { closeArrayDequ.add(temp); } }else { temp=(temp*3+1)/2; if (newArrayDequ.contains(temp))) { closeArrayDequ.add(temp); } } } } SortedSet<Integer> sortedSet=new TreeSet<Integer>(); //sortedSet is used to store key numbers 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++) { //Output the key number in order from large to small if (j2==leftInt.length-1) { System.out.println(leftInt[j2]); }else { System.out.print(leftInt[j2]+" "); } } } } } </span>The above is all about this article, I hope it will be helpful to everyone's learning.