google题目

T(0) = T(1) = 1;

T(2) = 2;

T(N) = T(N-1) + T(N-2) + T(N-3);

  • 代码最少的lisp实现
	(defun fact1-google (min mid max count max-count)
	  (case max-count
		(0 1)
		(1 1)
		(2 2)
		(t (if (> count max-count)
		   max
		   (fact1-google mid max (+ min mid max) (1+ count) max-count)))))

	(defun fact-google (n)
	  (fact1-google 1 1 2 3 n))
  • 学习SICP之前的解题1
public class Test {
	private static int iMax;//T(n-1)  max
	private static int iMid;//T(n-2)  mid
	private static int iLast;//T(n-3)  last
	
	public static int fn(int n){
		if(n < 3){
			return ((0==n || 1==n) ? 1 : 2);
		}else{
			init();
			int times = (int) Math.rint(n/3);
				
			while(0 != times){
				//T(n-3) = T(n-4) + T(n-5) + T(n-6)
				iLast = iMax + iMid + iLast;
				//T(n-2) = T(n-4) + T(n-5) + T(n-3)
				iMid = iMax + iMid + iLast;
				//T(n-1) = T(n-4) + T(n-2) + T(n-3)
				iMax = iMax + iMid + iLast;
				times--;
			}
				
			int result = -1;
			if(0 == n % 3) result = iLast;
			if(1 == n % 3) result = iMid;
			if(2 == n % 3) result = iMax;
			
			return result;
		}
	}
        
	public static void init(){
		iMax = 2;
		iMid = 1;
		iLast = 1;
	}

}
  • 学习SICP之后
	public static int fact_google(int n){
			return fact1_google(1, 1, 2, 3, n);
	}
	
	private static int fact1_google(int min, int mid, int max,
int count, int maxCount)
	{
		if(1 == maxCount || 0 == maxCount){
			return 1;
		}
		if(2 == maxCount){
			return 2;
		}
			
		if(count > maxCount) return max;
		else return fact1_google(mid, max, min+mid+max,	++count, maxCount);
	}


blog comments powered by Disqus

Published

14 December 2012

Tags