POJ1207解题报告 Java

import java.util.Scanner;

public class Main {
	public static int[] data=new int[10001];
	/**
	 * @param args
	 */
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int i,j; 
		getTable();     //建立查询表
		int max,big,small;
		while(input.hasNext()){
			i=input.nextInt();
			j=input.nextInt();
			max=0;
			if(j<i){
				big=i;
				small=j;
			}else{
				big=j;
				small=i;
			}
			for(int p=small;p<=big;p++){
				if(data[p]>max)max=data[p];
			}
			System.out.println(i+" "+j+" "+max);
		}
		
		input.close();
	}
	/**
	 * 建立查询表，通过下标数字可以直接查询到该数字需要的轮数
	 */
	public static void getTable(){
		for(int p=1;p<=10000;p++){
			getNum(p);
		}
	}
	/**
	 * 递归算出一个表值
	 * @param i
	 * @return
	 */
	public static int getNum(int i){	
		if(i==1)data[i]=1;
		else if(data[i]!=0)return data[i];
		else if(i%2==0) data[i]=getNum(i/2)+1;
		else if(i%2!=0) {
			if(3*i>=10000)data[i]=getLarge(3*i+1)+1;
			else data[i]=getNum(3*i+1)+1;
		}
		else return 0;
		return data[i];
	}
	/**
	 * 对于大于10000这种出界了的数，只能通过递归而不是查表的方法算
	 * @param i
	 * @return
	 */
	public static int getLarge(int i){	
		if(i<=10000){
			if(data[i]!=0)return data[i];
			else if(i==1)return 1;
			else if(i%2==0) return getLarge(i/2)+1;
			else return getLarge(i*3+1)+1;
		}else{
			if(i%2==0) return getLarge(i/2)+1;
			else return getLarge(i*3+1)+1;
		}
	}

}
           

这就貌似是备忘录+递归的方法。