3n+1问题

3n+1问题

每周一题之1  3n+1问题

大水题

PC/UVa IDs: 110101/100

Popularity: A

Success rate: low Level: 1

测试地址：

​​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

import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int i,j; while (in.hasNext()) { i = in.nextInt(); j = in.nextInt();　　　　　　　int a=i,b=j; if (i > j) { int k = i; i = j; j = k; } int temp = Integer.MIN_VALUE; for (int n = i; n <= j; n++) { int x = fun(n); temp=Math.max(x, temp); } System.out.println(a+ " " + b+ " " + temp); } } static int fun(int n) { int count = 0; while (n != 1) { if (n % 2 == 0) n = n / 2; else n = 3 * n + 1; count++; } count++; return count; }}

优化解法：

package december.year18;import java.util.HashMap;import java.util.Scanner;/** * 3n+1 * @author DGW-PC * @data 2018年12月9日 */public class Solution1 { static HashMap map=new HashMap<>(); public static void main(String[] args) { Scanner cin=new Scanner(System.in); while(cin.hasNext()) { int i=cin.nextInt(); int j=cin.nextInt(); int a=i; int b=j; if(i>j) { a=a^b; b=a^b; a=a^b; } int maxn=Integer.MIN_VALUE; for (int k =i; k <= j; k++) { //检查后面大区间的重复计算问题 Integer fi = map.get(k); if(fi==null) { fi=f(k); map.put(k, fi); } maxn=Integer.max(maxn, fi); } System.out.println(i+" "+j+" "+maxn); } } private static Integer f(long fi) { int count=1; while(fi!=1) { if((fi&1)==0) { fi/=2; }else { fi=fi*3+1; } count++; } return count; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。