[问题描述]

考虑如下的序列生成算法:从整数 n 开始,如果 n 是偶数,把它除以 2;如果 n 是奇数,把它乘 3 加1。

用新得到的值重复上述步骤,直到 n = 1 时停止。例如,n = 22 时该算法生成的序列是:

22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

人们猜想(没有得到证明)对于任意整数 n,该算法总能终止于 n = 1。这个猜想对于至少 1 000 000内的整数都是正确的。

对于给定的 n,该序列的元素(包括 1)个数被称为 n 的循环节长度。在上述例子中,22 的循环节长度为 16。

输入两个数 i 和 j,你的任务是计算 i 到 j(包含 i 和 j)之间的整数中,循环节长度的最大值。

[输入]

输入每行包含两个整数 i 和 j。所有整数大于 0,小于 1 000 000。

[输出]

对于每对整数 i 和 j,按原来的顺序输出 i 和 j,然后输出二者之间的整数中的最大循环节长度。这三个整数应该用单个空格隔开,且在同一行输出。对于读入的每一组数据,在输出中应位于单独的一行。

[样例输入]

1 10

100 200

201 210

900 1000

[样例输出]

1 10 20

100 200 125

201 210 89

900 1000 174

思路分析

将i和j从小到大遍历一遍,遍历的过程中求出每个数经过题目中的规则得到1时停止,保留所需的循环节长度,与这个数之前的最大循环节长度进行比较,取大数,即可。

坑1:i和j不一定是i>j,要判断一下

坑2:中间重复的步骤太多,要按照上诉步骤直接求出,会超时,所以需要用HashMap 存一下前面的数(key)对应的循环节长度(value),后面再求的时候,先查询一下该数(key)是否存在,若存在,可直接取出来用,若不存在,再进行计算,这样会省去对一个数的重复计算。

java 代码如下:

import java.util.Scanner;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i,j,MaxCount=-1;
HashMap<Integer,Integer> map = new HashMap();
Integer count = 1;
int a,b; //循环接收数据
while(sc.hasNext()){
i = sc.nextInt();
j = sc.nextInt();
a = i;
b = j; //判断两数的大小
if (a > b) {
a = j;
b = i;
} //循环求出i和j之间的数换算到1的循环节长度,求最大循环节长度
for (int k = a ; k <= b; k++) {
count = map.get(k);
if(count==null){
count = f(k);
map.put(k, count);
}
MaxCount = Math.max(count, MaxCount);
}
System.out.println(i+" "+j+" "+MaxCount);
MaxCount = -1;
}
} //计算循环节长度
static int f(long k) {
int count = 1;
while (k != 1) {
if ((k & 1) == 0) {
k /= 2;
} else {
k = k * 3 + 1;
}
count++;
}
return count;
}
}

最新文章

  1. C语言程序设计第5堂作业
  2. 贪吃蛇C#和JAVA实现
  3. 申请https证书需要注意的4大问题
  4. atitit.基于http json api 接口设计 最佳实践 总结o7
  5. 用JSON-server模拟REST API(一) 安装运行
  6. HTMO DOM部分---小练习;列表之间移动、日期选择、好友选中、滑动效果、滚动条效果、飞入飞出效果。
  7. 【MySQL】binlog缓存的问题和性能
  8. Adobe AIR socket complicating 导致 socket RST
  9. netbean使用技巧
  10. Android 内核初识(4)属性服务器
  11. Mvc学习笔记(4)
  12. javascript 字符串转数字
  13. 201521123048 《java程序设计》 第11周学习总结
  14. Loj 【CQOI 2006】简单题,mmp
  15. 腾讯云服务器使用smtp发送邮件
  16. NO.2: 尽量以const,enum,inline 替换 #define
  17. 彻底删除Cygwin
  18. python 时间戳转元组
  19. 【转】Java并发编程:线程池的使用
  20. java基础知识面试题(1-40)

热门文章

  1. 一个项目中mysql数据库经常死锁的问题解决记录
  2. Java 基础 IO
  3. 【LeetCode每天一题】Jump Game II(跳跃游戏II)
  4. Linux下批量杀掉筛选进程
  5. NOIP2012借教室
  6. Nginx 多域名配置
  7. AR(I)MA时间序列建模过程——步骤和python代码
  8. Shellcode入门
  9. 改变FileUpload文件上传控件的显示方式,确认后上传
  10. SQL语句汇总——数据修改、数据查询