SICP习题 1.19(对数级?---斐波那契数的再一次优化!!!)

(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q n) (cond ((= n 0) b) ((even? n) (fib-iter a b (+ (square p) (square q)) (+ (* 2 p q) (square q)) (/ n 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- n 1))))) (define (square x) (* x x))

 用java来跑一跑:

/** * Created by Ramble on 2017/11/22. */ public class Fib { public static long digui(long n) { if (n==0) return 0; if (n==1) return 1; else { return digui(n-1)+digui(n-2); } } public static long diedai(long n) { return diedai_iter(1, 0, n); } public static long diedai_iter(long a, long b, long count) { if (count==0) return b; else { return diedai_iter(a+b, a, count-1); } } public static long fib(long n) { return fib_iter(1, 0, 0, 1, n); } public static long fib_iter(long a,long b, long p,long q, long n) { if (n==0) { return b; } if (n%2==0) { return fib_iter(a,b,p*p+q*q,2*p*q+q*q, n/2); } else { return fib_iter(b*q+a*q+a*p,b*p+a*q,p,q,n-1); } } public static void main(String[] args) { long startTime = System.currentTimeMillis();//获取当前时间 //doSomeThing(); //要运行的java程序 // System.out.println(digui(50L)); for (long i=1000; i<5000; i++) { for(long j=1000;j<1200;j++) { long x = diedai(i); long y = diedai(j); long xy = x*y; System.out.println(xy); } } // 程序运行时间：9324ms // for (long i=1000; i<5000; i++) { // for(long j=1000;j<1200;j++) { // long x = fib(i); // long y = fib(j); // long xy = x*y; // System.out.println(xy); // } // } //程序运行时间：4430ms long endTime = System.currentTimeMillis(); System.out.println("程序运行时间："+(endTime-startTime)+"ms"); //12586269025 } }

 经过我拙劣的比较,对数级比线性还是要好很多的.

转载于:https://www.cnblogs.com/R4mble/p/7889983.html

相关资源：sicp：关于Clojure的SICP-源码