Problem14

题目：The following iterative sequence is defined for the set of positive integers:

n  n/2 (n is even)
n  3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13  40  20  10  5  16  8  4  2  1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

(克拉茨问题，求一百万内的一个数，使其经过克拉茨问题的运算后得到的序列最长)

 

 

public class Problem14 {
	private int[] counts;
	private int num;
	
	public Problem14(int num){
		this.num = num;
		counts = new int[num];
	}
	
	public static void main(String[] args) {
		int range = 1000000;
		Problem14 p = new Problem14(range);
		int cmp1 = 0;
		int cmp2 = 0;
		int r = 0;
		int tmp = 0;
		
		long st1 = System.nanoTime();
		for(int i = 1; i<=range; i++){
			tmp = p.comlen(i);
			if(tmp>cmp1){
				cmp1 = tmp;
				r = i;
			}

		}
		
		long et1= System.nanoTime();
		System.out.println(r);
		
		/*
		long st2 = System.nanoTime();
		for(int i = 1; i<=range; i++){
			tmp = p.len(i);
			if(tmp>cmp2){
				cmp2 = tmp;
				r = i;
			}		
		}
		
		long et2= System.nanoTime();
		System.out.println(r);
		*/
		//System.out.println(p.getCounts(1000000));
		System.out.println(et1-st1);
		//System.out.println(et2-st2);
		
		
	}

	public int len(int n){
		long copy = n;
		int len = 1;
		while(copy != 1){
			if(copy%2==0){
				
				copy /= 2;
				if(copy<=num){
					int flag = (int)copy;
					if(counts[flag-1] != 0){
						len += counts[flag-1];
						break;
					}
				}
				len++;
			}else{
				
				copy = 3*copy+1;
				if(copy<=num){
					int flag = (int)copy;
					if(counts[flag-1] != 0){
						len += counts[flag-1];
						break;
					}
				}
				len++;
			}	
		}
		counts[n-1] = len;
		return len;	
	}
	/*
	public int comlen(int n){
		long copy = n;
		int len  = 1;
		while(copy != 1){
			if(copy%2==0)
				copy /= 2;
			else
				copy = 3*copy+1;
			len++;
		}
		return len;
	}
	*/

}

 

我的想法是这样的：

 

按照常规做法，只需计算一百万内各个自然数的Collatz数列，然后比较即可。但这样其实重复了一些过程，比如题中例子：

 

13  40  20  10  5  16  8  4  2  1

 

自然数从13到20的运算是是之前没出现过的，但到了自然数10，不难发现在计算13之前是计算过10的Collatz数列的长度

 

的，所以这个数列计算到10其实可以不必计算了，只需把预先存储起来10的Collatz数列的长度加上13到20这过程中产生

 

自然数个数就可以了。