PAT for Java：05-继续(3n+1)猜想：卡拉兹(Callatz)猜想

叁歲伎倆 2021-11-02 06:12 304阅读 0赞

题目源地址：[https://pintia.cn/problem-sets/994805260223102976/problems/type/7][https_pintia.cn_problem-sets_994805260223102976_problems_type_7]

继续(3n+1)猜想：

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。 现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：  
每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。

输出格式：  
每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。

输入样例：  
6  
3 5 6 7 8 11

输出样例：  
7 6

这里本人采用了数组来做，代码如下：

import java.util.Scanner;
    
    /*
     * 当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、
     * 4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。某个数 n为
     * “关键数”，如果 n 不能被数列中的其他数字所覆盖,找出这些关键数字，并按从大到小的顺序输出它们.
     */
    public class Callatz2 {
    
    	public static void main(String[] args) {
    
    		Scanner sc = new Scanner(System.in);
    		int k = sc.nextInt();
    		int numberArr[] = new int[101];// 控制下标在<=100
    		input(sc, k, numberArr);
    		function(numberArr);
    		output(numberArr);
    		sc.close();
    	}
    
    	// 输出格式化
    	private static void output(int[] numberArr) {
    		boolean hasNum = false;
    		for (int i = 100; i > 1; --i) {
    			if (numberArr[i] == 1) {
    				if (hasNum) {
    					System.out.print(" ");
    				}
    				System.out.print(i);
    				hasNum = true;
    			}
    		}
    	}
    
    	// 将覆盖的且在数组下标范围内值为1的下标的元素值赋0
    	private static void function(int[] numberArr) {
    		for (int i = 2; i <= 100; ++i) {
    			if (numberArr[i] == 1) {
    				int temp = i;
    				while (temp != 1) {
    					if (temp % 2 == 0) {
    						temp /= 2;
    						if (temp <= 100 && numberArr[temp] == 1) {
    							numberArr[temp] = 0;
    						}
    					} else {
    						temp = (3 * temp + 1) / 2;
    						if (temp <= 100 && numberArr[temp] == 1) {
    							numberArr[temp] = 0;
    						}
    					}
    				}
    			}
    		}
    	}
    
    	// 将待测数据作为数组下标，数组值赋为1
    	private static void input(Scanner sc, int k, int[] tempNumber) {
    		for (int i = 0; i < k; ++i) {
    			int number = sc.nextInt();
    			tempNumber[number] = 1;
    		}
    	}
    
    }

具体思路：

（1）先将录入的数据作为数组下标并将其元素值设为1，表示这个下标是原始数据；

（2）然后读取值为1的下标进行Callatz判断，将其过程中产生的覆盖数先判断是否小于等于100然后与值为1的数组下标比对，true则将这个下标对应的值赋值为0，表示该下标（原始数据）被覆盖了；

（3）剩下的值为1的即表示没有被覆盖，逆序打印下标即可，记得处理空格。

注意：

（2）过程中产生的覆盖数要判断是否小于等于100再进行赋值操作，否则定义数组时务必要保证数据能够有空间可存，不要小看才1-100，实测过程中产生的最大数不止224=(3\*99+1)\*3+1，大概设置数组空间为3000才够用（其实浪费空间），而采用先判断后加入则只需101即可（最大下标即为数据最大值100，对应数组空间即101，因为最大下标=(length-1)）,经过PAT编译器时，前面几个通过了，只有后面一个或2个没过，很大可能就是这个问题，亲测！

[https_pintia.cn_problem-sets_994805260223102976_problems_type_7]: https://pintia.cn/problem-sets/994805260223102976/problems/type/7