PAT——1005. 继续(3n+1)猜想 (25)
2024-09-04 16:19:53
卡拉兹(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
package com.hone.basicalTry; import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet; /**
* @author Xia
* 思路:采用两个容器,第一个容器用于装过程数,第二个容器用来装载所有的数
* 最后比较过程数中是否包含有所有数中任意一个。如果不包含则说明是关键数。
*
*/
public class Test1005Continue3nPlusOne {
public static void main(String[] args) {
Scanner ss = new Scanner(System.in);
int n = Integer.parseInt(ss.nextLine());
Set<Integer> progress = new TreeSet<>(); //过程中产生的数(这里优先使用TreeSet可以避免添加冗杂数据)
List<Integer> allNum = new ArrayList<>(); //所有的数
for (int i = 0; i < n; i++) {
int a = ss.nextInt();
allNum.add(a);
if (!progress.contains(a)) { //首先判断a是否在过程数容器中,如果不在则开始按照假定的开始计算
while (a != 1) {
if (a%2 ==0) {
a = a/2;
progress.add(a);
}else {
a = (3*a+1)/2;
progress.add(a);
}
}
} } for (int i = 0; i < allNum.size(); i++) {
if (progress.contains(allNum.get(i))) {
allNum.remove(i);
i--;
}
}
Collections.sort(allNum);
for (int i = allNum.size()-1; i > 0; i--) {
System.out.print(allNum.get(i)+" ");
}
System.out.println(allNum.get(0));
}
}
最新文章
- Mysql快速删除表中重复的数据
- 【BZOJ】2938: [Poi2000]病毒
- 剑指offer题目41-50
- C语言 二级指针内存模型②
- Microsoft Script Editor
- c#实现FTP上传
- [python]字符串方法
- 在Github上面搭建Hexo博客(一):部署到Github
- Unity扩展 自定义事件Send组件
- gnome-ssh-askpass:No such file or directory &;&; unable to read askpass response
- 【填坑纪事】一次用System.nanoTime()填坑System.currentTimeMills()的实例记录
- div模拟文本框textarea
- 谷歌浏览器报错 Active resource loading counts reached to a per-frame
- 使用Docx4j创建word文档
- Programming Assignment 2: Deques and Randomized Queues
- js实现数组、对象深度克隆的两种办法
- CodeForces - 1016B
- 三十分钟理解计算图上的微积分:Backpropagation,反向微分
- 每日一Vim(1)
- sql各种连接详解
热门文章
- 六、mybatis分页插件集成
- node.js缓存处理方式
- 查询多表集合(union)、查询时建临时字段、查询时给字段设置默认值
- 排序算法lowb三人组-冒泡排序
- cf1043F. Make It One(dp 容斥原理)
- C# DataGridview转换为DataTable
- vs2010开发activex(MFC)控件/ie插件(三),js调用ocx控件的接口函数
- Android Animation 知识点速记备忘思维导图
- androidwebview timeout
- html tags and attribute集参考