函数式编程的例子 Supporting tagline
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