PAT乙级 1005 继续(3n+1)猜想
题目
分析
-
这题需要输出的是关键数，首先得知道什么是关键数：
题目中给出了3，5，8，4，2，1这样一组数
将3按(3n+1)的规则计算，(3*n+1)/2=5，(5*3+1)/2=8，8/2=4，4/2=2，2/1=1
在计算过程中可以得到3，5，8，4，2，1，在这组数中5，8，4，2，1都可以由3计算得到，也就是题目中所说的“覆盖”，而5，8，4，2，1计算却无法得到3，因此3是这组数的关键数
-
因此我们可以将输入的每个数都计算一遍，将它们计算过程中出现的数记录下来，最终没有被记录的数就是关键数，输出关键数
-
我们可以用数组来解决问题，数组下标用来存储输入的数，数组的值用来记录是否被“覆盖”了
-
由于K<100，并且待验证的数1<=n<=100，所以数组的长度设置为101，刚好用来存储数字，数组初始值为0
-
先用一个for循环，每输入一个待验证数n，就把它存储到数组num[n]中，同时数组的值加1，表示num[n]存入了数
-
然后再用一个for循环进行(3n+1)计算，只用计算num[n]=1的数，将数组的下标n取出来进行(3n+1)运算(需要再用到一个循环)
-
每循环一次就意味着计算了一次，将计算结果tmp保存下来，并且比较num[tmp]是否等于1，如果等于1，说明它是待验证数，让num[tmp]的值加1，表示它被覆盖了
-
最终计算完成后，数组的值会有三种，等于0表示没有输入过这个数，等于1说明它是待验证数，并且没有被覆盖，也就是关键数，大于1表示被覆盖了，所以接下来的工作就是输出num[n]=1的数
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int k = cin.nextInt();
int[] num = new int[101];//默认初始值为0
for (int i = 0; i < k; ++i) {
int tmp = cin.nextInt();//将输入的值保存到tmp中
num[tmp] = 1;//将输入的值变成数组下标，并记录下来
}
for (int i = 0; i <= 100; ++i) {
if (num[i] == 1) {//只对记录过的数进行计算
int tmp = i;//将下标取出来
while (tmp != 1) {
if (tmp % 2 == 0) {
tmp /= 2;
} else {
tmp = (tmp * 3 + 1) / 2;
}
if (tmp <= 100 && num[tmp] == 1) num[tmp] += 1;//记录每次计算后得到的数，如果它是待验证数就加1
//让tmp<=100的意义在于：在计算过程中会出现很大的数，例如输入的数为97时，计算过程中会出现4616这样的数，如果用num[4616]与1比较的话，数组下标就越界了，而且高于100的数在本题没有用处，因为待验证数最高不超过100，因此加上这个条件就能解决数组下标越界的情况，数组也只用开到101
}
}
}
boolean flag = false;
for (int i = 100; i >= 0; --i) {
if (num[i] == 1) {//num[i]==1表示没有被覆盖，是关键数
if (flag) System.out.print(" ");//在每个数之前输出空格，由于一开始flag为false，所以第一次不会输出空格
System.out.print(i);
flag = true;
}
}
cin.close();
}
}