每日一题（15）

Question

给定数列的第一项，我们用如下法则生成该数列： 前一项 x，若x为偶数，则该项为x的一半，否则， 该项为x的三倍加1。这样直到有一项是1，停止生成。问：小于1000000的正整数中，哪个数为第一项时该数列的项数最多。

Answer 1

 oooO ↘┏━┓ ↙ Oooo 
 ( 踩)→┃你┃ ←(死 ) 
  \ ( →┃√┃ ← ) / 
　 \_)↗┗━┛ ↖(_/ 

Answer 2

package com.iss.Test;import java.util.ArrayList;public class MaxList
{ public static int getListLength(int start)
{
ArrayList<Integer> list = new ArrayList<Integer>(); list.add(start); produceList(list, start); return list.size();
} public static void produceList(ArrayList<Integer> list, int last)
{
int number = 0;
if (last % 2 == 0)
number = last / 2;
else
number = last * 3 + 1; list.add(number);
if (number == 1)
return;
produceList(list, number); } /**
 * @param args
 */
public static void main(String[] args)
{
int max = 0 ;
int index = 0;
for (int i = 0; i < 100000; i++)
{ int a = getListLength(i + 1);
max = Math.max(a, max);
index = max == a? (i+1):index;
}

System.out.println((index+1)+" " +max);
}}死办法抛砖引玉

Answer 3

效率不高。。 static Set<Long> s = new HashSet<Long>(1000000); public static void main(String[] args) {
long len = 0;
long num = 0;
for (long i = 1; i < 1000000; i++) {
if (s.contains(i)) {
continue;// 跳過已出現的數字
}
long val = d(i, 1);

if (val > len) {
len = val;
num = i;
}
}
System.out.println(num + " " + len);
} public static long d(long i, long c) {
if (i == 1) {
return c;
}
long next;
if (i % 2 == 0) {
next = i / 2;
} else {
next = i * 3 + 1;
}
if (next < 1000000) {
s.add(next);// 記住出現過的數字
}
return d(next, c + 1);
}

Answer 4

不知道答案对不对import java.util.Arrays;public class NumberTest {
public static void main(String[] args) {
final int NUM =1000000;
long begin =System.currentTimeMillis();
Number [] total = new Number[NUM+1];
for(int i=1;i<=total.length;i++){
total[i-1]=getCycle(i);
}
Arrays.sort(total);
long end = System.currentTimeMillis();
System.out.println("总共用时："+(end-begin)/1000+"S");
System.out.println("数字："+total[NUM].getNumber());
System.out.println("循环总数："+total[NUM].getCount());
}
public static Number getCycle(int i){
int j=i;
int count = 0;
while(j!=1){
if(j%2==0){
j=j>>>1;
}else{
j=3*j+1;
}
count++;
}
return new Number(count,i);
}
}
class Number implements Comparable{
private int count;
public int getCount() {
return count;
}
public int getNumber() {
return number;
}
private int number;
public Number(int count,int number){
this.count =count;
this.number = number;
}
public int compareTo(Object o) {
Number n = (Number)o;
return this.count-n.getCount();
}
}

Answer 5

int显然是不行的，改成long可以算出来，但那效率。。

Answer 6

837799需计算524步using System;class CalculateTest
{
    static int[] Counter;    static void Main()
    {
        int upper = 1000000;
        int max = 0, index = 1;
        Counter = new int[upper * 2];        for (int i = 2; i <= upper; i++)
        {
            Solve(i);            if (max < Counter[i])
            {
                max = Counter[i];
                index = i;
            }
        }        Console.WriteLine("{0}需计算{1}步", index, max);
    }    static int Solve(long n)
    {
        if ((n == 1) || (n < Counter.Length && Counter[n] > 0))
            return Counter[n];        int result;        if ((n & 1) == 1)
            result = Solve(n * 3 + 1) + 1;
        else
            result = Solve(n >> 1) + 1;        if (n < Counter.Length)
            Counter[n] = result;        return result;
    }
}

Answer 7

1000w的结果跟你不一样
我的是8400511  685项TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int j = 0;
long iTemp = 0;
for (int i = 1; i <= 10000000; i++) {
iTemp = i;
j = 0;
while (iTemp != 1) {
j++;
iTemp = (iTemp & 1) == 0 ? iTemp >> 1 : iTemp * 3 + 1;
}
map.put(j, i);
}
System.out.println(map.lastEntry());不知道哪里错了.

Answer 8

程序写出来了，不够优化，机子运行太慢，结果还没出来
public class test1 {
static int k=0;
static int n=0;
static int j=0;
public static void main(String[] args) {
for(int x=1;x<1000000;x++){
        fun(x);
        if(n>k){j=x;k=n;}//如果已经存在的最大的循环次数k比最新的循环次数n小的话，记录下最新的x的值，同时，更新最大循环次数,k=n
}
System.out.println(j);//输出n最大时的x值
    }     
    public static int fun(int x){
     int y=x;
     while(y!=1){
     if(y/2==0){
     y=y/2;
     }
     else y=y*3+1;
     n++;
     }
     return n;//每循环一次n加1，可以得出x值时循环了多少次
    }
}欢迎指正错误！

Answer 9

   public static void main(String[] args) throws Exception {
      int i = 1;
      int maxNum = 0;
      int maxCnt = 0;      while(i < 1000000) {
         System.err.print("\n" + i + ":\t");
         int re = generate(i, 0);         if(maxCnt < re) {
            maxCnt = re;
            maxNum = i;
         }         i++;
      }      System.err.println("\nmaxNum = " + maxNum + ", maxCnt = " + maxCnt);
   }
   
   public static int generate(int x, int count) {
      if(String.valueOf(x).indexOf("1") != -1) {
         System.err.print(" count = " + count);
         return count;
      }
      else if(x % 2 == 0) {
         x = x / 2;
      }
      else {
         x = x * 3 + 1;
      }      System.err.print(x + ",");
      return generate(x, ++count);
   }
maxNum = 594, maxCnt = 7

Answer 10

你这个用次数做key，若后面有相同的数循环一样的次数将会覆盖掉最早的那一个

Answer 11

保存已经计算过的数字这个思路是不错的，但也占用内存空间，创建对象的时间开销也不小。
我实现了另外一种优化，空间占用接近0，执行速度仍是毫秒级的
public class Question1 {
public static int count(int x) {
int count = 1;
while (x!=1) {
x = ((x&1)==0)? x>>>1 : 3*x+1;
count++;
}
return count;
} public static void main(String[] args) {
int max=0;
int maxcount=0;
int temp;
long time = System.currentTimeMillis();
for (int i=500001; i<1000000; i++) {
if ((i-1)%3==0 && ((i-1)/3)%2==1)
continue;
temp = count(i); 
if (temp>maxcount) {
maxcount = temp;
max = i;
}
}
System.out.println(max + ", " + maxcount + "项");
System.out.println((double)(System.currentTimeMillis()-time)/1000 + "秒");
}
}

Answer 12

public class Test {    static int i=1;
static int getCount(int num) {
int next;
if ((num & 1) == 0) {
next = num / 2;
} else {
next = 3 * num + 1;
}
if (next != 1) {
i++;
getCount(next);
}
return i+1;
}
public static void main(String[] args) {
System.out.println(getCount(11111));
int max=0;
for(int i=1;i<500000;i++){
max=max>getCount(i)?max:getCount(i);
}
System.out.println(max);
}
}
经测试10万级别可以运行 100万溢出 

Answer 13

用我的count()方法替换掉你的d()方法，耗时1.047秒
public class Question1_sheep {
static Set<Long> s = new HashSet<Long>(1000000);    public static void main(String[] args) {
        long len = 0;
        long num = 0;
long time = System.currentTimeMillis();
        for (long i = 1; i < 1000000; i++) {
            if (s.contains(i)) {
                continue;// 跳過已出現的數字
            }
            //long val = d(i, 1);
            int val = count((int)i);
            
            if (val > len) {
                len = val;
                num = i;
            }
        }
        System.out.println(num + " " + len);
System.out.println((double)(System.currentTimeMillis()-time)/1000 + "秒");
    }
    
public static int count(int x) {
int count = 1;
while (x!=1) {
x = ((x&1)==0)? x>>>1 : 3*x+1;
count++;
}
return count;
} /*
    public static long d(long i, long c) {
        if (i == 1) {
            return c;
        }
        long next;
        if (i % 2 == 0) {
            next = i / 2;
        } else {
            next = i * 3 + 1;
        }
        if (next < 1000000) {
            s.add(next);// 記住出現過的數字
        }
        return d(next, c + 1);
    }*/}

Answer 14

是的，Java的对象创建是很耗时间的一部分
你直接换成一个boolean数组会快很多，如：boolean[] bs = new boolean[1000000];但不管是用boolean[]，还是Set，空间开销也不小的

Answer 15

记忆化搜索
下面这段代码耗时0.14s public static void main(String[] args) {
int CACHE_SIZE = 400000;
long[] cache = new long[CACHE_SIZE];
long start = System.currentTimeMillis();
long current;
int count;
int max = 0;
int maxnr = 0;
for (int i = 1; i < 1000000; i++) {
current = i;
count = 1;
while (current != 1) {
if (current < CACHE_SIZE && cache[(int) current] != 0) {
count += cache[(int) current];
break;
}
current = ((current & 1) == 1) ? (3 * current + 1) : (current >> 1);
count++;
}
if (count > max) {
max = count;
maxnr = i;
}
if (i < CACHE_SIZE && cache[(int)i] == 0)
cache[(int)i] = count;
}
long elapsed = System.currentTimeMillis() - start;
float time = elapsed / 1000.0F;
System.out.println("time = " + time);
System.out.println(maxnr);
}

Answer 16

public class Tmp implements Runnable{
static Object o = new Object();
static int max = 0;
static int maxNumber = 0;
int start;
public Tmp(int x){
start = x * 1000000;
}
public static void main(String[] args) throws InterruptedException {
for(int i = 0; i < 10; i++){
new Thread(new Tmp(i)).start();
}
Thread.sleep(3000);
System.out.println(Tmp.max);
System.out.println(Tmp.maxNumber);
}
public int test(int x){
int count = 0;
while(x != 1){
count++;
x = ((x&1) == 0? x >>> 1 : 3 * x + 1);
}
return count;
}
public void run() {
for(int x = start; x < start + 1000000; x++){
if((x + 1) % 3 == 0)
continue;
int sum = test(x);
synchronized (o){
if(sum > max){
max = sum;
maxNumber = x;
}
}
}
}
}
我这用这个3秒能出答案，但是不知道为啥程序停不了，汗

Answer 17

又来晚了。
小绵羊，你cache干嘛用long啊？一共1000000，max count顶多也就1000000——不可能出现循环

Answer 18

改用int[]，在我的机器上，从39ms（恒定），变成了35ms-36ms，提高了10%。

Answer 19

混点分public class Question { public static void main(String[] args) {
long start = System.currentTimeMillis();
Question a = new Question(1000000);
a.solve();
System.out.println(System.currentTimeMillis() - start + "ms");
} public Question(int max) {
this.arr = new int[max + 1];
arr[1] = 1;
} private int[] arr; public void solve() {
int temp = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == 0)
arr[i] = count(i);
if (arr[i] > arr[temp])
temp = i;
}
System.out.println(temp + " : " + (arr[temp] - 1));
} private int count(long i) {
long temp = (i & 1) == 0 ? i >> 1 : i * 3 + 1;
if (temp < arr.length && arr[(int) temp] > 0) {
if(i < arr.length)
arr[(int) i] = arr[(int) temp] + 1;
return arr[(int) temp] + 1;
} else {
return count(temp) + 1;
}
}}

Answer 20

long够用，但count不一定<=100w

Answer 21

private int count(long i) {
long temp = (i & 1) == 0 ? i >> 1 : i * 3 + 1;
int result = 0;
if (temp < arr.length && arr[(int) temp] > 0) {
result = arr[(int) temp] + 1;
} else {
result = count(temp) + 1;
}
if(i < arr.length)
arr[(int) i] = result;
return result;
}

//    private int count(long i) {
//        long temp = (i & 1) == 0 ? i >> 1 : i * 3 + 1;
//        if (temp < arr.length && arr[(int) temp] > 0) {
//            if(i < arr.length)
//                arr[(int) i] = arr[(int) temp] + 1;
//            return arr[(int) temp] + 1;
//        } else {
//            return count(temp) + 1;
//        }
//    }
改点细节 居然速度提高了 30%

Answer 22

public void solve() {
int temp = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == 0)
count(i);
//arr[i] = count(i); 这里也得改下，刚才忘了
if (arr[i] > arr[temp])
temp = i;
}
System.out.println(temp + " : " + (arr[temp] - 1));
}

Answer 23

继续我的多线程，在我机器上1000 0000级别只要1.5秒 100 0000级别的要0.15秒
public class Tmp implements Runnable{
static Object o = new Object();
static int max = 0;
static int maxNumber = 0;
int start;
static int times = 0;
public Tmp(int x){
start = x * 1000000 + 1;
}
public static void main(String[] args) throws InterruptedException {
long start = System.currentTimeMillis();
for(int i = 5; i < 10; i++){ //只需计算一半以后就可以，因为上边一半可以从下面一半除以2获得
new Thread(new Tmp(i)).start();
}
while(times < 5)
Thread.sleep(10);
long elapsed = System.currentTimeMillis() - start;
float time = elapsed / 1000.0F;
        System.out.println("time = " + time);
System.out.println(Tmp.max);
System.out.println(Tmp.maxNumber);
}
public int test(int x){
int count = 0;
while(x != 1){
count++;
x = ((x&1) == 0? x >>> 1 : 3 * x + 1); //这里学习艾瑞克．泰 老师滴
}
return count;
}
public void run() {
for(int x = start; x < start + 1000000; x++){
if(((x + 1) % 3 == 0) && (((x + 1)/3)&1) == 1) //如果这个数+1除3以后，是个奇数，说明可以从这个奇数获得，就不需要算这个数了
continue;
int sum = test(x);
synchronized (o){
if(sum > max){
max = sum;
maxNumber = x;
}
}
}
System.out.println(start + "is over");
times++;
}
}