Problem14

1.package com.shui.mu.yao.io.algorithm;  
2.  
3.public class Problem14 {  
4.  
5.    public static void main(String[] args) {  
6.        long starttime = System.currentTimeMillis();  
7.        int start = 640000;/**10：123456789往上翻20再翻40..->640000--1280000*/  
8.        int end = 1000000;  
9.        int[] seed = new int[end];  
10.        int max = 0;  
11.        int digit = 0;  
12.        /**预热10W数据到arr里面 存储seed值*/  
13.        for (int i = 2; i < 10000; i++) {  
14.            find(end, seed, i);  
15.        }  
16.        for (int i = start; i < end; i++) {  
17.            int number=find(end, seed, i);  
18.            if (number > max) {  
19.                max = number;  
20.                digit = i;  
21.            }  
22.        }  
23.        System.out.println("digit: "+digit+"\t"+"maxCount:"+max);  
24.        System.out.println(System.currentTimeMillis() - starttime);  
25.          
26.  
27.    }  
28.  
29.    private static int find(int end, int[] seed, int i) {  
30.        long count = i;  
31.        int number = 0;  
32.        if(seed[i]>0)  
33.            return seed[i];  
34.        while (count != 1) {  
35.            if(count<end&&seed[(int) count]>0)  
36.            {  
37.                number+=seed[(int) count];  
38.                break;  
39.            }  
40.            if ((count & 0X0001) == 0) {  
41.                count = count >> 1;  
42.            } else {  
43.                count = (count << 1) + 1 + count;  
44.            }  
45.            number++;  
46.        }  
47.        seed[i]=number;  
48.        return number;  
49.    }  
50.      
51.  
52.}